Головна

Фібоначчієва система числення (фсс)

  1. IV. фінансова система
  2. IX. Система органів сечовиділення
  3. SCADA-система Intouch
  4. SCADA-система WinCC
  5. V Лекція 8 класифікаційної системи Л. Н. Пушкарьова
  6. V2: Система національних рахунків і макроекономічні показники
  7. XIV. система права

Для комп'ютерів, заснованих на класичній двійковій системі числення, не завжди можна ефективно вирішувати проблему відсутності механізму виявлення помилок. У 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. Змінні і константи |

© 2016-2022  um.co.ua - учбові матеріали та реферати