2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Числа Фибоначчи в двоичной системе счисления
Сообщение12.11.2017, 17:47 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
Последовательность чисел Фибоначчи получаем немного изменив двоичную систему счисления - проведём преобразование. Пример:
$(n)_{notation}$
$(5)_{10}=(101)_2$
Как будем преобразовывать: нули заменим единицами, единицы двойками, после суммируем их. $101\rightarrow 212 \rightarrow 5$
$(6)_{10}=(011)_2 \rightarrow 122 \rightarrow 5$
$(7)_{10}=(111)_2=\rightarrow 222 \rightarrow 6$
Запишем в два столбика числа до преобразования, и после:
$0\rightarrow 1$ ; $1\rightarrow 2$ ; $2\rightarrow3$ ; $3\rightarrow4$ ; $4\rightarrow4$ ; $5\rightarrow5$ ; $6\rightarrow5$ ; $7\rightarrow6$ ; $8\rightarrow5$ ; $9\rightarrow6$ ; $10\rightarrow6$ ; $11\rightarrow7$
Числа справа повторяются, посчитаем их повторения:
$1\rightarrow1$ ; $2\rightarrow1$ ; $3\rightarrow1$ ; $4\rightarrow2$ ; $5\rightarrow3$ ; $6\rightarrow5$ ; $7\rightarrow8$ ; $8\rightarrow13$ ;
Получаем последовательность чисел Фибоначчи.
Чтобы вывести формулу для чисел Фибоначчи, нужно посчитать количество повторений числа. Отмечу, каждое повторяющееся число $n$ (преобразованное из двоичного числа) встречается в натуральном ряду у чисел в промежутке $\min=floor(\left \frac{n+1}{2})\right $ ; $\max=2^{n-1}$ ;
Для примера возьмём повторяющееся число $8$ . Сколькими способами мы можем записать число $8$ суммой из двоек и единиц?
$1+1+1+1+1+1+2$
$1+1+1+1+2+2$
$1+1+2+2+2$
$2+2+2+2$
От каждой из вариантов отнимем по одной двойке:
$1+1+1+1+1+1$
$1+1+1+1+2$
$1+1+2+2$
$2+2+2$
Для каждого случая высчитаем число сочетаний из $n$ (количества чисел) по $k$ (количество двоек), и суммируем их. Получаем:
$$\sum_{k=0}^{floor (\left \frac{n-2}{2} )\right } ( \frac{(n-(k+2))!}{(n-(2k+2))! \cdot k!} )$$
В википедии упоминается лишь про диагональное суммирование в треугольнике Паскаля.

 Профиль  
                  
 
 Re: Числа Фибоначчи в двоичной системе счисления
Сообщение12.11.2017, 18:07 
Заслуженный участник


20/08/14
11071
Россия, Москва
Soul Friend в сообщении #1264766 писал(а):
$(6)_{10}=(011)_2$
Более общеупотребительным является запись старшего значащего бита слева, а не справа. И шестёрка выглядит соответственно наоборот: $6_{10}=110_2$.

-- 12.11.2017, 18:10 --

Soul Friend в сообщении #1264766 писал(а):
Как будем преобразовывать: нули заменим единицами, единицы двойками, после суммируем их.
Это преобразование можно упростить (для понимания): к количеству единиц в двоичной записи добавить длину двоичной записи числа. Или удвоить количество единиц и добавить количество нулей.

-- 12.11.2017, 18:13 --

И что предлагается обсуждать то?

 Профиль  
                  
 
 Re: Числа Фибоначчи в двоичной системе счисления
Сообщение12.11.2017, 19:01 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Soul Friend в сообщении #1264766 писал(а):
В википедии упоминается лишь про диагональное суммирование в треугольнике Паскаля.

Именно диагональное суммирование по Вашей формуле и получаем. Только для $F_{n-1}$. А что даёт двоичная запись, я тоже не понял.

 Профиль  
                  
 
 Re: Числа Фибоначчи в двоичной системе счисления
Сообщение12.11.2017, 19:45 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
Странное проявление (или выявление) последовательности, необычная математическая логика. Хотя, есть и другие формулы для чисел Фибоначчи.

 Профиль  
                  
 
 Re: Числа Фибоначчи в двоичной системе счисления
Сообщение12.11.2017, 20:58 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Да, есть формула Бине. Увязать двоичную запись с биномиальными коэффициентами можно еще исходя из того факта, что сумма элементов $n$-ой строки треугольника Паскаля есть $n$-ая степень двойки. Из двоичной записи получаем нужный набор строк, но такое суммирование годится не только для фибоначчи.

 Профиль  
                  
 
 Re: Числа Фибоначчи в двоичной системе счисления
Сообщение12.11.2017, 22:13 
Заслуженный участник


27/04/09
28128
Soul Friend в сообщении #1264766 писал(а):
Числа справа повторяются, посчитаем их повторения:
$1\rightarrow1$ ; $2\rightarrow1$ ; $3\rightarrow1$ ; $4\rightarrow2$ ; $5\rightarrow3$ ; $6\rightarrow5$ ; $7\rightarrow8$ ; $8\rightarrow13$ ;
Тогда правильнее будет считать, что 1 повторяется 0 раз. И в самом деле, если считать ноль представимым пустой строкой, так и будет (мы же не добавляем слева нули к представлениям других чисел, так и для нуля нечего).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group