10 класс Код Фибоначчи - основа арифметики будущих компьютеров учебный материал ко Всероссийскому уроку информатики «Час кода
Что такое числовая система
Двоичная позиционная ЧС
Недостатки двоичной ЧС
Нетрадиционные ЧС
Числовой ряд Фибоначчи
Фибоначчиевая ЧС
Фибоначчиевая ЧС
Фибоначчиевая ЧС
Свертка и развертка
Арифметика в фиб. ЧС
595.00K
Category: informaticsinformatics

Код Фибоначчи - основа арифметики будущих компьютеров

1. 10 класс Код Фибоначчи - основа арифметики будущих компьютеров учебный материал ко Всероссийскому уроку информатики «Час кода

МОУ СОШ №12 с УИОП. Егорьевск
Владимир Утенков
10 класс
Код Фибоначчи - основа арифметики
будущих компьютеров
учебный материал ко Всероссийскому уроку информатики
«Час кода 1017»

2. Что такое числовая система

Позиционная система счисления – в ней количественный эквивалент цифры
зависит от ее положения в записи числа.
Базис позиционной системы счисления – последовательность чисел, на
которые умножают цифры в зависимости от их позиций.
Поясним эти понятия на примере всем хорошо знакомой десятичной
позиционной системы счисления:
Алфавит: 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
Такая система счисления называется аддитивно-мультипликативной –
значение числа определяется как сумма ряда (аддитивно), а члены ряда
определяются умножением цифры на ее вес (мультипликативно).

3. Двоичная позиционная ЧС

Наиболее просто технически реализуется числовая система с двумя числами
в алфавите – двоичная.
Алфавит – 0, 1.
Размерность – 2.
Базис – 20=1, 21=2, 22=4, …, 2j, …
Пример:
1001012

1∙25 + 0∙24 + 0∙23 + 1∙22 + 0∙21 + 1∙20 = 3710
Двоичная система является основой всей современной цифровой техники.

4. Недостатки двоичной ЧС

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

5. Нетрадиционные ЧС

Мы с вами пользуемся не только привычной нам десятичной позиционной
системой, но и системой, основанной на иных принципах. Пример измерение времени. Рассмотрим запись вида:
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).

6. Числовой ряд Фибоначчи

Средневековый математик Фибоначчи придумал
числовой ряд построенный по следующим
правилам:
- два первых числа ряда: 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 года) —
первый крупный
математик средневековой
Европы. Наиболее
известен под прозвищем
Фибоначчи.

7. Фибоначчиевая ЧС

Недостатки свойственные позиционной двоичной системе стимулировали
поиски других числовых систем, лишенных этих недостатков. В последние
десятилетия 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

8. Фибоначчиевая ЧС

У фибоначчиевой числовой системы есть интересное свойство: можно
преобразовывать одно и то же число во множество его представлений в
этой системе с помощью специальных фибоначчиевых операций свертки
и развертки, выполняемых над кодовым изображением числа:
свертка: 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
В максимальной (или развернутой) форме рядом не встречаются два нуля.

9. Фибоначчиевая ЧС

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

10. Свертка и развертка

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

11. Арифметика в фиб. ЧС

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