Последовательности
 

Всем привет!
Подскажите как вывести количество последовательностей длины N из нулей и единиц, не содержащих двух единиц подряд?

откуда и куда вывести? если из программы на STDOUT, то, обычно, оператор print помогает

Ну если в лоб решать - то просто перебирай всевозможные комбинации нулей и единиц, и считай тольке те, у которых нет двух единиц подряд...

млин, это же легко...
короче, заведем двухмерный массив a[i, j], где i - длина последовательности, j - на что оканчивается (0 или 1)

a[1, 1] = 1
a[1, 0] = 1

потом, к нолику мы можем дописать или 0 или 1, т. е. a[i, 0] = a[i - 1, 0] + a[i - 1, 1]
к единице только нолик, т.е. a[i, 1] = a[i - 1, 0]
результат в a[n, 0] + a[n, 1]

как-то так

][yZ, если ещё соптимайзить, то можно заметить, что две твои последовательности имеют вид:
a_n = a_n-1 + b_n-1=a_n-1 + a_n-2
b_n = a_n-1

a_0=1; a_1=1 => a_n = n-1-ое число Фибоначчи F_n-1,
ответ: a_n-1+F_n-1 = F_n-1 + F_n-2 = F_n.
/*с индексами мог напутать, но вроде правда*/

НУ я хз число фибоначи или когонить другова, чисто эксперементально рашил провести собственный опыт.

Искать через перебор в данном случае очень не рационально.
В большинстве случаев, там где есть перебор всех возможных комбинаций
На конечном множестве, то такие вещи почти всегда имеют формулы.
Или их можно вывести опытным путем.

Вот небольшие рассуждения:

Формула для полного числа комбинаций:
K= 2 ^ N.
И так.
если N = 1 то K = 2 ^ 1 = 2
0
1
Непоходят 0


если N = 2 то K = 2 ^ 2 = 4

00
01
10
11
Из низ видно что тока 1 неподходит.

Если N = 3 то K = 2 ^ 3 = 8
000
001
010
011
100
101
110
111
Из них 3 неподходит


Если N = 4 то K = 2 ^ 4 = 16
0000
0001
0010
0011
0100
0101
0110
0111

1000
1001
1010
1011
1100
1101
1110
1111
Из них 8 неподходит.

Если N = 5 то K = 2 ^ 5 = 32

00000
00001
00010
00011
00100
00101
00110
00111

01000
01001
01010
01011
01100
01101
01110
01111

10000
10001
10010
10011
10100
10101
10110
10111

11000
11001
11010
11011
11100
11101
11110
11111

Из них 19 не неподходит

ВОт простые вычисления. далее Строим таблицу.
N = длинна ряда
K = число комбинаций
G = Число подходящих вариант
B = Число не подходящих вариантов


0) N0 = 1 K0 = 2 G0 = 2 B0 = 0
1) N1 = 2 K1 = 4 G1 = 3 B1 = 1
2) N2 = 3 K2 = 8 G2 = 5 B2 = 3
3) N3 = 4 K3 = 16 G3 = 8 B3 = 8
4) N4 = 5 K4 = 32 G4 = 13 B4 = 19

Теперь простейшим поиском закономерности можно найти вот что:

G0 = 2
G1 = G0 + 1
G2 = G1 + G0
G3 = G2 + G1
G4 = G3 + G2

теперь видна сразу закономерность распределения подходящих чисел
и считатсья будет примерно так

][yZ предложил естественное динамическое решение
я сказал общую формулу на его основании (хотя вообще это очевидно по другой причине: r_n = r_n-1 + r_n-2, так как мы могли взять любую последовательность длины n-1 и дописать "0" и любую длины n-2 и дописать "01")
slesh - а ты изварщенец, батенька :))))

Почему извращенец ?
Если есть аналитическое решение - то конечно его нужно использовать :)

А теперь будем рассуждать логически-математически:
k(x) - функция количества чисел содержащих '11'
k(0)=0
k(1)=0
k(2)=1
11
k(3)=3
11 - число пришедшее от предыдущей разрядности
110 - числа полученный добавлением в начало '11' и перебором
111 - остальных свободных бит т.е. вида 11x
k(4)= 8
11
110
111
1011
1100
1101
1110
1111
С первыми 3-мя числами все ясно, они пришли от предыдущей разрядности. Последние четыре, то же ясны, они вида 11xx.
И остаеться одно интересное число - 1011, будем условно называть такие числа - числа Лакмусачи (Lukmusacci) ))).

k(5)=19
Количество складываеться из:
-8 чисел от предыдущей разрядности
-8 чисел вида 11xxx
-3 числа Лакмусачи

k(6)=43
Количество складываеться из:
-19 чисел от предыдущей разрядности
-16 чисел вида 11xxxx
-8 чисел Лакмусачи

Пронзительный читатель уже догадался к чему я виду:
количество чисел Лакмусачи для разрядности n равно k(n-2) , посмотрите внимательно Лакмусачи для 6 равно количеству чисел содержащих '11' для 4.

В итоге мы можем вывести эмпирическую функцию k(n):
k(n)=k(n-2)+k(n-1)+2^(n-2), где k(n-2) - числа Лакмусачи,
k(n-1) - числа пришедшие от прошлой разрядности, 2^(n-2) - числа вида 11x.
Тем самым количество чисел не содержащих '11' для разрядности n равно: 2^(n) - k(n)=2^(n)-k(n-2)-k(n-1)-2^(n-2)

Спомощью не сложных математических операций, можно апроксимировать эту функцию, не смотря на то что она дискретная.
Моего компьютера хватила только на апроксимацию многочленом 13-ой степени.
Тем самым получим не рекурсивную функцию вида y(x)=F(y(x-a1),y(x-a2),...,y(x-an)), полноценную функцию y=f(x)

http://i1.fastpic.ru/thumb/2010/0112...4a39939c1.jpeg

маткадовский файл