10 января 2018

Мостовая Е.Е. Необычные системы счисления. Фибоначчиева система счисления

Мостовая Елена Евгеньевна,
учитель информатики
ГБОУ г. Москвы «Школа № 1370»,
Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.

 

В 1202 г. итальянский математик Леонард Пизанский (Leonardo Pisanto, около 1170 – около 1228), известный под именем Фибоначчи (Fibonacci), предложил такую задачу:

Пара кроликов каждый месяц дает приплод – двух кроликов (самца и самку), от которых через два месяца уже получается новый приплод. Сколько кроликов будет через год, если в начале года мы имели одну пару молодых кроликов?

Числа, соответствующие количеству кроликов составляют последовательность:  1, 1, 2, 3, 5, 8, 13, 21, 34, …

Каждый из членов этой последовательности, начиная с третьего, равен сумме двух предыдущих членов. Эта последовательность называется рядом Фибоначчи, а ее члены – числами Фибоначчи. На уроках математики  эти числа связаны с так называемым золотым сечениям. На уроках информатики числа Фибоначчи широко используются для объяснения рекурсивной зависимости, где F(n)=F(n-1) + F(n-2), при n³3, F(1)=1 и F(2)=1.

Таким образом, получаем, что:

F(1) =1,

F(2)=1,

F(3)=1+1 = 2,

F(4)=1+2 = 3,

F(5)=2+3 = 5,

F(6)= 3+5 = 8 и т.д.

В итоге, получаем числа: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …

Но мало кто знает, что числа Фибоначчи используются в так называемой Фибоначчиевой системе счисления.

В старшей школе при изучении темы «Кодирование информации» я предлагаю обучающимся познакомиться с Фибоначчиевой системой счисления в целях расширения представлений о системах счисления и обобщения принципа позиционности.

Обучающиеся узнают, что принцип разложения любого числа в Фибоначчиевой системе счисления основывается на уже знакомом им переводе десятичного числа в двоичное «Методом подбора степеней числа 2»: исходное десятичное число представляют в виде суммы степеней числа 2, в этой сумме слагаемые выстраивают от большего к меньшему. Затем те степени двойки, которые имеются, заменяются 1, а те, которых нет заменяются на 0.

Например, число 37 будет представлено в двоичной системе счисления, как 100101 согласно разложению:

исходное десятичное число степени числа «два»
32 16 8 4 2 1
37 1 0 0 1 0 1

 

Т.е. в разложении десятичного числа используются двоичные цифры (алфавит) – только 0 и 1. Следовательно, если запись числа в фибоначчиевой системе имеет вид f(n), f(n–1), …, f(2), f(1), то этому числу соответствует десятичное значение, равное  , где F(k) – числа Фибоначчи, f(k) Î {0, 1}, причем в записи числа две единицы не должны стоять рядом, что очень важно: при несоблюдении этого условия запись числа будет неоднозначной.

Например, число 5 в десятичной системе счисления может быть записано как 110Fib (5 = 1 · 3 + 1 · 2 + 0 · 1).

Разложение (вариант 1)

исходное десятичное число Базисные числа фибоначчиевой системы счисления
3 2 1
5 1 1 0

 

и 1000Fib (5 = 1 · 5 + 0 · 3 + 0 · 2 + 0 · 1), разложение (вариант 2)

исходное десятичное число Базисные числа фибоначчиевой системы счисления
5 3 2 1
5 1 0 0 0

 

Причем, правильным считается второе разложение, где в записи нет двух подряд идущих единиц. В этом случае каждое натуральное число в фибоначчиевой системе счисления записывается единственным образом.

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

Задание 1. Найдите все способы перевода следующих чисел из десятичной системы счисления в фибоначчиеву, например, чисел 37 и 25.

Вариант решения обучающегося: Перевод числа из десятичной системы счисления в фибоначчиевую:

исходное десятичное число Базисные числа фибоначчиевой системы счисления
34 21 13 8 5 3 2 1
37 1 0 0 0 0 1 0 0

 

3710 = 34 + 3 = 1*34+0*21+0*13+0*8+0*5+1*3+0*2+0*1= 10000100Fib

исходное десятичное число Базисные числа фибоначчиевой системы счисления
  21 13 8 5 3 2 1
25   1 0 0 0 1 0 1

 

2510 = 21 + 3 + 1 = 1*21+0*13+0*8+0*5+1*3+0*2+1*1=100101Fib

Задание 2. Переведите в десятичную систему числа, записанные в фибоначчиевой системе, например числа: 10010101 и 101010101.

Вариант решения обучающегося: Перевод числа из фибоначчиевой системы счисления в десятичную:

неизвестное десятичное число Базисные числа фибоначчиевой системы счисления
34 21 13 8 5 3 2 1
? 1 0 0 1 0 1 0 1

 

10010101Fib=1*34+0*21+0*13+1*8+0*5+1*3+0*2+1*1=4610

неизвестное десятичное число Базисные числа фибоначчиевой системы счисления
55 34 21 13 8 5 3 2 1
? 1 0 1 0 1 0 1 0 1

 

101010101Fib=1*55+1*21+0*13+1*8+0*5+1*3+0*2+1*1=8810

Необходимо отметить, что, хотя для записи числа в этой системе счисления используются только цифры 0 и 1, эту запись нельзя считать двоичным представлением числа.

Список литературы:

1. Фибоначчиева система счисления // Материал из Википедии – свободной энциклопедии. [Электронный ресурс]. URL: http://ru.wikipedia.org/wiki/Фибоначчиева_система_счисления (дата обращения: 07.01.2018).
2. MAXimal. [Электронный ресурс]. URL: http://www.e-maxx.ru/algo/fibonacci_numbers (дата обращения: 07.01.2018).
 
Мнение редакции может не совпадать с мнением авторов.
Просмотров 1264