singlepost

Комбинаторика << На главную или назад  

Определить число n-послед из (0, 1, 2), в которых отсутствует две подряд стоящих 1.
Не поможете решить

14 ответов в теме “Комбинаторика”

Страницы: [1] 2 »

  1. 1
    Bullish Market ответил:

    какая длина последовательности?

  2. 2
    Иван Шопин ответил:

    10001, 10002 считается?

  3. 3
    Жека Кирпичев ответил:

    Достаточно посчитать число 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.
    Не знаю, можно ли эту формулу упростить. Может, и можно, но мне лень.

  4. 4
    Жека Кирпичев ответил:

    Ой. Точнее, не p(n) = сумма…., а q(n)-p(n) = сумма.

  5. 5
    Михаил Ганеев ответил:

    я так понимаю послед любой длины

  6. 6
    Bullish Market ответил:

    Тогда михаил число последовательностей счётно)

  7. 7
    Петр Полежаев ответил:

    Здесь более всего подойдет ДП (динамическое программирование)

    Пусть 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. 8
    Петр Полежаев ответил:

    Естественно формуло можно прооптимизить объединива d[i, 0] и d[i, 2]

  9. 9
    Жека Кирпичев ответил:

    Вообще-то здесь лучше подойдет элементарное знание основ комбинаторики.
    d[i, c] = 3^(i-1).

    Сделаю скидку на то, что ты писал пост в 7-45 утра ;)

  10. 10
    Петр Полежаев ответил:

    Во-первых, счет по твоей формуле имеет временную сложность
    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)};

Страницы: [1] 2 »

Ответить

Пожалуйста, зарегистрируйтесь для комментирования.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.