Блог

Главная - Вопросы по программированию - сколько двоичных последовательностей длиной n

сколько двоичных последовательностей длиной n

#math #binary #sequence

#математика #двоичный #последовательность

Вопрос:

как найти решение этой проблемы на python / java или любом другом языке:

введите описание изображения здесь

Заранее спасибо

Комментарии:

1. На самом деле это совсем не похоже на проблему программирования. Это похоже на домашнюю задачу для класса дискретной математики.

2. @JohnColeman Да, мне нужна подсказка 🙂

3. Было бы достаточно легко написать программу на Python, которая бы перебирала ответ для small n . По причинам, которые я не могу четко сформулировать, я подозреваю, что ответ как-то связан с числами Фибоначчи.

Ответ №1:

Поскольку программа не является доказательством, и вам все равно нужно это доказать, вот некоторый код Python:

 def zig_zag(seq):
    """tests if binary sequence seq satsifies zig-zag pattern"""
    for i in range(len(seq)-1):
        if (i%2 == 0 and seq[i] > seq[i 1]) or (i%2 == 1 and seq[i] < seq[i 1]):
            return False
    return True

def count_zig_zags(n):
    """counts the number of binary zig-zag patterns of length n"""
    count = 0
    for i in range(2**n):
        b = bin(i)[2:]
        if zig_zag(b): count  = 1
    return count

Например:

 >>> [count_zig_zags(n) for n in range(1,12)]
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]

Доказательство было бы с помощью сильной индукции.

Комментарии:

1. Я думаю, что для длины 3 вывод должен быть, например, 10. Почему 5 ?!

2. Есть ли какое-либо рекурсивное решение?

3. Как результат для n = 3 может быть 10? 2 ^ 3 = 8, поэтому даже без ограничений на двоичные последовательности это должно быть <= 8. 5 двоичных последовательностей, которые удовлетворяют ограничениям 000, 010, 011, 110, 111 .

4. Для рекурсивного решения обратите внимание, что допустимое решение длины n может быть расширено до допустимого решения длины n 1 либо 1, либо 2 способами, и что число, которое может быть расширено 2 способами, совпадает с числом допустимых последовательностей длины n-1 (доказательство, которое, по-видимому, требует 2 случаевв зависимости от того, является ли n четным или нечетным, не указано).