Всем привет! Подскажите как вывести количество последовательностей длины 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 теперь видна сразу закономерность распределения подходящих чисел и считатсья будет примерно так Code: 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 - а ты изварщенец, батенька )))
А теперь будем рассуждать логически-математически: 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) маткадовский файл
Млять, lukmus нахуя ты залил картинку на этот ёбаный обменник. // сори за мат. Зайдя туда появилась парочка назойливых банеров. А после comodo порадывал меня тем что опера запустила программу, а программка запустила другую программку и так далее. И как назло комод стол в режиме обучения по этому с радость пропустил всё. ------------ Врубил комод на полную. Сделал ребут. И он заорал на прогу, которая по виду блокала экран ) ----------- Зато слил часть связки, и все exe. А там их 4 штуки )
Code: // 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
извини, перезалил, просто вчера какой-то гал был и картинка покрайней мере у меня не отображалась с другого хостинга
Я прочитал вот это: >>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) твой ответ = этот хорошо У меня был баг
а с чего ты взял что твоя формула и выводы верны, что составляешь тождество с моей функцией. По твоей формуле: 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 а по крайней мере одна из ошибок твоей формулы, такая что в варианте: например для разрядности 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. Так что правильный походу у тебя ответ, хоть ты его и не аргументировал тут нет ошибки