количество 16-ти разрядных чисел в двоичной системе счислени

[lad_2007-39]

Как определить: число, равное количеству 16-ти значных чисел в двоичной системе счисления, таких, что их запись не содержит двух идущих подряд нулей.

Всем откликнувшимся - спасибо

[Circiter]

Непосредственная проверка дает ответ 4180 (если я не ошибся). А как решать, пока не знаю...

[paha]

lad_2007-39 в сообщении #395077 писал(а):

число, равное количеству 16-ти значных чисел в двоичной системе счисления, таких, что их запись не содержит двух идущих подряд нулей

по индукции:)

У меня получилось $F_{17}=1597$ (17-ое число Фибоначчи)

Circiter в сообщении #395107 писал(а):

(если я не ошибся)

[gris]

Может быть посчитать отдельно для каждого количества нулей?
0 - 1
1 - 16 или 15
...
8 - 2 или 1
Или относится к тому, считается число 16-значным с учётом ведущих нулей или нет.

[ewert]

Пусть $N(m)$ -- количество "хороших" чисел из $m$ разрядов. Тогда $N(m)=N_0(m)+N_1(m)$, где $N_0(m)$ -- количество хороших чисел, начинающихся с нуля и, соответственно, $N_1(m)$ -- с единицы. Имеем рекуррентные соотношения:

$N_0(m+1)=N_1(m);$
$N_1(m+1)=N(m)=N_0(m)+N_1(m).$

Получается, да, последовательность Фибоначчи. Только вроде как это будет $N(16)=2584$ (учитывая, что $N(1)=2$ и $N(2)=3$, очевидно).

[paha]

gris в сообщении #395124 писал(а):

Или относится к тому, считается число 16-значным с учётом ведущих нулей или нет.

все-таки 1=01 -- не двузначное число:)

-- Вт янв 04, 2011 12:59:47 --

ewert в сообщении #395129 писал(а):

учитывая, что $N(2)=3$, очевидно

двузначные числа: 10 и 11... их два:)

Т.е. в Ваших терминах ответ $N_1$, а не $N$

[ewert]

paha в сообщении #395131 писал(а):

двузначные числа: 10 и 11... их два:)

Т.е. в Ваших терминах ответ $N_1$, а не $N$

ну это да, это стандартная двусмысленность в терминологии

[Circiter]

Кстати, а почему участником paha отыскивалось $F_{17}$, а не $F_{16}$? Та самая "двусмысленность в терминологии"? Просто, если с правильными начальными данными посчитать (по ewert'у) 17-ый элемент, то получится 4181, что всего на единицу больше моего первого результата. Где подвох?

P.S.: Да, я в начале, кажется, не посчитал число, состоящее из одних только единиц. :)

-- Вт янв 04, 2011 16:35:31 --

Это что-же, два ответа? Т.е., 4181 и 2584? И что топикстартер будет отвечать? Видимо, второй ответ правильнее. :)

[paha]

Circiter в сообщении #395145 писал(а):

Кстати, а почему участником paha отыскивалось $F_{17}$, а не $F_{16}$?

ewert в сообщении #395129 писал(а):

$N_0(m+1)=N_1(m);$
$N_1(m+1)=N(m)=N_0(m)+N_1(m).$

Т.е. $N_1(m+1)=N_1(m)+N_1(m-1)$, $N_1(1)=1$, $N_1(2)=2$ поэтому $N_1(m)=F_{m+1}$
А мы и искали $N_1(16)=F_{17}$

[ewert]

Circiter в сообщении #395145 писал(а):

Кстати, а почему участником paha отыскивалось $F_{17}$, а не $F_{16}$?

Лично я даже и не задумывался о том, какие номера чему соответствуют. Просто вывел последовательность Фибоначчи в табличку. Случайно вышло так, что в первой строчке оказалась $2$, во 2-й -- $3$, в 15-й -- $1597$, в 16-й -- $2584$ и в 17-й -- $4181$. И поскольку я твёрдо знаю, что $N(1)=2$ и $N(2)=3$, то стало быть, $N(16)$ -- это именно $2548$. А если б случайно в моей программке индексация оказалась вдруг сбита -- просто сделал бы на это поправку.

[Circiter]

Так, моя программулька, после того как я добавил проверку на строгую 16-тя разрядность чисел, выдает ответ 1597. :) Ужос.

[ewert]

Circiter в сообщении #395158 писал(а):

добавил проверку на строгую 16-тя разрядность чисел,

Вот это напрасно. То, что к-во $m$-разрядных чисел, начинающихся не с нуля, есть $N_1(m)\equiv N(m-1)$ -- факт тривиальный.

Кстати насчёт терминологии. Двусмысленность понятия "$m$-значное число" отчасти снимется, если договориться называть числа, начинающиеся не с нуля, именно "$m$-значными", а начинающиеся с чего угодно -- "$m$-разрядными". Но всё равно это очень зыбко, слишком многие употребляют эти два термина как синонимы. Конкретно в этой задачке: то, что к-во знаков равно именно 16 (а не 10, скажем) -- явно намекает на то, что имелись в виду просто машинные слова, т.е. что начинаться с нуля разрешено.

[mihiv]

У меня получилось число чисел,начинающихся с единицы в старшем 16-ом разряде, равно:$\sum \limits _{i=0}^8C\limits ^i_{16-i}=1597$,совпадает с результатом Circiter'a и paha.

[paha]

mihiv в сообщении #395207 писал(а):

$\sum \limits _{i=0}^8C\limits ^i_{16-i}=1597$

неужели так числа Фибоначчи вычисляются???

$\sum \limits _{i=0}^nC\limits ^i_{2n-i}=F_{2n+1}$

[mihiv]

Это что-то новое?