Алгоритмы C++
.pdf
то таковой делитель найдётся после вычисления |
. Следовательно, для каждого делителя |
его |
|
слагаемое |
учтётся несколько раз, т.е. сумму можно представить в таком виде: |
|
|
|
|
|
|
|
|
где |
— это количество таких чисел |
, что |
. Найдём явное выражение для этого количества. |
||
Любое такое число |
имеет вид: |
, где |
(иначе было бы |
). Вспоминая |
|
функцию Эйлера, мы находим, что количество таких |
— это величина функции Эйлера |
. Таким |
|||
образом, |
, и окончательно получаем формулу: |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Расстановка слонов на шахматной доске
Требуется найти количество способов расставить K слонов на доске размером NxN.
Алгоритм
Решать задачу будем с помощью динамического программирования.
Пусть D[i][j] - количество способов расставить j слонов на диагоналях до i-ой включительно, причём только тех диагоналях, которые того же цвета, что и i-ая диагональ. Тогда i = 1..2N-1, j = 0..K.
Диагонали занумеруем следующим образом (пример для доски 5x5):
черные: |
белые: |
||||
1 |
_ 5 _ 9 |
_ 2 _ 6 _ |
|||
_ 5 |
_ 9 _ |
2 |
_ 6 |
_ 8 |
|
5 |
_ 9 _ 7 |
_ 6 _ 8 _ |
|||
_ 9 |
_ 7 _ |
6 |
_ 8 |
_ 4 |
|
9 |
_ 7 _ 3 |
_ 8 _ 4 _ |
|||
Т.е. нечётные номера соответствуют чёрным диагоналям, чётные - белым; диагонали нумеруем в порядке увеличения количества элементов в них.
При такой нумерации мы можем вычислить каждое D[i][], основываясь только на D[i-2][] (двойка вычитается, чтобы мы рассматривали диагональ того же цвета).
Итак, пусть текущий элемент динамики - D[i][j]. Имеем два перехода. Первый - D[i-2][j], т.е. ставим всех j слонов
на предыдущие диагонали. Второй переход - если мы ставим одного слона на текущую диагональ, а остальных j-1 слонов - на предыдущие; заметим, что количество способов поставить слона на текущую диагональ равно количеству клеток в ней минус j-1, т.к. слоны, стоящие на предыдущих диагоналях, будут перекрывать часть направлений. Таким
образом, имеем:
D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1)
где cells(i) - количество клеток, лежащих на i-ой диагонали. Например, cells можно вычислять так:
int cells (int i) { if (i & 1)
return i / 4 * 2 + 1;
else
return (i - 1) / 4 * 2 + 2;
}
Осталось определить базу динамики, тут никаких сложностей нет: D[i][0] = 1, D[1][1] = 1.
Наконец, вычислив динамику, найти собственно ответ к задаче несложно. Перебираем количество i=0..K слонов, стоящих на чёрных диагоналях (номер последней чёрной диагонали - 2N-1), соответственно K-i слонов ставим на белые диагонали (номер последней белой диагонали - 2N-2), т.е. к ответу прибавляем величину D[2N-1][i] * D[2N-2][K-i].
Реализация
int n, k; // входные данные if (k > 2*n-1) {
cout << 0; return 0;
}
vector < vector<int> > d (n*2, vector<int> (k+2)); for (int i=0; i<n*2; ++i)
d[i][0] = 1; d[1][1] = 1;
for (int i=2; i<n*2; ++i)
for (int j=1; j<=k; ++j)
d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);
int ans = 0;
for (int i=0; i<=k; ++i)
ans += d[n*2-1][i] * d[n*2-2][k-i]; cout << ans;
отлично от нуля, то данная строка не является правильной скобочной последовательностью, иначе является.
.
пар скобок (строка длины 
), то количество будет равно:
Пусть теперь имеется не один, а типов скобок. Тогда каждая пара скобок независимо от остальных может принимать один из 
типов, а потому мы получаем такую формулу:
Нахождение всех последовательностей
Иногда требуется найти и вывести все правильные скобочные последовательности указанной длины 
(в данном случае 
— это длина строки).
Для этого можно начать с лексикографически первой последовательности "...((()))...", а затем находить каждый раз лексикографически следующую последовательность с помощью алгоритма, описанного в следующем разделе.
Но если ограничения не очень большие ( до |
), то можно поступить значительно проще. Найдём |
|
всевозможные перестановки этих скобок (для этого удобно использовать функцию next_permutation()), их будет |
, |
|
и каждую проверим на правильность вышеописанным алгоритмом, и в случае правильности выведем |
|
|
текущую последовательность. |
|
|
Также процесс нахождения всех последовательностей можно оформить в виде рекурсивного перебора с отсечениями.
Нахождение следующей последовательности
Здесь рассматривается только случай одного типа скобок.
По заданной правильной скобочной последовательности требуется найти правильную скобочную последовательность, которая находится следующей в лексикографическом порядке после текущей (или выдать "No solution", если такой не существует).
Будем двигаться по последовательности справа налево и считать количество открывающих и закрывающих скобок. Если в какой-то момент мы стоим на открывающей скобке, а количество открывающих скобок строго меньше количества закрывающих, то мы нашли самую правую позицию, от которой мы можем начать изменять последовательность. Поставим в неё закрывающую скобку, затем максимально возможное
количество открывающих скобок, а затем все оставшиеся закрывающие скобки. Если такой позиции мы не смогли найти, то ответа не существует.
Реализация:
string s; cin >> s;
int n = (int) s.length(); string ans = "No solution";
for (int i=n-1, c1=0, c2=0; i>=0; --i) { if (s[i] == '(')
++c1;
else
++c2;
if (s[i] == '(' && c1 < c2) { ans = s.substr(0,i) + ')'; for (int k=0; k<c1; ++k)
ans += '(';
for (int k=0; k<c2-1; ++k) ans += ')';
break;
}
}
cout << ans;
Таким образом, мы решили эту задачу за 
.
Номер последовательности
Здесь пусть N - количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
Научимся считать динамику , где 
— длина последовательности (не обязательно правильной), 
— баланс
(т.е. разность между количеством открывающих и закрывающих скобок, рассматриваются только случаи, когда баланс неотрицателен), 
— количество таких последовательностей.
Базой динамики является |
, а переходы такие: пусть мы находимся в состоянии |
, и |
попробуем добавить '(' или ')'. Если мы добавляем открывающую скобку, то переходим в состояние
, иначе — в 
.
Таким образом, эту динамику мы можем посчитать за 
.
Сначала пусть допустимы только скобки одного типа.
Теперь посчитаем с помощью этой динамики номер последовательности. Для этого заведём счётчик глубины вложенности в скобки, и будем двигаться по последовательности слева направо. Если текущий символ
( |
) равен '(', то мы увеличиваем |
на 1 и переходим к следующему символу. Если |
же текущий символ равен ')', то мы должны прибавить к ответу |
, тем самым учитывая, |
|
что в этой позиции мог бы стоять символ '(' (который бы привёл к лексикографически меньшей последовательности, чем текущая); затем мы уменьшаем 
на единицу.
Пусть теперь разрешены скобки нескольких типов. Тогда, ясно, мы должны на каждом шаге перебирать все скобки, которые меньше текущего символа, и прибавлять к ответу соответствующее
значение |
, однако его надо будет домножить на |
, чтобы учесть, что в |
этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только |
||
, поскольку |
скобок являются закрывающими для открывающих скобок, |
|
находящихся вне этого остатка (а потому их типы мы варьировать не можем).
Нахождение 
-ой последовательности
Здесь пусть 
— количество пар скобок в последовательности. В данной задаче по заданному требуется найти - ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
Как и в предыдущем разделе, посчитаем динамику |
— количество правильных скобочных |
|
последовательностей длины с балансом . |
|
|
Пусть сначала допустимы только скобки одного типа. |
|
|
Будем двигаться по символам искомой строки, с 0-го по |
-ый. Как и в предыдущей задаче, будем хранить |
|
счётчик |
— текущую глубину вложенности в скобки. В каждой текущей позиции будем перебирать |
|
возможный символ - открывающую скобку или закрывающую. Пусть мы хотим поставить сюда открывающую скобку,
тогда мы должны посмотреть на значение |
. Если оно |
, то мы ставим в текущую |
|
позицию открывающую скобку, увеличиваем |
на единицу и переходим к следующему символу. Иначе мы |
|
|
отнимаем от величину |
, ставим закрывающую скобку и уменьшаем значение |
. В |
|
конце концов мы и получим искомую скобочную последовательность. Реализация на языке Java с использованием длинной арифметики:
int n; BigInteger k; // входные данные
BigInteger d[][] = new BigInteger [n*2+1][n+1]; for (int i=0; i<=n*2; ++i)
for (int j=0; j<=n; ++j)
d[i][j] = BigInteger.ZERO; d[0][0] = BigInteger.ONE;
for (int i=0; i<n*2; ++i)
for (int j=0; j<=n; ++j) { if (j+1 <= n)
d[i+1][j+1] = d[i+1][j+1].add( d[i][j] ); if (j > 0)
d[i+1][j-1] = d[i+1][j-1].add( d[i][j] );
}
String ans = new String();
if (k.compareTo( d[n*2][0] ) > 0) ans = "No solution";
else {
int depth = 0;
for (int i=n*2-1; i>=0; --i)
if (depth+1 <= n && d[i][depth+1].compareTo( k ) >= 0) { ans += '(';
++depth;
}
else {
ans += ')';
if (depth+1 <= n)
k = k.subtract( d[i][depth+1] ); --depth;
}
}
Пусть теперь разрешён не один, а типов скобок. Тогда алгоритм решения будет отличаться от предыдущего |
|
|
случая только тем, что мы должны домножать значение |
на величину |
, |
чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только , поскольку скобок являются закрывающими для открывающих
скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем). Реализация на языке Java для случая двух типов скобок - круглых и квадратных:
int n; BigInteger k; // входные данные
BigInteger d[][] = new BigInteger [n*2+1][n+1]; for (int i=0; i<=n*2; ++i)
for (int j=0; j<=n; ++j)
d[i][j] = BigInteger.ZERO; d[0][0] = BigInteger.ONE;
for (int i=0; i<n*2; ++i)
for (int j=0; j<=n; ++j) { if (j+1 <= n)
d[i+1][j+1] = d[i+1][j+1].add( d[i][j] ); if (j > 0)
d[i+1][j-1] = d[i+1][j-1].add( d[i][j] );
}
String ans = new String(); int depth = 0;
char [] stack = new char[n*2]; int stacksz = 0;
for (int i=n*2-1; i>=0; --i) { BigInteger cur;
// '('
if (depth+1 <= n)
cur = d[i][depth+1].shiftLeft( (i-depth-1)/2 );
else
cur = BigInteger.ZERO; if (cur.compareTo( k ) >= 0) {
ans += '('; stack[stacksz++] = '('; ++depth;
continue;
}
k = k.subtract( cur ); // ')'
if (stacksz > 0 && stack[stacksz-1] == '(' && depth-1 >= 0) cur = d[i][depth-1].shiftLeft( (i-depth+1)/2 );
else
cur = BigInteger.ZERO;
if (cur.compareTo( k ) >= 0) { ans += ')';
--stacksz; --depth; continue;
}
k = k.subtract( cur ); // '['
if (depth+1 <= n)
cur = d[i][depth+1].shiftLeft( (i-depth-1)/2 );
else
cur = BigInteger.ZERO; if (cur.compareTo( k ) >= 0) {
ans += '['; stack[stacksz++] = '['; ++depth;
continue;
}
k = k.subtract( cur ); // ']'
ans += ']'; --stacksz; --depth;
}