Определить число n-послед из (0, 1, 2), в которых отсутствует две подряд стоящих 1.
Не поможете решить
Определить число n-послед из (0, 1, 2), в которых отсутствует две подряд стоящих 1.
Не поможете решить
Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.
8 мая 2008 в 17:03
нет, по этой задаче не надо писать прогу просто найти количество последовательностей
8 мая 2008 в 10:03
#13 – А, ну тогда разумеется другое дело.
8 мая 2008 в 10:02
Во-первых, счет по твоей формуле имеет временную сложность
O(n^2), по моим – O(n). При больших n естественно лучше
выбирать алгоритм с меньшей временной сложностью. Тем более,
что всю таблицу d хранить не надо, достаточно двух векторов-столбцов.
Во-вторых, твоя формула не совсем правильная.
Подсчет по твоей формуле:
p(0) = 1
p(1) = 3
P(2) = 8
P(3) = 21, должно быть 22
Правильная формула:
P(0) = 1;
p(1) = 3;
p(n) = 3^n – 3^(n-2) – 2 * sum[i = 1, n - 2] {p(i – 1) * 3 ^ (n – i – 2)};
8 мая 2008 в 10:02
и d[i, c] != 3 ^ (i -1) ни в коем случае
так d[3,1]= 6, d[4, 0] = 22 и т.п.
8 мая 2008 в 10:02
*Пусть d[i, c] – количество последовательностей из {0, 1, 2},
длины i (1 <= i <= n) оканчивающихся на цифру c (c из {0, 1, 2}), не содержащих подряд двух 1.
8 мая 2008 в 8:00
Вообще-то здесь лучше подойдет элементарное знание основ комбинаторики.
d[i, c] = 3^(i-1).
Сделаю скидку на то, что ты писал пост в 7-45 утра
8 мая 2008 в 7:04
Здесь более всего подойдет ДП (динамическое программирование)
Пусть d[i, c] – количество последовательностей из {0, 1, 2},
длины i (1 <= i <= n) оканчивающихся на цифру c (c из {0, 1, 2}), не содержащих подряд двух 1.
Для последовательностей 1-й длины все очевидно
d[1, 0] = 1;
d[1, 1] = 1;
d[1, 2] = 1;
Для последовательностей длины i
i = 2..n
Каждая последовательность длины i, оканчивающаяся на 0 – это
последовательность длины i – 1, оканч. на 0, 1 или 2, к которой
приписали 0.
d[i, 0] = d[i - 1, 0] + d[i - 1, 1] + d[i - 1, 2];
Каждая последовательность длины i, оканчивающаяся на 1 – это
последовательность длины i – 1, оканч. на 0 или 2, к которой
приписали 1.
d[i, 1] = d[i - 1, 0] + d[i - 1, 2];
Каждая последовательность длины i, оканчивающаяся на 2 – это
последовательность длины i – 1, оканч. на 0, 1 или 2, к которой
приписали 2.
d[i, 2] = d[i - 1, 0] + d[i - 1, 1] + d[i - 1, 2];
Результат – сумма:
result = d[n, 0] + d[n, 1] + d[n, 2]
8 мая 2008 в 7:04
Естественно формуло можно прооптимизить объединива d[i, 0] и d[i, 2]
8 мая 2008 в 1:04
Тогда михаил число последовательностей счётно)
7 мая 2008 в 23:05
я так понимаю послед любой длины
7 мая 2008 в 23:01
Достаточно посчитать число n-последовательностей из (0,1,2), в которых ПРИСУТСТВУЕТ 2 единицы подряд.
Все такие последовательности имеют вид A11B, где в A нет двух единиц подряд и A не оканчивается на 1, а В произвольно.
Пусть p(n) – число n-последовательностей где нет двух единиц подряд.
Пусть q(n) = число всех n-последовательностей.
Тогда p(n) = сумма по i=0..n-2 { p(i) * q(n-i-2) }, а q(n) = 3^n.
Не знаю, можно ли эту формулу упростить. Может, и можно, но мне лень.
7 мая 2008 в 23:01
Ой. Точнее, не p(n) = сумма…., а q(n)-p(n) = сумма.
7 мая 2008 в 22:04
10001, 10002 считается?
7 мая 2008 в 21:04
какая длина последовательности?