Объясните, пожалуйста, устное решение задачи

← →
Pdkle (2007-09-17 15:40) [0]

Сколько существует последовательностей из 9 бит в которых 2 единицы не стоят вместе?
Заранее благодарен!

← →
Anatoly Podgoretsky © (2007-09-17 15:47) [1]

> Pdkle (17.09.2007 15:40:00) [0]

Легче посчитать где стоят вместе, в крайнем случае можно на бумажке

← →
Kerk © (2007-09-17 15:48) [2]

Судя по всему 64

← →
tesseract © (2007-09-17 15:50) [3]

> последовательностей из 9 бит

Последовательностей ? имееться в виду

000000001
000000010
000000011 <- уже ерунда.
000000100
000000101
000000111 <- опять ерунда.

?

← →
DVM © (2007-09-17 16:05) [4]

> в которых 2 единицы не стоят вместе?

а единиц всего 2 или и 3 может быть?

← →
MBo © (2007-09-17 16:08) [5]

проще всего рекурсивное решение. Обозначим P(N) количество удовлетворяющих условию последоавтельностей длиной N
Тогда P(9) = P(8) + P(7)
Смысл формулы - сумма количеств последовательностей, в которой на 9 месте стоит "0", значит, следующая единица может идти с 8 места, и количеств последовательностей, где на 9 месте стоит "1", значит, след. единица может быть только с 7 места.
аналогично разворачиваем P(8) и P(7) и так далее.
Методом внимательного всматривания в формулу P(N) = P(N-1) + P(N-2) можно вспомнить некоего Фибоначчи...

← →
Alien1769 © (2007-09-17 16:10) [6]

> Kerk © (17.09.07 15:48) [2]
> Судя по всему 64

Просили не ответ, а по-буквам для школьников-студентов. Почему и как !

← →
Alarm © (2007-09-17 16:11) [7]

>DVM © (17.09.07 16:05) [4]
Думаю, что не более пяти. Иначе тесно:)

← →
tesseract © (2007-09-17 16:31) [8]

> Думаю, что не более пяти. Иначе тесно:)

Что вы, гораздо больше.

← →
Pdkle (2007-09-17 16:36) [9]

На 9 месте в последовательности стоит 34. А реальный ответ - 89.
В чем проблема?

← →
ТТ (2007-09-17 16:52) [10]

такое решение принимается? :)
var
a1,a2,a3,a4,a5,a6,a7,a8,a9:byte;
k:integer;
s:string;
begin
k:=0;
for a1:=0 to 1 do
for a2:=0 to 1 do
for a3:=0 to 1 do
for a4:=0 to 1 do
for a5:=0 to 1 do
for a6:=0 to 1 do
for a7:=0 to 1 do
for a8:=0 to 1 do
for a9:=0 to 1 do begin
s:=inttostr(a1)+inttostr(a2)+inttostr(a3)+
inttostr(a4)+inttostr(a5)+inttostr(a6)+
inttostr(a7)+inttostr(a8)+inttostr(a9);
if pos("11",s)=0 then begin
inc(k);
memo1.Lines.Add(s);
end;
end;
memo1.Lines.Add(inttostr(k));

000000000
000000001
000000010
000000100
000000101
000001000
000001001
000001010
000010000
000010001
000010010
000010100
000010101
000100000
000100001
000100010
000100100
000100101
000101000
000101001
000101010
001000000
001000001
001000010
001000100
001000101
001001000
001001001
001001010
001010000
001010001
001010010
001010100
001010101
010000000
010000001
010000010
010000100
010000101
010001000
010001001
010001010
010010000
010010001
010010010
010010100
010010101
010100000
010100001
010100010
010100100
010100101
010101000
010101001
010101010
100000000
100000001
100000010
100000100
100000101
100001000
100001001
100001010
100010000
100010001
100010010
100010100
100010101
100100000
100100001
100100010
100100100
100100101
100101000
100101001
100101010
101000000
101000001
101000010
101000100
101000101
101001000
101001001
101001010
101010000
101010001
101010010
101010100
101010101
89

← →
DVM © (2007-09-17 16:55) [11]

> ТТ (17.09.07 16:52) [10]

а эта, если бы знаков было, скажем 1000?

← →
ТТ (2007-09-17 16:58) [12]

это очень долго объяснять пришлось бы

>а 9 месте в последовательности стоит 34. А реальный ответ - 89.
В чем проблема?
в неправильно выбранном условии завершения рекурсии и соответстенно сдвиге последовательности
P(1) = 2 (0 и 1)
P(2) = 3 (00 01 10)

P(N) = Fib(N+2) (если ряд Fib начинать с 1,1...)

> Объясните, пожалуйста, устное решение задачи

Объясняю:
Тупой перебор вариантов. Не так уж их и много...

> Тупой перебор вариантов. Не так уж их и много...

всего 512

> > Тупой перебор вариантов. Не так уж их и много...
>
> всего 512

посчитайте для 10^10 бит..

Объясните, пожалуйста, устное решение задачи Найти похожие ветки