2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 бинарная запись не содержит трех одинаковых бит подряд
Сообщение23.11.2010, 18:15 
Сколько существует натуральных чисел, не больших 1023, бинарная запись которых не содержит трех одинаковых бит подряд?


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

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 18:32 
Аватара пользователя
Ну так начальные значения же не такие, как у Фибоначчи

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 18:38 
Xaositect в сообщении #379576 писал(а):
Ну так начальные значения же не такие, как у Фибоначчи

И?

У Вас вышло 228?

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 18:43 
Аватара пользователя
За рассуждениями не следил. Проверил перебором на компе - вышло 231.

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 18:47 
ИСН в сообщении #379579 писал(а):
За рассуждениями не следил. Проверил перебором на компе - вышло 231.

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 18:53 
Аватара пользователя
А смысл? Скорее всего, Вы правы, а книга врёт.
Ну вот начало выдачи:
Код:
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
...

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 18:58 
ИСН в сообщении #379585 писал(а):
А смысл? Скорее всего, Вы правы, а книга врёт.

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

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 21:00 
Аватара пользователя
Xenia1996 писал(а):
О боже! Вы на ассемблере писали???


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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 21:03 
Аватара пользователя
Xenia1996, это не программа, :lol: а то, что она выдаёт.

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение23.11.2010, 22:22 
Xenia1996 в сообщении #379588 писал(а):
ИСН в сообщении #379585 писал(а):
А смысл? Скорее всего, Вы правы, а книга врёт.

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

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

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение24.11.2010, 10:27 
Dan B-Yallay в сообщении #379644 писал(а):
Xenia1996 писал(а):
О боже! Вы на ассемблере писали???


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

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение24.11.2010, 11:05 
Аватара пользователя
Я об этом думал в терминах работы со строками, поэтому - Перл.
Код:
foreach(1..1023){
   $_=sprintf "%b",$_;
   print ++$n, "   $_\n" if !/(111|000)/;
}

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

 
 
 
 Re: Три бита подряд (не удается найти ошибку в рассуждении)
Сообщение24.11.2010, 11:31 
Xenia1996 в сообщении #379570 писал(а):
... тогда ответ на задачу будет 231. Но правильный ответ, почему-то, оказался 228.
Возможно в "правильном" ответе не учитываются числа $1, 2, 3$, т.к. их очевидно нельзя представить тремя битами.

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

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group