Поиск общих способов выбора элементов, для которых нет двух последовательных

Question

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

Я попытался сделать это с учетом повторяемости, но не смог достичь ни одного. Пожалуйста, помогите мне решить проблему.

Answer 1

После поиска в сети Я получил решение проблемы выше.

Скажите, что N элементов. Если N равно, мы можем выбрать почти N/2 элементов, так что ни один из них не является последовательным, а если N нечетно, мы можем выбрать почти (N + 1)/2 элемента. Пусть K - это максимальные элементы, которые можно выбрать.

Мы можем выбрать пункты от 1 до K.

• Для выбора одного изделия мы можем выбрать любой элемент.

• Для выбора двух элементов мы сохраняем N-2 элементов в последовательности. Круги ниже представляют элементы в последовательности. И у нас есть общее количество N-1 пробелов, начинающихся слева от первого элемента справа от последнего элемента. Пространства представлены знаком подчеркивания '_'. Если мы выберем два из любого пространства и заменим их на элемент, тогда у нас будет N элементов, и выбранные два элемента не будут последовательными, поскольку никакие два пробела не будут последовательно.

     _ o _ o _ o _ o _ o _ o _ o _ o _ o _ o _ 
  

• Для выбора р элементов, мы будем держать Н-р элементов в последовательности, которая приведет к N-р + 1 пространств. Мы можем выбрать любые p пробелы из этих N-p + 1 пробелов.

Таким образом, общие возможные пути станут
^Н С ^{+ N-1} С + ^N-2 С + ... ^{N- K + 1} C _K, который является суммой первых чисел N Фибоначчи (1,1,2,3,5, ...).
Также сумма первых чисел Фибоначчи Н Р (п + 2) - 1

Answer 2

Я думаю, вы можете сделать это, построив массив длины n с каждым местом в массиве, представляющим количество способов выбора элементов, если это место было выбрано первым. (Выбор слева направо.)

псевдопользователей код (непроверенные):

int[] list = new int[n]; 
int total = 0; 

for(int position = n-1; position >= 0; position--) 
{ 
    list[position] = 1; 
    for(int subPos = position + 2; subPos < n; subPos++) 
    { 
     list[position] += list[subPos]; 
    } 
    total += list[position]; 
} 

Объяснение:

Значение в list[i] когда закончит работу представляет собой число способов выбора элементов из строка с элементом i, являющимся левым большинством элементов, которые выбраны.

Очевидно, что существует только один способ выбора предметов, так что самый правый элемент - это самый левый элемент, который выбран. Если n = 5, то выбор может быть представлен следующим образом: 00001

Аналогичным образом, для второго самого правильного предмета существует только один способ выбрать элементы, такие как левый самый элемент: 00010.

Для третьего наиболее подходящего элемента есть один способ выбрать его, где вы выбираете этот предмет, тогда вы должны добавить количество способов выбора каждого из предметов, которые могут быть выбраны вторым (это то, что второй цикл для). Таким образом, этот пункт будет иметь: 00100 и 00101.

Четвертый наиболее правный товар: 01000, 01010, 01001.

Fith самый правый элемент (первый элемент слева): 10000, 10100, , 10010, 10001.

Таким образом, массив для п = 5 будет в конечном итоге с этими значениями: {5,3,2,1,1}

И общее бы тогда: 5 + 3 + 2 + 1 + 1 = 12

Answer 3

Его простое решение.

Скажите, что вам нужно выбрать 3 номера из первых 100 натуральных чисел, так что нет двух последовательных.

Рассмотрим первые 98 натуральных чисел, и случайным образом выбрать 3 натуральные числа (, б, с) в 98C3 способами.

Мы знаем 0 < a, b, c < 99 и |a-b|, |b-c|, |a-c| >= 1 (с , б, с разные).

let A=a+0; B=b+1; C=c+2;

Так теперь мы знаем разницу между любыми двумя из , В и С больше 1 (т.е. , B и С не могут быть последовательными числами).

И 0 < A, B, C<101. A, B и C удовлетворяет всем условиям для искомого вопроса.

Таким образом, решение равно 98 C 3.

Обобщая → P выбора элементов из N, таким образом, что нет двух подряд является (N-p-1) C p.

Answer 4

Кажется, трудно понять, как вы объяснили, почему это серия Фибоначчи. У меня есть более простой способ объяснить то же, что и ниже. Предположим, что мы выражаем число комбинаций для n элементов как T (n). Если мы не выберем первый элемент, количество комбинаций будет таким же, как количество комбинаций для оставшихся элементов n-1, то есть T (n-1). Если мы выберем первый элемент (мы не можем выбрать второй элемент, поскольку он последовательно соответствует первой позиции), то количество комбинаций будет таким же, как количество комбинаций для оставшихся n-2 элементов, которое равно T (n-2) , Следовательно, нижеследующий вывод.

T(n) = T(n-1) + T(n-2). 
T(1) = 2 (1. selected and 2. not selected) 
T(2) = 3 (1. both not selected, 2. only first selected, 3. only second selected) 

Это серия Фибоначчи и может быть вычислена по сложности времени O (n).