Количество способов приема конфет `N`

Question

У меня проблема, и я не знаю, как я могу ее решить. Вы знаете кого-то формулу, алгоритм или тип таких проблем?

У меня есть только номер N, N конфеты, и мне нужно подсчитать количество способов приема N конфеты, но кроме первой конфеты приняты, конфеты должны быть принято рядом с одной из предыдущих конфет, принятых ранее. Например, если N = 3 существует 4 способа приема:

• Принимая сначала число конфет 1; затем конфеты 2, 3.
• Принимая сначала конфеты номер 2; затем 1, 3.
• Принимая сначала число конфет 2; затем 3, 1.
• Принимая сначала леденец номер 3; затем конфеты 2, 1.

Answer 1

Число способов для n конфет является сумма n-1 й строки pascal's triangle.

Answer 2

Посмотрите на рисунок:

number of candies 
1 2 3 4 
1 12 123 1234 
    21 213 2134 
     231 2314 
     321 2341 
      3214 
      3241 
      3421 
      4321 
1 2 4 8 
total ways 

это напоминает вам о чем-то ли?

Answer 3

Другая реализация, вероятно, более полезная в теории:

Учитывая 1-индексированный массив C леденца мраморов (1 для еще не принято и 0 для принято, все, начиная с 1) и отправной точкой N:

1. Если N отрицательный, ноль или больший размер C, конец без каких-либо действий.
2. Если C[N] 0, конец без каких-либо действий.
3. Если C[N] равно 1, установите его в 0, добавьте 1 к счету возможных путей, затем отметьте C[N-1] и C[N+1] против этого алгоритма.

Просто повторите этот алгоритм для каждого действительного индекса в C. Кроме того, убедитесь, что каждая рекурсия имеет копию C, а не оригинал C, но все они разделяют общее количество путей.

Пошаговое первой части вашего примера:

1. C[1] является 1, поэтому мы устанавливаем его в 0, добавьте 1, и проверьте C[0] и C[2].
2. 0 - 0, поэтому мы останавливаем эту рекурсию.
3. C[2] 1, поэтому мы устанавливаем его на 0 и проверяем C[1] и C[3].
4. C[1] 0.
5. C[3] is 1, so we set it to 0 and check С [2] and С [4] `.
6. C[2] is 0.
7. -больше, чем 3.

Повторите для N=2 и N=3, и больше всего цикл массивов.

Answer 4

Если вы сначала берете конфету, то выбирают (n-1, k-1) способы выбора остального (где select (n, k) - биномиальный коэффициент nCk). Это потому, что после первого вам нужно либо взять самую левую конфету слева, либо левую самую левую конфету справа от k, и есть (k-1) конфеты слева от k.

Суммирование по k дает вам все возможные пути с учетом первого выбора: sum (k = 1 ... n) выбрать (n-1, k-1).

Поскольку select (n-1, k-1) - это количество способов выбора элементов k-1 из n-1 элементов, эта сумма равна количеству способов выбора любого количества элементов из n- 1 шт. Это 2^(n-1).

Answer 5

Скажем, сначала мы принимаем конфеты i-th. Затем у нас есть i - 1 конфеты слева и N - i направо. Каждая следующая леденец - самая правая из левой части или самая левая из правой части. Левая и правая части независимы, поэтому число возможных способов приема всех конфет - это количество уникальных перестановок последовательности LLLL....LLLRRR....RRR, где i - 1L's и N - iR's.

Общее число таких перестановок:

SequenceLength!/(count(L)!*count(R)!) = (N - 1)!/((i - 1)! * (N - i)!) 

Теперь, если мы суммируем по всем возможным i значения, мы имеем:

Answer 6

Вам не нужно проходить через бином коэффициенты.

Существует 2^(n-1) последовательности Rs и Ls длины n-1. Они находятся в биекции с последовательностями взятия конфет, записывая, будет ли следующая следующая конфета справа или слева от тех, которые вы использовали раньше. Любая последовательность Rs и Ls однозначно определяет местоположение первой конфеты: если есть Ls, то первая конфета должна быть в положении a + 1.