Презентация, доклад по информатике для учащихся 10-х классов Код Фибоначчи - основа арифметики будущих компьютеров

ко Всероссийскому уроку информатики «Час кода 1017»

МОУ СОШ №12 с УИОП. Егорьевск

Владимир Утенков

цифры зависит от ее положения в записи числа.
Базис позиционной системы счисления – последовательность чисел, на которые умножают цифры в зависимости от их позиций.
Поясним эти понятия на примере всем хорошо знакомой десятичной позиционной системы счисления:
Алфавит: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Размерность: 10.
Базис позиционной системы счисления: 1, 10, 100, 1000, 10…. то есть степени числа: 100, 101, 102, 103, … 10n…;
Пример:
2034510
↓
2∙104 + 0∙103 + 3∙102 + 4∙101 + 5∙100
Такая система счисления называется аддитивно-мультипликативной – значение числа определяется как сумма ряда (аддитивно), а члены ряда определяются умножением цифры на ее вес (мультипликативно).

в алфавите – двоичная.
Алфавит – 0, 1.
Размерность – 2.
Базис – 20=1, 21=2, 22=4, …, 2j, …
Пример:
1001012
↓
1∙25 + 0∙24 + 0∙23 + 1∙22 + 0∙21 + 1∙20 = 3710
Двоичная система является основой всей современной цифровой техники.

использовать так называемый дополнительных код числа.
Процедура записи отрицательного двоичного числа:
- инвертировать запись числа, заменив 0 на 1, а 1 на 0;
- прибавить к числу единицу.
Пример:
1110 = 10112
Двоичный код числа -1110 вычисляется так:
1011 → 00001011 → 11110100 + 1 = 11110101
2. Двоичный код не имеет так называемой избыточности, то есть одна ошибка в нем кардинально изменяет значение закодированного числа.
Пример:
4710 = 1011112 → 1010112 = 4310
В условиях, когда надежность технических систем все больше зависит от надежности работы управляющих ими компьютерных систем и цифровых систем связи, эффективные механизмы обнаружения и автоматического исправления ошибок кодирования приобретают решающее значение.
Поэтому предлагаются числовые системы основанные на других принципах.

Ошибка

системой, но и системой, основанной на иных принципах. Пример - измерение времени. Рассмотрим запись вида:
10 часов 12 минут 11 секунд вечера, 7 апреля 2016 года
Эта запись содержит:
- количество часов в 12-ричной системе с указанием времени суток (вечер), правда количество часов можно было указать и в 24-ричной системе как 22 часа);
- количество минут и секунд в 60-ричной системе:
- день месяца в системе, основание которого зависит от месяца (в апреле, например, 30 дней, а в марте 31, в феврале 28 или 29 и т.д.);
- название месяца в 12-ричной системе;
- год в десятичной системе.
Кроме того, по календарю на 2016 год можно определить, что этот день приходится на четверг. Это еще и так называемый лунный цикл из 28 дней, разбитый на 4 недели.
Еще один пример: в быту используется 12-ричная числовая система (число 12 называется дюжина) , так как она удобнее для деления, чем десятичная (число 12 делится на 6, 4, 3, 2, а число 10 только на 5 и 2).

правилам:
- два первых числа ряда: 1; 1;
- последующие числа ряда образуются как сумма двух предыдущих, следующее число: 1+1 =2;
- следующее: 1+2=3;
- следующее: 2+3=5 и т. д.
Таким образом, ряд Фибоначчи имеет вид:
1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; …
Особенностью ряда Фибоначчи является то что числа в нем быстро увеличиваются. Так член ряда с номером 35 имеет значение 9 227 465.
Если последовательно делить очередное число Фибоначчи на предыдущее, получается со все большей точностью иррациональное число примерно равное 1,612, которое называют золотое сечение. Это отношение встречается в пропорциях многих произведений искусства.

Леонардо Пизанский (род. около 1170 года, ум. около 1250 года) — первый крупный математик средневековой Европы. Наиболее известен под прозвищем Фибоначчи.

лишенных этих недостатков. В последние десятилетия XX века советский ученый А. П. Стахов предложил числовую систему с базисом из ряда Фибоначчи:
Алфавит: 0, 1.
Размерность: 2.
Базис позиционной системы счисления: 1, 2, 3, 5, 8, 13, 21, 34,…
Пример:
10110fib
↓
1∙8 + 0∙5 + 1∙3 + 1∙2 + 0∙1 = 1310
Оказывается в этой системе каждой последовательности из единиц и нулей соответствует единственное число, но числу большему 2 соответствует несколько последовательностей из единиц и нулей.
Пример: 310 = 1∙3 + 0∙2 + 0∙1 → 100fib
310 = 0∙3 + 1∙2 + 1∙1 → 011fib

и то же число во множество его представлений в этой системе с помощью специальных фибоначчиевых операций свертки и развертки, выполняемых над кодовым изображением числа:
свертка: 011 → 100;
развертка: 100 → 011.
Смысл этих операций легко понять, если вспомнить, что базисом фибоначчиевой системы является ряд чисел, в котором следующее число является суммой двух предыдущих, а так как ненулевое значение в разряде означает, что это число из ряда и что два соседних с ним в сумме должны быть ему равны: 5=3+2; 8=5+3; 13=8+5 и т.д.
Если над кодовым изображением числа произвести все возможные развертки, то мы придем к специальному фибоначчиевому изображению, называемому максимальной формой.
Пример:
для числа 9810 = 1000010001fib → 100 0010001 fib → 011 0010001 fib → 0110010001 fib → 0101110001 fib → 0101110001 fib → 0101101101 fib →101101101 fib
В максимальной (или развернутой) форме рядом не встречаются два нуля.

мы придем к специальному фибоначчиевому изображению, называемому минимальной формой.
Пример:
для числа 2510 = 110101fib → 0110101fib → 1000101fib → 1000101fib
В минимальной форме рядом не встречаются две единицы.
Для исследования фибоначчиевой числовой системы автором разработана компьютерная программа. Она написана на языке QBasic 4.5 и откомпилирована:








Задание: перевести в фибоначчиевую форму числа: 7; 123; 445, 7 722 144.
Преобразовать в минимальную и максимальную формы число 100111010fib

Пуск программы

В ней вы вводите фибоначчиевое представление числа, получаете его десятичное представление и выполнение свертки и развертки (образование минимальной и максимальной форм).









011001100011
100010000100

Пуск программы

Образование минимальной формы

применяют следующий алгоритм:
1. Числа записывают одно над другим поразрядно, добавив нули слева:
1210 = A = 10101fib → 10101
710 = B = 1010fib → 01010
2. Единицы из числа A перемещают на место нулей числа B:
A = 10101 00000
↓ ↓ ↓ →
B = 01010 11111
3. Для числа B выполняют операции приведения к минимальной форме:
B = 11111 → 011111 → 100111 → 100111 → 101001
Проверим результат с помощью программы преобразования чисел в фибоначчиевую форму:
A+B = 1210 +710 = 1910 = 101001fib
Ученые под руководством А. П. Стахова разработали алгоритмы вычитания, умножения и деления в фибоначчиевой числовой системе. Смотри здесь.