Використання системи числення Фібаначчі

ЗМІСТ

      

ВСТУП 2

РОЗДІЛ І. ПЕРЕВОД   ЧИСЕЛ  З  ДЕСЯТКОВОЇ  СИСТЕМИ  ЧИСЛЕННЯ  В Р-ІЧНУ  6

1.1 Два способи переводу  цілих чисел 6

1.2 Перевод кінцевих десятичних дробів  9

РОЗДІЛ ІІ.ЗМІШАНІ  СИСТЕМИ  ЧИСЛЕННЯ   11

РОЗДІЛ ІІІ.СИСТЕМИ  ЧИСЛЕННЯ  ТА  АРХІТЕКТУРА   15

3.1 Використання урівноваженої трійковоїсистемичислення  17

3.2 Використання системи числення  Фібаначчі  18

3.3 Недвійкова комп’ютернаарифметика   20

        ВИСНОВКИ 22

СПИСОК  ВИКОРИСТАНИХ  ДЖЕРЕЛ 24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВСТУП

 

Однію з формальних мов є система числення.

  Система числення – сукупність способів і засобів запису чисел для проведення підрахунків. Звичайною для нас і загальноприйнятою є позиційна десяткова система числення. Як умовні знаки для запису чисел вживаються цифри.

Найпростішим способом запису натурального числа є зображення його за допомогою відповідної кількості паличок або рисочок. Таким способом можна користуватися для невеликих чисел.

Розрізняють такі типи систем числення:

§ непозиційні

§ позиційні;

§ змішані.

Позиційна система числення – система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа. Для позиційних систем числення характерні наочність зображення чисел і відносна простота виконання операцій.

У позиційних системах числення одна і та ж цифра (числовий знак) у записі числа набуває різних значень залежно від своєї позиції. Таким чином, позиція цифри має вагу у числі. Здебільшого вага кожної позиції кратна деякому натуральному числу b (b>1), яке називається основою системи числення.

Основа системи числення –  число, яке означає, у скільки разів одиниця наступного розрядку більше за одиницю попереднього.

Винахід позиційної системи числення, заснованої на помісному значенні цифр, приписують шумерам і вавилонцям. Її було розвинуто індусами і вона отримала неоціненні наслідки для історії людської цивілізації.

Для запису чисел системи числення з основою до 36 включно у якості цифр використовуються арабські цифри (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) а потім букви латинського алфавіту (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z). При цьому, a = 10, b = 11 і т.д.

Також поширені системи числення з основами:

§ 2 – двійкова (у дискретній математиці, інформатиці, програмуванні)

§ 8 – вісімкова (у програмуванні)

§ 12 – дванадцятирічна (мала широке застосування у давнину, подекуди використовується і нині)

§ 16 –  шістнадцятирічна (поширена у програмуванні, а також для кодування шрифтів)

§ 60 –  шістдесяткова (для виміру кутів і, зокрема, довготи і широти)

 

Архітекту́ра ЕОМ — це набір відомостей, необхідний та достатній для написання для даної обчислювальної машини коректних програм на машинній мові, таких, що не залежать від конкретного втілення цієї архітектури. Електронні обчислювальні машини одної архітектури (тобто з однаковою програмною організацією), але реалізовані з використанням різних конструктивних рішень, називають сумісними, або сумісним сімейством ЕОМ.

Найбільшого поширення в ЕОМ отримали 2 типи архітектури: прінстонська (фон Неймана) і гарвардська. Обидві вони виділяють 2 основних вузли ЕОМ: центральний процесор і пам'ять комп'ютера. Різниця полягає в структурі пам'яті: в прінстонській архітектурі програми і дані зберігаються в одному масиві пам'яті і передаються в процесор одним каналом, тоді як гарвардська архітектура передбачає окремі сховища і потоки передачі для команд і даних.

У докладніший опис, що визначає конкретну архітектуру, також входять: структурна схема ЕОМ, засоби і способи доступу до елементів цієї структурної схеми, організація і розрядність інтерфейсів ЕОМ, набір і доступність регістрів, організація пам'яті та способи її адресації, набір і формат машинних команд процесора, способи представлення і формати даних, правила обробки переривань.

За перерахованими ознаками та їх поєднаннями серед архітектур виділяють:

• За розрядністю інтерфейсів і машинних слів: 8 -, 16 -, 32 -, 64-розрядні (ряд ЕОМ має й інші розрядності);
• За особливостями набору регістрів, формату команд і даних: CISC, RISC, VLIW;
• За кількістю центральних процесорів: однопроцесорні, багатопроцесорні, суперскалярні;
• багатопроцесорні за принципом взаємодії з пам'яттю: симетричні багатопроцесорні (SMP), масивно-паралельні (MPP), розподілені.

 

 

РОЗДІЛ І. ПЕРЕВОД  ЧИСЕЛ З ДЕСЯТКОВОЇ СИСТЕМИ ЧИСЛЕННЯ В P-ІЧНУ

 

1. Два способи переводу цілих чисел

 Спосіб 1. Перевод діленням на Р із залишком.

Запишемо число а в Р-ічной системі числення в розгорнутій формі:

 а = апРп + ап_гРп 1 + ... + агР + а0,

де ап, an_v ... av а0  поки невідомі. Тоді, розділивши а на Р із залишком, отримуємо цілу частку:

                апРп~х + ап_хРп~г + ... + аа                         (1.1)

і а0 в залишку, що не перевищує Р- 1. Таким чином, ми визначили останню цифру в Р-ічной записі чісла а. Розділивши отриману частку (1.1) знову на Р, отримаємо в залишку значення ау. Нова частка: anPn ~ 2 + + o, n-iPn1 + . . . + #2. Таким чином, ми визначили передостанню цифру в Р-ічному записі числа а. Продовжуємо цей процес, поки частка при діленні на ціле число стане рівние нулю. Більш формально даний спосіб можна записати у вигляді наступного алгоритму.  

Алгоритм переводу цілого числа з десяткової системи числення в Р-ічную

1. Ділимо вихідне число а на Р остачі в десятковій системі числення і записуємо в якості нового значення десяткового числа а цілу частину результату від ділення.
2. Залишок від ділення замінюємо на відповідну цифру в Р-ічной системі числення і приписуємо її зліва до отриманих раніше цифрам Р-ічного запису числа а (перша отримана цифра відповідає меншому розряду).
3. Виконуємо пункти 1 і 2, до тих пір поки число а не стане рівним 0.

 

 

Приклад 1. Переведемо число 123 в трійкову систему числення.

               123:3=41  (0)                          У дужках вказані залишки від ділення

                 41:3=13  (3)                          на ціле число, які є відповідними

                 13:3=4    (1)                          трійковому вигляду числа.  

                   4:3=1    (1)

                   1:3=0    (1)

 Відповідь: 123 = 111 203

Переведемо це ж число в шістнадцятирічну систему числення.

     123:16 = 7 (11)

      7:16 = 0 (7)

Замінимо число 11 на шістнадцятирічну цифру.

Відповідь: 123 = 7В1б.

 

    Спосіб 2. Цей спосіб заснований на виділенні максимального ступеня числа Р у вихідному десятковому числі.

     Замінимо в розгорнутій формі запису числа в Р-ічній системі всі цифри на максимальну (рівну Р-1) і покажемо, що і в цьому випадку число строго менше, ніж   Pn + 1.  Очевидно, що таке число також не менше, ніж Рn, так як аn > 1.

Рп < апРп + а^Р^1 + ... + агР + а0 <(Р-1)- Рл + (Р-1)-Рл_1 + ... + (Р-1)-Р +

+ (Р-1) = Pп+1 - 1 < Pп+1

Останню рівність отримано з використанням формули суми кінцевого числа членів геометричної прогресії. Для знаходження більшої цифри (аn) в Р-ічному записі числа необхідно знайти такий ступінь числа Р, для якої виконуються нерівності: Рп< а< Рп+1, тобто аn дорівнюватиме цілій частині від ділення а на Рn. Залишком ж від такого поділу є число ал_1Рл_1 + ... + + ахР + а0 > 0. Позначимо його, як і раніше, а. Якщо воно дорівнює нулю, то і всі цифри ап1, ... av а0 рівні 0,  і обчислення закінчуються, в іншому випадку ми знову шукаємо максимальний ступінь k числа Р, для якої справедливо:

Р* < а^ри'1 + ... + ахР + a0Pk+1 < Рп.

Тоді n -1 - k наступних за аn цифр будуть рівні нулю (при n - 1 = k нульові цифри між аn і аk відсутні, а аk отримуємо в результаті поділу без остачі а на Р. Поки залишок від такого поділу не стане дорівнювати нулю, будемо продовжувати описані дії.

 

   Приклад 2. Переведемо другим способом число 100 в двійкову систему числення.

    Використовуючи таблицю двійкових ступенів, запишемо нерівності: 26 <100 <27. Отже, двійковий запис числа 100 складатиметься з 7 цифр. Ціла частина від діленнія 100 на 26 дорівнює 1, тобто більша цифра шуканого числа дорівнює 1. Залишок від ділення 100 на 26 дорівнює 36. Так як  25 < 36 < 26, то і друга зліва цифра дорівнює одиниці. Залишок же від ділення 36 на 2 дорівнює 4 = 2, тобто третя і четверта, а також шоста і сьома цифри в двійковому записі числа 100 нульові.

Відповідь: Ю010 = 11001002.

  

    Приклад 3. Переведемо в шістнадцятирічну систему числення число 525.

Використовуючи таблицю ступенів числа 16, запишемо нерівності: 161 <

< 525 < 162. Отже, запис числа 525 в шістнадцятирічній системі матиме три цифри. Розділимо 525 на 256, отримаємо частку 2 і в залишку 13, таким чином більша цифра в шістнадцятирічному  записі – 2. В силу того, що 13< <161, друга цифра в шістнадцятирічному вигляді дорівнює 0, а меншою цифрою є [13], вона позначається символом D. 

Відповідь: 52510 = 20D16.

    Зауважимо, що другий спосіб переводу ефективний лише тоді, коли нам уже відомі значення всіх ступенів числа Р, які не перевищують вихідне число. Але перевага такого методу полягає в природному порядку записи одержані Р-ічних чисел (зліва направо), що буває важливо при програмуванні: чергова отримана цифра відразу ж може виводитися на друк. У першому ж способі перекладу всі цифри треба попередньо запам'ятати для подальшого роздруковки результату в порядку, зворотному їх отриманню.

 

 

  1.2  Перевод кінцевих десяткових дробів.

 

     В  цьому пункті ми розглянемо  перевод тільки кінцевих десяткових дробів.

Якщо в дробу є ненульова ціла частина, то вона переводиться з десяткової системи в Р-ічну окремо. Сформулюємо правила переводу дробової частини.

     Даний  правильний кінцевий десятковий  дріб. Припустимо , що в Р-ічній системі наш дріб Комерсант має вигляд b =0,Ъ_хЪ_2...Ък... (в Р-ічній системі дріб може виявитися нескінченним). Необхідно знайти цифри b_v Ъ_2> ... > >Ъ_к, ... .

      Запишемо десятковий дріб Ъ в розгорнутій формі в Р-ічній системі числення:

Ъ = Ь_гР-1 + Ь_2Р-2 + ... + Ъ_кР~к + ... .     (1.2)

     Помножимо ліву (саме число) і праву частини виразу (1.2) на Р. У правій частині одержимо:

Ь_! + Ь_2Р~1 + ... + b_kP'k+1 + ...,      (1.3)

значить, перша цифра дробової частини числа Ъ в Р-ічній системі дорівнює цілій частині результату множення десяткового дробу Ь на Р. Дробову частину результату множення позначимо через Ъ, тобто . Ь = Ъ^1 + ... + +Ь_кР~к+1 + ..., і знову помножимо отриману рівність на Р. В результаті праворуч отримаємо: Ъ_2 + &_3Р 1 + ... + Ъ_кР~к+2 ..., і ціла частина результату в лівій частині буде дорівнювати Ъ_2  (друга шукана цифра). Цей процес необхідно продовжувати до тих пір, поки дробова частина результату множення лівої частини на Р не дорівнюватиме нулю або не буде виділений період з повторюваних цифр Ь_г. Іноді процес можна перервати раніше, коли вже досягнута необхідна точність обчислень.

    Сформулюємо описані вище правила перекладу десяткових дробів в Р-ічну систему у вигляді алгоритму.

    Алгоритм перекладу правильних  кінцевих десяткових дробів в  Р-ічну систему числення

Приклад 3. Переведемо число 0,375 в двійкову систему:

0. — перша цифра результату
1. — друга цифра результату
1. — остання цифра результату

 

 Відповідь: 0,375 = 0,0112    

  Переведемо число 0,515625 в четвіркову систему.

0,515625-4 = 2,0625

0,0625-4=0,25

0,25-4=1,0

   Відповідь: 0,515625 = 0,2014.

Приклад 4. Переведемо число 0,123 в п'ятіркову систему.

                                                 

 

 

Дробова частина останнього виразу, рівна вже зустрічалася раніше, дробової частини, отже, останні дві цифри утворюють період п’ятіркового дробу.

 

РОЗДІЛ ІІ. ЗМІШАНІ СИСТЕМИ ЧИСЛЕННЯ

 

     У деяких випадках числа, задані в системі числення з основою Q, доводиться зображати за допомогою цифр в інший Р-ічній системі числення.

   Визначення 1. Системи числення, в яких кожен коефіцієнт розкладання числа  за  ступенями   Q (цифра Q-ічної системи  числення)  записується  в

Р-ічній системі числення, називаються змішаними. Інакше такі системи називають P-Q-ічними.

    Наприклад, раніше широке поширення в обчислювальній техніці мала двійково-десяткова система. У двійково-десятковій системі числення основою системи числення є число 10, але всі десяткові цифри окремо кодуються чотирма двійковими цифрами і в такому вигляді записуються послідовно один за одним. Так, число 83910 в двійково-десятковій системі числення буде записуватися як 1000001110012_10. Зауважимо, що таке подання володіє надмірністю, оскільки чотири двійкові цифри можуть кодувати не 10, а 16 різних чисел.

    Особливий інтерес представляє випадок, коли Q=Pm, де  m n – натуральне число. Для таких систем вид числа в P-Q-ічній системі збігається з видом числа в Р-ічній системі. Тоді перевод чисел з Р-ічної системи числення в Q-ічну і навпаки може проводитися за більш простим алгоритмам (сформулюємо і доведемо їх поки тільки для цілих чисел).

    Теорема 1. Для того щоб перевести ціле число з системи числення з основою Р в систему числення з основою Q = Рт, де т – натуральне число, достатньо записати числа в Р-ічній системі розбити на групи по т п цифр, починаючи з правої цифри, і кожну таку групу замінити однією цифрою в Q-ічній системі. наприклад: 101012 = 10|101 = 25g