Головна |
Для комп'ютерів, заснованих на класичній двійковій системі числення, не завжди можна ефективно вирішувати проблему відсутності механізму виявлення помилок. У 80-х роках XX століття група вчених під керівництвом професора Олексія Петровича Стахова з Таганрозького радіотехнічного інституту створила дослідний екземпляр перешкодостійкого процесора [3]. Цей процесор міг сам контролювати виникаючі в його роботі збої. Для кодування інформації була обрана Фібоначчієва система числення. Її використання дозволило побудувати дивовижний процесор, на званий "Фібоначчі-процесор", або "Ф-процесор". І хоча успішна спроба побудови завадостійкого процесора на основі Фібоначчієва системи числення носила скоріше теоретичний, ніж практичний інтерес, вивчення цієї чудової системи числення заслуговує на увагу.
Для вказівки, що число записано в ФСС, будемо використовувати в нижньому індексі скорочення fib. Наприклад, 10000101fib = 3810.
Числа Фібоначчі - елементи числової послідовності 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, +1597, +2584, +4181, 6765, 10 946,. .., в якій кожне наступне число, починаючи з третього, дорівнює сумі двох попередніх чисел.
Для формального визначення чисел Фібоначчі використовують наступне рекурентне співвідношення:
F0 =1, F1 =1, Fn =Fn2 +Fn1 .
Послідовність, відома у нас як числа Фібоначчі, використовувалася в Стародавній Індії задовго до того, як стала відома в Європі після вивчення та опису її Леонардо Пізанським Фібоначчі (1170-1250).
ФСС відноситься до позиційних систем. Алфавітом ФСС є цифри 0 і 1, а її базисом - послідовність чисел Фібоначчі 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ... Зверніть увагу, що F0 = 1 в базис не включається.
У табл. перераховані деякі числа в двійковій і Фібоначчієва системах числення.
десяткове | двоичное | ФСС |
100 або 11 | ||
1000 або 110 | ||
10010 або 1110 | ||
10100100 або 10011100 або 10100011 або 10011011 |
Фібоначчієва система є різновидом двійковоїсистеми - її алфавіт складають цифри 0 і 1. Отже, цю некласичні двійкову систему числення, взагалі кажучи, можна використовувати для кодування інформації в комп'ютері, так як елементна база сучасної комп'ютерної техніки орієнтована на обробку довічних послідовностей.
Надмірність ФСС проявляється в різних кодових уявленнях одного і того ж числа.
4.1. Алгоритми переведення цілих чисел з ФСС в десяткову систему і назад
Як відомо, все позиційні системи влаштовані однаково і, отже, переклад з будь-якої позиційної системи числення в десяткову здійснюється по одному і тому ж алгоритму.
В P-ічних системах числення базис є геометричною прогресією. Внесок в значення числа цифри a, що стоїть на k-м місці зліва, дорівнює a-Pk, де P - Основа системи числення. Часто кажуть, що "вага" k-го розряду дорівнює Pk.
У ФСС "вага" кожного розряду числа також визначається базисом цієї системи. Для зручності подальшої роботи випишемо "ваги" перших 10 розрядів ФСС (нумерацію розрядів ведемо справа наліво, починаючи з першого). Така нумерація розрядів зручна, оскільки в якості ваги k-го розряду використовується kе число Фібоначчі.
10-й розряд | 9-й розряд | 8-й розряд | 7-й розряд | 6-й розряд | 5-й розряд | 4-й розряд | 3-й розряд | 2-й розряд | 1-й розряд |
Врівноважені системи числення | Способи (форми) записи алгоритмів
Основні алгоритмічні структури | Розширення алгорітміческх структур | Приклад програми з використанням рекурсії | Поняття типу даних | Процедури і функції для роботи з рядками | ВИДІЛЕННЯ І ЗВІЛЬНЕННЯ ДИНАМІЧНОЇ ПАМ'ЯТІ | структуровані ТД | Мови програмування і їх класифікація | Pascal. Змінні і константи |