Давайте сначала рассмотрим метод грубой силы.
Каталонское число c n - это количество способов, которыми можно комбинировать n ходов вверх(╱) и n нажатий (╲), не опускаясь ниже горизонта.По определению c n = (n + 2) / 2 · (n + 3) / 3 · ... (n + n) /n.
Мы можем использовать беззнаковые 2 n битовые целые числа для описания каждой комбинации.(Однако не все 2 n битовых целочисленных значений без знака описывают действительную комбинацию.) Если мы рассматриваем ненулевой или установленный бит как восходящий удар, а нулевой бит - как нисходящий, пик возникает, когда после нисходящего удара следует заход вверх.(Когда за ходом вниз следует за ходом вверх, у вас есть долина.)
(Обратите внимание, что не все беззнаковые 2 n битовые целочисленные значения описывают действительную комбинацию. Чтобы быть действительным, оченьпервый бит должен быть восходящим, и должно быть точно n повышающих ударов.)
Итак, сначала напишите функцию, которая вычисляет количество пиков в одной комбинации, описываемой целым числом без знака.(Обратите внимание, что поскольку каждое целое число без знака, которое описывает комбинацию, имеет точно установленный n бит, нам не нужно явно передавать n , только целое число без знака, которое описывает комбинацию.) Например,,
unsigned int peaks(unsigned int description)
{
unsigned int count = 0;
while (description) {
count += ((description & 3) == 1);
description >>= 1;
}
return count;
}
Выше комбинация считывается, начиная с младшего бита.(И поскольку для горного хребта должно быть установлено, что он может быть выше горизонта, ни одно четное значение не описывает комбинацию.) Выражение (description & 3) выделяет два последних значащих бита.Четыре возможных случая соответствуют двойному наклону, пику, долине и двойному наклону соответственно в порядке возрастания числового значения.Пиковый регистр соответствует значению 1 (01 b в двоичном виде: ход вверх, затем ход вниз, чтение цифр в порядке возрастания значимости, справа налево).В C значение логического False равно нулю, а логическое True равно 1, поэтому в вышеприведенном цикле мы получаем количество случаев, когда установленный бит следует (в более значимом положении) битом сброса.
Value Mountains n Peaks
1 ╱╲ 1 1
3 ╱╱╲╲ 2 1
5 ╱╲╱╲ 2 2
7 ╱╱╱╲╲╲ 3 1
9 ╱╲╲╱ Not a valid combination
11 ╱╱╲╱╲╲ 3 2
13 ╱╲╱╱╲╲ 3 2
15 ╱╱╱╱╲╲╲╲ 4 1
17 ╱╲╲╲╱ Not a valid combination
19 ╱╱╲╲╱╲ 3 2
21 ╱╲╱╲╱╲ 3 3
23 ╱╱╱╲╱╲╲╲ 4 2
25 ╱╲╲╱╱╲ Not a valid combination
27 ╱╱╲╱╱╲╲╲ 4 2
29 ╱╲╱╱╱╲╲╲ 4 2
31 ╱╱╱╱╱╲╲╲╲╲ 5 1
33 ╱╲╲╲╲╱ Not a valid combination
35 ╱╱╲╲╲╱ Not a valid combination
37 ╱╲╱╲╲╱ Not a valid combination
39 ╱╱╱╲╲╱╲╲ 4 2
Затем создайте функцию, которая генерирует все целочисленные значения без знака, которые описывают действительную комбинацию для конкретного n , и подсчитайте ихкоторые соответствуют определенному числу пиков.
Один из способов перебора - написать функцию подсчета пиков, чтобы она возвращала 0 для всех недопустимых комбинаций.Например:
static unsigned int peaks(unsigned int description)
{
unsigned int count = 0;
int height = 0;
/* Description must start with an upstroke. */
if (!(description & 1))
return 0;
while (description) {
switch (description & 3) {
case 0: /* Downslope; next is downslope. */
if (--height < 0)
return 0;
break;
case 1: /* Upslope; next is downslope. */
count++;
height++;
break;
case 2: /* Downslope; next is upslope. */
if (--height < 0)
return 0;
break;
default: /* 3: Upslope; next is upslope. */
height++;
}
description >>= 1;
}
return count;
}
n , которому соответствует описание (если peak(description) > 0), - это количество битов, установленных в описании.Отличный трюк для подсчета, который составляет
unsigned int popcount(unsigned int value)
{
unsigned int count = 0;
while (value) {
value &= value - 1;
count++;
}
return count;
}
С помощью этих двух функций вы можете решить поставленный вопрос для мелкого n , исследуя все 2 n -битцелые числа без знака (от 0 до (1 << (2*n)) - 1 включительно).
Для лучшего подхода давайте проверим количество пиков для каждого n :
n Combs Occurrences*Peaks
0 1 1*0
1 1 1*1
2 2 1*1, 1*2
3 5 1*1, 3*2, 1*3
4 14 1*1, 6*2, 6*3, 1*4
5 42 1*1, 10*2, 20*3, 10*4, 1*5
6 132 1*1, 15*2, 50*3, 50*4, 15*5, 1*6
Другими словами, n = 6 имеет 132 действительных комбинации.Из них один с одним пиком, 15 с двумя пиками, 50 с тремя пиками, 50 с четырьмя пиками и один с шестью пиками.
Если мы просто сформируем целочисленные последовательности для подсчета пиков, мыможно выразить вышеуказанное как
1,
1, 1,
1, 3, 1
1, 6, 6, 1,
1, 10, 20, 10, 1,
1, 15, 50, 50, 15, 1,
и т. д., продолжая с 1, 21, 105, 175, 105, 21, 1 для n = 7 и с 1, 28,196, 490, 490, 196, 28, 1 для n = 8 и т. Д.
Если мы выполним поиск этой последовательности в OEIS, мы обнаружим, что это на самом деленазываемые числами Нараяны T ( n , k ), и вся целочисленная последовательность равна OEIS A001263 .
(Примечание: я не знал, что это так! Все, что я знал, я мог использовать OEIS, чтобы узнать, была ли известна последовательность, и обычно они есть. Другими словами, я не просто показываю вам ответ на этот конкретный вопрос здесь., но как я нахожу - весьма эффективно, если можно так выразиться, - решения этой проблемы, начиная с численного подхода грубой силы.)
Таким образом, математический ответ таков: число Нараяны T ( n , k ) сообщает вам количество различных горных цепей, соответствующих каталонскомучисло c n с точными k пиками.
Если вы реализуете биномиальный коэффициент как функцию binomial(n, k),тогда ответ будет T(n, k) = binomial(n, k) * binomial(n, k - 1) / n.
Обратите внимание, однако, что вы можете реализовать T(n, k) более эффективно как разделение между продуктами терминов (то есть, используя два массива терминов и исключая общие термины и продуктычленов, использующих вспомогательную функцию * наибольший общий делитель *, без проблем с точностью из-за отмены термина.)