Просмотр полной версии : Последовательности
Всем привет!
Подскажите как вывести количество последовательностей длины N из нулей и единиц, не содержащих двух единиц подряд?
откуда и куда вывести? если из программы на STDOUT, то, обычно, оператор print помогает
Всем привет!
Подскажите как вывести количество последовательностей длины N из нулей и единиц, не содержащих двух единиц подряд?
Ну если в лоб решать - то просто перебирай всевозможные комбинации нулей и единиц, и считай тольке те, у которых нет двух единиц подряд...
млин, это же легко...
короче, заведем двухмерный массив 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
теперь видна сразу закономерность распределения подходящих чисел
и считатсья будет примерно так
const N = 5 ;
var
x : integer;
G : integer;
LastG : integer;
Tmp : integer;
begin
LastG := 1;
G := 2;
for x := 1 to N do
begin
Tmp := G;
G := G + LastG;
LastG := Tmp;
end;
ShowMessage(inttostr(G));
end;
][yZ предложил естественное динамическое решение
я сказал общую формулу на его основании (хотя вообще это очевидно по другой причине: r_n = r_n-1 + r_n-2, так как мы могли взять любую последовательность длины n-1 и дописать "0" и любую длины n-2 и дописать "01")
slesh - а ты изварщенец, батенька :))))
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/c1/7d5864024d452b2962ae2fb4a39939c1.jpeg (http://fastpic.ru/view/1/2010/0112/7d5864024d452b2962ae2fb4a39939c1.jpeg.html)
маткадовский файл (http://www.sendspace.com/file/b88b4f)
k(n)=k(n-2)+k(n-1)+2^(n-2) - это неверный ответ, прости :)
k(n)=k(n-2)+k(n-1)+2^(n-2) - это неверный ответ, прости :)
Тем самым количество чисел не содержащих '11' для разрядности n равно: 2^(n) - k(n)=2^(n)-k(n-2)-k(n-1)-2^(n-2)
перечитай, у меня все верно, там не учитываеться 0 т.е. начинается с 1 если что.
Млять, lukmus нахуя ты залил картинку на этот ёбаный обменник. // сори за мат.
Зайдя туда появилась парочка назойливых банеров.
А после comodo порадывал меня тем что опера запустила программу, а программка запустила другую программку и так далее.
И как назло комод стол в режиме обучения по этому с радость пропустил всё.
------------
Врубил комод на полную. Сделал ребут. И он заорал на прогу, которая по виду блокала экран )
-----------
Зато слил часть связки, и все exe. А там их 4 штуки )
Античат решает задачку оО
я в шоке :D
// s - pointer to block
// l - length of block
//
// ret: 0 - no serial '1' detected
// x - idx of first '1' (1-base)
int check_fragment(char *s, int l)
{
for(int i=0; i< l-1; i++)
if(s[i]=='1' && s[i+1]=='1')
return i+1; // avoid zerobase offset
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *s01 = "1110101010"; // source 0/1
const int block_len = 5; // N
int slen = strlen(s01);
int num_frags = 0, temp;
for(int i=0; i< slen; ){
if(strlen(&s01[i])<block_len)break;
temp = check_fragment(&s01[i], block_len);
if(temp==0){
i+= block_len;
num_frags++;
continue;
}
i+=temp;
}
printf("%d", num_frags);
return _getch();
}
те ес я правильно понял то в данном варианте
char *s01 = "1110101010"; // source 0/1
const int block_len = 5; // N
вывод должен быть равен 1, как он и есть собсна.
...ес прально понял =)
примерной такой вывод (N=5):
0000000000 - 2
1111111111 - 0
0000110000 - 2
1100000000 - 1
0000000011 - 1
1111110000 - 1
1101010110 - 1
Млять, lukmus нахуя ты залил картинку на этот ёбаный обменник. // сори за мат.
Зайдя туда появилась парочка назойливых банеров.
А после comodo порадывал меня тем что опера запустила программу, а программка запустила другую программку и так далее.
И как назло комод стол в режиме обучения по этому с радость пропустил всё.
------------
Врубил комод на полную. Сделал ребут. И он заорал на прогу, которая по виду блокала экран )
-----------
Зато слил часть связки, и все exe. А там их 4 штуки )
извини, перезалил, просто вчера какой-то гал был и картинка покрайней мере у меня не отображалась с другого хостинга
Я прочитал вот это:
>>k(x) - функция количества чисел содержащих '11'
>>k(n)=k(n-2)+k(n-1)+2^(n-2)
это (edit: оказывается)верно.
Обозначим s(n) количество чисел разрядности ровно n, содержащих 11.
Такие числа можно получить двумя способами:
'10' . число, содержащее '11' длины (n-2) (получили k(n-2) чисел)
'11' . любое число длины (n-2) (и ещё 2^(n-2))
( . - конкатенация строк)
Значит, s(n) = k(n-2)+2^(n-2).
Твоё k(n) = сумма по i=1..n s(i) = сумма по i=1..(n-1) s(i) + s(n)= k(n-1) + k(n-2) + 2^(n-2)
твой ответ = этот
хорошо :) У меня был баг :)
Обозначим s(n) количество чисел разрядности ровно n, содержащих 11.
Такие числа можно получить двумя способами:
'10' . число, содержащее '11' длины (n-2) (получили s(n-2) чисел)
'11' . любое число длины (n-2) (и ещё 2^(n-2))
( . - конкатенация строк)
Значит, s(n) = s(n-2)+2^(n-2).
а с чего ты взял что твоя формула и выводы верны, что составляешь тождество с моей функцией. По твоей формуле:
n=4 => s(4)=s(2)+2^2=1+4=5, хотя для разрядности 4 существуют следующие числа с '11':
11
110
111
1011
1100
1101
1110
1111
т.е. их 8
s(5)=s(3)+2^3=3+8=11. хотя их 19:
11
110
111
1011
1100
1101
1110
1111
10011
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
а по крайней мере одна из ошибок твоей формулы, такая что в варианте:
'11' . любое число длины (n-2) (и ещё 2^(n-2))
например для разрядности 3 никогда не получиться числа 112=310, минимальное будет число 110 т.к все числа разрядности n-2=3-1=1 это: 1 и 0, но там нет пустого множества.
ты меня не понял - я считаю функцию s(n) как ровно n-разрядное число.
Но да, согласен, у меня там бага в строчке
>>'10' . число, содержащее '11' длины (n-2) (получили s(n-2) чисел)
правильно, конечно же,
>>'10' . число, содержащее '11' длины (n-2) (получили k(n-2) чисел)
так как я забыл, что мы не считаем числа, начинающиеся с 1.
Так что правильный походу у тебя ответ, хоть ты его и не аргументировал :)
а по крайней мере одна из ошибок твоей формулы, такая что в варианте:
тут нет ошибки
vBulletin® v3.8.14, Copyright ©2000-2026, vBulletin Solutions, Inc. Перевод: zCarot