бинарная запись не содержит трех одинаковых бит подряд

[Xenia1996]

Сколько существует натуральных чисел, не больших 1023, бинарная запись которых не содержит трех одинаковых бит подряд?


Я рассуждала так:

Пусть $a_{n}$ - количество n - битных чисел, удовлетворяющих условию задачи.
Предположим, мы уже имеем n - битное число, удовлетворяющее условию задачи. Добавим ещё один бит.
Если добавляемый бит не равен последнему биту, его всегда можно добавить - имеем количество вариантов, равное $a_{n}$. Если же равен, значит не должны быть равны биты n и $n-1$. Стало быть, $a_{n+1}=a_{n}+a_{n-1}$. То бишь мы получаем последовательность Фибоначчи, и тогда ответ на задачу будет 231. Но правильный ответ, почему-то, оказался 228.

[Xaositect]

Ну так начальные значения же не такие, как у Фибоначчи

[Xenia1996]

Xaositect в сообщении #379576 писал(а):

Ну так начальные значения же не такие, как у Фибоначчи

И?

У Вас вышло 228?

[ИСН]

За рассуждениями не следил. Проверил перебором на компе - вышло 231.

[Xenia1996]

ИСН в сообщении #379579 писал(а):

За рассуждениями не следил. Проверил перебором на компе - вышло 231.

А кого тут можно попросить за рассуждениями последить?

[ИСН]

А смысл? Скорее всего, Вы правы, а книга врёт.
Ну вот начало выдачи:

 1   1
 2   10
 3   11
 4   100
 5   101
 6   110
 7   1001
 8   1010
 9   1011
10   1100
11   1101
12   10010
13   10011
14   10100
15   10101
16   10110
17   11001
18   11010
19   11011
20   100100
...

Действительно, числа Фибоначчи.

[Xenia1996]

ИСН в сообщении #379585 писал(а):

А смысл? Скорее всего, Вы правы, а книга врёт.

О боже! Вы на ассемблере писали???

И потом, на олимпиаде мне бы не зачли простой перебор (даже, умей я перебирать со скоростью компа).

[Dan B-Yallay]

Xenia1996 писал(а):

О боже! Вы на ассемблере писали???

Почему Вы думаете что на ассемблере?

[ИСН]

Xenia1996, это не программа, а то, что она выдаёт.

[MrDindows]

Xenia1996 в сообщении #379588 писал(а):

ИСН в сообщении #379585 писал(а):

А смысл? Скорее всего, Вы правы, а книга врёт.

О боже! Вы на ассемблере писали???

И потом, на олимпиаде мне бы не зачли простой перебор (даже, умей я перебирать со скоростью компа).

Если перебор выполнен полностью правильно, обязаны зачесть, так как задача решена. Но если будет хоть одна ошибка, могут ноль балов поставить)

[Xenia1996]

Dan B-Yallay в сообщении #379644 писал(а):

Xenia1996 писал(а):

О боже! Вы на ассемблере писали???

Почему Вы думаете что на ассемблере?

Уже не думаю
Хотя программы, работающие с битами, удобнее всего на ассемблере писать...

[ИСН]

Я об этом думал в терминах работы со строками, поэтому - Перл.

foreach(1..1023){
   $_=sprintf "%b",$_;
   print ++$n, "   $_\n" if !/(111|000)/;
}

В битах, вероятно, было бы ещё круче, но это уж - - -

[lim0n]

Xenia1996 в сообщении #379570 писал(а):

... тогда ответ на задачу будет 231. Но правильный ответ, почему-то, оказался 228.

Возможно в "правильном" ответе не учитываются числа $1, 2, 3$, т.к. их очевидно нельзя представить тремя битами.

[Gortaur]

Возможно - но это было бы странно, потому как то в условии об этом ни слова - и очевидным это может быть только для автора задачи. С другой стороны если решение приведено полное, то думаю на проверке могут заметить этот факт и не снять баллов даже в случае перебора, если будут приведены все 231 число.
Как тут оффтоп сделать, а то это не относится напрямую к сабжу?

[bot]

Вообще-то правильный ответ 178.
Надо считать все начинающиеся с нуля (начинающихся с 1 столько же) для них получится последовательность Фибоначчи, а требуемое число вдвое больше.