Количество мероприятий

голоса
4

Предположим , что мы имеем п элементов, а 1 , 2 , ..., п , расположенных по окружности. То есть, 2 находится в пределах от более 1 и в 3 , 3 находится между в 2 и в 4 , п между в п -1 и в 1 , и так далее.

Каждый элемент может принимать значение от 1 или 0. Два устройства различны , если имеются соответствующие я «s , чьи значения различаются. Например, при п = 3, (1, 0, 0) и (0, 1, 0) различные механизмы, даже если они могут быть изоморфными при вращении или отражении.

Поскольку существует N элементов, каждый из которых может принимать два значения, общее количество механизмов равно 2 н .

Вот вопрос:

Сколько договоренности возможны, так что никакие два соседних элемента оба не имеют значение 1? Если это помогает, рассматривать только случаи , когда п > 3.

Я спрашиваю здесь по нескольким причинам:

  1. Этот вопрос возник, когда я решал проблему программирования
  2. Похоже, проблема может извлечь выгоду из булевой логики / битой арифметики
  3. Может быть, нет замкнутого решения.
Задан 10/12/2008 в 00:41
источник пользователем
На других языках...                            


4 ответов

голоса
10

Давайте сначала задать вопрос «сколько 0-1 последовательность длиной п есть без какого-либо два последовательных 1s?» Пусть ответ будет А (п). Мы имеем А (0) = 1 (пустая последовательность), А (1) = 2 ( "0" и "1"), и А (2) = 3 ( "00", "01" и "10", но не "11").

Для того, чтобы сделать его легче написать повторения, мы будем вычислять A (N) в виде суммы двух чисел:
B (N), число таких последовательностей , которые заканчиваются на 0, и
С (п), число таких последовательности , которые заканчиваются на 1.

Тогда В (п) = А (п-1) (взять любую такую последовательность длины п-1, и присоединять 0)
и С (п) = В (п-1) (потому что , если у Вас есть 1 в положении п , вам необходимо иметь 0 при п-1.)
Это дает (п) = в (п) + С (п) = А (п-1) + в (п-1) = А (п-1) + А (п-2). К настоящему времени это должно быть знакомо :-)

А (п) есть просто число Фибоначчи F п + 2 , где последовательность Фибоначчи определяется
F 0 = 0, F 1 = 1, а Р п + 2 = Р п + 1 + Ж п при п ≥ 0.

Теперь для вашего вопроса. Мы подсчитаем количество соглашений с 1 = 0 и 1 = 1 отдельно. Для первых, A 2 ... A п может быть любой последовательности на всех (без последовательных 1s), так что число А (п-1) = Р п + 1 . В последнем случае , мы должны иметь 2 = 0, а затем 3 ... п является любая последовательность, без последовательных 1s , что заканчивается с 0 , т.е. В (п-2) = А (п-3) = F N- 1 .

Таким образом , ответ F п + 1 + F п-1 .

На самом деле, мы можем пойти еще дальше , чем этот ответ. Обратите внимание , что если вы звоните ответ как
G (п) = F п + 1 + F п-1 , то
G (п + 1) = F п + 2 + F п и
G (п + 2) = F п + 3 + Ж п + 1 , так что даже G (п) удовлетворяет тому же , как повторение последовательности Фибоначчи! [ На самом деле, любая линейная комбинация Фибоначчи-подобных последовательностей будет удовлетворять тому же повторения, так что это не все , что удивительно.] Таким образом , еще один способ , чтобы вычислить ответы были бы с помощью:
G (2) = 3
С (3) = 4
G ( п) = G (п-1) + G (п-2) для n≥4.

И теперь вы можете также использовать замкнутую форму F п = (α пп ) / (α-Р) (где α и β являются (1 & plusmn ; √5) / 2, то корни х 2 -x-1 = 0), чтобы получить
G (N) = ((1 + √5) / 2) п + ((1-√5) / 2) п .
[Вы можете игнорировать второй член , потому что очень близко к 0 при большом п, на самом деле G (п) является ближайшим к целому числу ((1 + √5) / 2) п для всех n≥2.]

Ответил 10/12/2008 в 01:00
источник пользователем

голоса
1

Я решил взломать до небольшого скрипта, чтобы попробовать его:

#!/usr/bin/python
import sys

# thx google 
bstr_pos = lambda n: n>0 and bstr_pos(n>>1)+str(n&1) or ""

def arrangements(n):
    count = 0
    for v in range(0, pow(2,n)-1):
        bin = bstr_pos(v).rjust(n, '0')
        if not ( bin.find("11")!=-1 or ( bin[0]=='1' and bin[-1]=='1' ) ):
            count += 1
            print bin
    print "Total = " + str(count)

arrangements(int(sys.argv[1]))

Запуск этого на 5, дал мне в общей сложности 11 возможностей с 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

PS - Простите, не () в коде выше.

Ответил 10/12/2008 в 01:14
источник пользователем

голоса
0

Эта проблема очень похожа на Цекендорф представления . Я не могу найти очевидный способ применить теорему Цекендорфа, из - за округлости ограничения, но числа Фибоначчи, очевидно , очень распространены в этой проблеме.

Ответил 10/12/2008 в 01:38
источник пользователем

голоса
0

Бросив мой наивный сценарий в миксе. Много возможностей для кэширования частичных результатов, но он бежал достаточно быстро для малого п, что я не удосужился.

def arcCombinations(n, lastDigitMustBeZero):
    """Takes the length of the remaining arc of the circle, and computes
       the number of legal combinations.
       The last digit may be restricted to 0 (because the first digit is a 1)"""

    if n == 1: 
        if lastDigitMustBeZero:
            return 1 # only legal answer is 0
        else:
            return 2 # could be 1 or 0.
    elif n == 2:
        if lastDigitMustBeZero:
            return 2 # could be 00 or 10
        else:
            return 3 # could be 10, 01 or 00
    else:
        # Could be a 1, in which case next item is a zero.
        return (
            arcCombinations(n-2, lastDigitMustBeZero) # If it starts 10
            + arcCombinations(n-1, lastDigitMustBeZero) # If it starts 0
            )

def circleCombinations(n):
    """Computes the number of legal combinations for a given circle size."""

    # Handle case where it starts with 0 or with 1.
    total = (
            arcCombinations(n-1,True) # Number of combinations where first digit is a 1.
            +
            arcCombinations(n-1,False) # Number of combinations where first digit is a 0.
        )
    return total


print circleCombinations(13)
Ответил 10/12/2008 в 01:16
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more