Алгоритм поиска компонент связности в графе

Форд-Беллман

struct edge {

int a, b, cost;

};

 

int n, m, v;

vector<edge> e;

const int INF = 1000000000;

 

void solve() {

vector<int> d (n, INF);

d[v] = 0;

for (;;) {

bool any = false;

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

if (d[e[j].b] > d[e[j].a] + e[j].cost) {

d[e[j].b] = d[e[j].a] + e[j].cost;

any = true;

}

if (!any) break;

}

// вывод d, например, на экран

}

 

Флойд-Уоршелл

Дан ориентированный или неориентированный взвешенный граф с вершинами. Требуется найти значения всех величин — длины кратчайшего пути из вершины в вершину .

Предполагается, что граф не содержит циклов отрицательного веса (тогда ответа между некоторыми парами вершин может просто не существовать — он будет бесконечно маленьким).

for (int k=0; k<n; ++k)

for (int i=0; i<n; ++i)

for (int j=0; j<n; ++j)

if (d[i][k] < INF && d[k][j] < INF)

d[i][j] = min (d[i][j], d[i][k] + d[k][j]);

 

BFS

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

Алгоритм работает за , где — число вершин, — число рёбер.

vector < vector<int> > g; // граф

int n; // число вершин

int s; // стартовая вершина (вершины везде нумеруются с нуля)

queue<int> q;

q.push (s);

vector<bool> used (n);

vector<int> d (n), p (n);

used[s] = true;

p[s] = -1;

while (!q.empty()) {

int v = q.front();

q.pop();

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (!used[to]) {

used[to] = true;

q.push (to);

d[to] = d[v] + 1;

p[to] = v;

}

}

}

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

 

if (!used[to])

cout << "No path!";

else {

vector<int> path;

for (int v=to; v!=-1; v=p[v])

path.push_back (v);

reverse (path.begin(), path.end());

cout << "Path: ";

for (size_t i=0; i<path.size(); ++i)

cout << path[i] + 1 << " ";

}

 

DFS

В результате поиска в глубину находится лексикографически первый путь в графе.

vector<bool> used;

void dfs(int v)
{
used[v] = true;
cout << v;
for (vector<int>::iterator i = g[v].begin(); i!= g[v].end(); ++i)
if (!used[*i])
dfs(*i);
}

 

Алгоритм поиска компонент связности в графе

 

Дан неориентированный граф с вершинами и рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.

int n;

vector<int> g[MAXN];

bool used[MAXN];

vector<int> comp;

 

void dfs (int v)

(………………………)

void find_comps() {

for (int i=0; i<n; ++i)

used[i] = false;

for (int i=0; i<n; ++i)

if (! used[i]) {

comp.clear();

dfs (i);

 

cout << "Component:";

for (size_t j=0; j<comp.size(); ++j)

cout << ' ' << comp[j];

cout << endl;

}

}

 

Поиск мостов

Пусть дан неориентированный граф. Мостом называется такое ребро, удаление которого делает граф несвязным (или, точнее, увеличивает число компонент связности). Требуется найти все мосты в заданном графе.

Неформально эта задача ставится следующим образом: требуется найти на заданной карте дорог все "важные" дороги, т.е. такие дороги, что удаление любой из них приведёт к исчезновению пути между какой-то парой городов.

const int MAXN =...;

vector<int> g[MAXN];

bool used[MAXN];

int timer, tin[MAXN], fup[MAXN];

 

void dfs (int v, int p = -1) {

used[v] = true;

tin[v] = fup[v] = timer++;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (to == p) continue;

if (used[to])

fup[v] = min (fup[v], tin[to]);

else {

dfs (to, v);

fup[v] = min (fup[v], fup[to]);

if (fup[to] > tin[v])

IS_BRIDGE(v,to);

}

}

}

 

void find_bridges() {

timer = 0;

for (int i=0; i<n; ++i)

used[i] = false;

for (int i=0; i<n; ++i)

if (!used[i])

dfs (i);

}

 

Поиск точек сочленения

Пусть дан связный неориентированный граф. Точкой сочленения (или точкой артикуляции, англ. "cut vertex" или "articulation point") называется такая вершина, удаление которой делает граф несвязным.

vector<int> g[MAXN];

bool used[MAXN];

int timer, tin[MAXN], fup[MAXN];

 

void dfs (int v, int p = -1) {

used[v] = true;

tin[v] = fup[v] = timer++;

int children = 0;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (to == p) continue;

if (used[to])

fup[v] = min (fup[v], tin[to]);

else {

dfs (to, v);

fup[v] = min (fup[v], fup[to]);

if (fup[to] >= tin[v] && p!= -1)

IS_CUTPOINT(v);

++children;

}

}

if (p == -1 && children > 1)

IS_CUTPOINT(v);

}

 

int main() {

int n;

... чтение n и g...

 

timer = 0;

for (int i=0; i<n; ++i)

used[i] = false;

dfs (0);

}

Здесь константе должно быть задано значение, равное максимально возможному числу вершин во входном графе.

Функция в коде — это некая функция, которая будет реагировать на то, что вершина является точкой сочленения, например, выводить эту вершины на экран (надо учитывать, что для одной и той же вершины эта функция может быть вызвана несколько раз).

 

8)Дейкстра

const int INF = 1000000000;

 

int main() {

int n;

... чтение n...

vector < vector < pair<int,int> > > g (n);

... чтение графа...

int s =...; // стартовая вершина

 

vector<int> d (n, INF), p (n);

d[s] = 0;

vector<char> u (n);

for (int i=0; i<n; ++i) {

int v = -1;

for (int j=0; j<n; ++j)

if (!u[j] && (v == -1 || d[j] < d[v]))

v = j;

if (d[v] == INF)

break;

u[v] = true;

 

for (size_t j=0; j<g[v].size(); ++j) {

int to = g[v][j].first,

len = g[v][j].second;

if (d[v] + len < d[to]) {

d[to] = d[v] + len;

p[to] = v;

}

}

}

}

 

9) Эратосфен

int n;

vector<char> prime (n+1, true);

prime[0] = prime[1] = false;

for (int i=2; i<=n; ++i)

if (prime[i])

if (i * 1ll * i <= n)

for (int j=i*i; j<=n; j+=i)

prime[j] = false;

 

Задача о назначениях

Задача имеет две эквивалентные постановки:

Дана квадратная матрица A[1..N,1..N]. Нужно выбрать в ней N элементов так, чтобы в каждой строке и столбце был выбран ровно один элемент, а сумма значений этих элементов была наименьшей.

Имеется N заказов и N станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

vector<int> u (n+1), v (m+1), p (m+1), way (m+1);

for (int i=1; i<=n; ++i) {

p[0] = i;

int j0 = 0;

vector<int> minv (m+1, INF);

vector<char> used (m+1, false);

do {

used[j0] = true;

int i0 = p[j0], delta = INF, j1;

for (int j=1; j<=m; ++j)

if (!used[j]) {

int cur = a[i0][j]-u[i0]-v[j];

if (cur < minv[j])

minv[j] = cur, way[j] = j0;

if (minv[j] < delta)

delta = minv[j], j1 = j;

}

for (int j=0; j<=m; ++j)

if (used[j])

u[p[j]] += delta, v[j] -= delta;

else

minv[j] -= delta;

j0 = j1;

} while (p[j0]!= 0);

do {

int j1 = way[j0];

p[j0] = p[j1];

j0 = j1;

} while (j0);

}

 

Binpow

int binpow (int a, int n) {

int res = 1;

while (n) {

if (n & 1)

res *= a;

a *= a;

n >>= 1;

}

return res;

}

 

 

Расширенный Евклид

В то время как "обычный" алгоритм Евклида просто находит наибольший общий делитель двух чисел и , расширенный алгоритм Евклида находит помимо НОД также коэффициенты и такие, что:

Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

int gcd (int a, int b, int & x, int & y) {

if (a == 0) {

x = 0; y = 1;

return b;

}

int x1, y1;

int d = gcd (b%a, a, x1, y1);

x = y1 - (b / a) * x1;

y = x1;

return d;

}

 

Длинка

Структура данных

Хранить длинные числа будем в виде вектора чисел , где каждый элемент — это одна цифра числа.

typedef vector<int> lnum;

Для повышения эффективности будем работать в системе по основанию миллиард, т.е. каждый элемент вектора содержит не одну, а сразу цифр:

const int base = 1000*1000*1000;

Цифры будут храниться в векторе в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).

Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.

А)Вывод

printf ("%d", a.empty()? 0: a.back());

for (int i=(int)a.size()-2; i>=0; --i)

printf ("%09d", a[i]);

Б) Чтение

for (int i=(int)s.length(); i>0; i-=9)

if (i < 9)

a.push_back (atoi (s.substr (0, i).c_str()));

else

a.push_back (atoi (s.substr (i-9, 9).c_str()));

В) Сложение

int carry = 0;

for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {

if (i == a.size())

a.push_back (0);

a[i] += carry + (i < b.size()? b[i]: 0);

carry = a[i] >= base;

if (carry) a[i] -= base;

}

Г) Вычитание

int carry = 0;

for (size_t i=0; i<b.size() || carry; ++i) {

a[i] -= carry + (i < b.size()? b[i]: 0);

carry = a[i] < 0;

if (carry) a[i] += base;

}

while (a.size() > 1 && a.back() == 0)

a.pop_back();

Д) Умножение длинного на короткое

int carry = 0;

for (size_t i=0; i<a.size() || carry; ++i) {

if (i == a.size())

a.push_back (0);

long long cur = carry + a[i] * 1ll * b;

a[i] = int (cur % base);

carry = int (cur / base);

}

while (a.size() > 1 && a.back() == 0)

a.pop_back();

Е) Умножение двух длинных чисел

lnum c (a.size()+b.size());

for (size_t i=0; i<a.size(); ++i)

for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {

long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size()? b[j]: 0) + carry;

c[i+j] = int (cur % base);

carry = int (cur / base);

}

while (c.size() > 1 && c.back() == 0)

c.pop_back();

Ж) Деление длинного на короткое

int carry = 0;

for (int i=(int)a.size()-1; i>=0; --i) {

long long cur = a[i] + carry * 1ll * base;

a[i] = int (cur / b);

carry = int (cur % b);

}

while (a.size() > 1 && a.back() == 0)

a.pop_back();

carry – остаток

 

Диофантовы уравнения

int gcd (int a, int b, int & x, int & y) {

if (a == 0) {

x = 0; y = 1;

return b;

}

int x1, y1;

int d = gcd (b%a, a, x1, y1);

x = y1 - (b / a) * x1;

y = x1;

return d;

}

 

bool find_any_solution (int a, int b, int c, int & x0, int & y0, int & g) {

g = gcd (abs(a), abs(b), x0, y0);

if (c % g!= 0)

return false;

x0 *= c / g;

y0 *= c / g;

if (a < 0) x0 *= -1;

if (b < 0) y0 *= -1;

return true;

}

A,b>0;

 

Дискретное логарифмирование

Задача дискретного логарифмирования заключается в том, чтобы по данным целым , , решить уравнение:

где и — взаимно просты

int solve (int a, int b, int m) {

int n = (int) sqrt (m +.0) + 1;

 

int an = 1;

for (int i=0; i<n; ++i)

an = (an * a) % m;

 

map<int,int> vals;

for (int i=1, cur=an; i<=n; ++i) {

if (!vals.count(cur))

vals[cur] = i;

cur = (cur * an) % m;

}

 

for (int i=0, cur=b; i<=n; ++i) {

if (vals.count(cur)) {

int ans = vals[cur] * n - i;

if (ans < m)

return ans;

}

cur = (cur * a) % m;

}

return -1;

}

 

Максимальный подпалиндром

Биномиальные коэффициенты

Биномиальным коэффициентом называется количество способов выбрать набор предметов из различных предметов без учёта порядка расположения этих элементов (т.е. количество неупорядоченных наборов).

 

int C (int n, int k) {

double res = 1;

for (int i=1; i<=k; ++i)

res = res * (n-k+i) / i;

return (int) (res + 0.01);

}

 

Числа Каталана

Числа Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач.

Первые несколько чисел Каталана (начиная с нулевого):

Числа Каталана встречаются в большом количестве задач комбинаторики. -ое число Каталана — это:

Количество корректных скобочных последовательностей, состоящих из открывающих и закрывающих скобок.

Количество корневых бинарных деревьев с листьями (вершины не пронумерованы).

Количество способов полностью разделить скобками множитель.

Количество триангуляций выпуклого -угольника (т.е. количество разбиений многоугольника непересекающимися диагоналями на треугольники).

Количество способов соединить точек на окружности непересекающимися хордами.

Количество неизоморфных полных бинарных деревьев с внутренними вершинами (т.е. имеющими хотя бы одного сына).

Количество монотонных путей из точки в точку в квадратной решётке размером , не поднимающихся над главной диагональю.

Количество перестановок длины , которые можно отсортировать стеком (можно показать, что перестановка является сортируемой стеком тогда и только тогда, когда нет таких индексов , что ).

Количество непрерывных разбиений множества из элементов (т.е. разбиений на непрерывные блоки).

Количество способов покрыть лесенку с помощью прямоугольников (имеется в виду фигура, состоящая из столбцов, -ый из которых имеет высоту ).

Вычисление

Имеется две формулы для чисел Каталана: рекуррентная и аналитическая. Поскольку мы считаем, что все приведённые выше задачи эквивалентны, то для доказательства формул мы будем выбирать ту задачу, с помощью которой это сделать проще всего.

Рекуррентная формула

Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.

Самой левой открывающей скобке l соответствует определённая закрывающая скобка r, которая разбивает формулу две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим , то для любого фиксированного будет ровно способов. Суммируя это по всем допустимым , мы и получаем рекуррентную зависимость на .

Аналитическая формула

(здесь через обозначен, как обычно, биномиальный коэффициент).

Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером равно . Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке . Но, с другой стороны, любой монотонный путь в решётке обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке . Монотонных путей в решётке имеется . В результате получаем формулу:

 

 

Ожерелья

Задача "ожерелья" — это одна из классических комбинаторных задач. Требуется посчитать количество различных ожерелий из бусинок, каждая из которых может быть покрашена в один из цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).

Решение

Решить эту задачу можно, используя лемму Бернсайда и теорему Пойа. [ Ниже идёт копия текста из этой статьи ]

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

Найдём явную формулу для вычисления . Во-первых, заметим, что перестановки имеют такой вид, что в -ой перестановке на -ой позиции стоит (взятое по модулю , если оно больше ). Если мы будем рассматривать циклическую структуру -ой перестановки, то увидим, что единица переходит в , переходит в , — в , и т.д., пока не придём в число ; для остальных элементов выполняются похожие утверждения. Отсюда можно понять, что все циклы имеют одинаковую длину, равную , т.е. ("gcd" — наибольший общий делитель, "lcm" — наименьшее общее кратное). Тогда количество циклов в -ой перестановке будет равно просто .

Подставляя найденные значения в теорему Пойа, получаем решение:

Можно оставить формулу в таком виде, а можно её свернуть ещё больше. Перейдём от суммы по всем к сумме только по делителям . Действительно, в нашей сумме будет много одинаковых слагаемых: если не является делителем , то таковой делитель найдётся после вычисления . Следовательно, для каждого делителя его слагаемое учтётся несколько раз, т.е. сумму можно представить в таком виде:

где — это количество таких чисел , что . Найдём явное выражение для этого количества. Любое такое число имеет вид: , где (иначе было бы ). Вспоминая функцию Эйлера, мы находим, что количество таких — это величина функции Эйлера . Таким образом, , и окончательно получаем формулу:

 

Задача о ферзях

int SIZE = 0;

int board[13][13];

int results_count = 0;

void showBoard()

{

for(int a = 0; a < SIZE; ++a)

{

for(int b = 0; b < SIZE; ++b)

{

std::cout << ((board[a][b])? "Q ": ". ");

}

std::cout << '\n';

}

}

bool tryQueen(int a, int b)

{

for(int i = 0; i < a; ++i)

{

if(board[i][b])

{

return false;

}

}

 

for(int i = 1; i <= a && b-i >= 0; ++i)

{

if(board[a-i][b-i])

{

return false;

}

}

 

for(int i = 1; i <= a && b+i < SIZE; i++)

{

if(board[a-i][b+i])

{

return false;

}

}

 

return true;

}

 

void setQueen(int a) {

if(a == SIZE)

{

 

results_count++;

return;

}

 

for(int i = 0; i < SIZE; ++i)

{ if(tryQueen(a, i))

{

board[a][i] = 1;

setQueen(a+1);

board[a][i] = 0;

}

}

 

return;

}

 

int main()

{

 

std::cin >> SIZE;

setQueen(0);

std::cout << results_count << std::endl;

 

return 0;

}

 

 

36)Ханойские башни

void hanoi_towers(int quantity, int from, int to, int buf_peg) {

if (quantity!= 0)
{
hanoi_towers(quantity-1, from, buf_peg, to);

cout << from << ' ' << to << endl;

hanoi_towers(quantity-1, buf_peg, to, from);
}
}

int main()
{
setlocale(LC_ALL,"rus");
int start_peg=1, destination_peg=2, buffer_peg=3, plate_quantity;
cin >> plate_quantity;

hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg);
return 0;
}

 

Теория Шпрага-Гранди. Ним

Введение

игру можно полностью описать ориентированным ациклическим графом: вершинами в нём являются состояния игры, а рёбрами — переходы из одного состояния игры в другое в результате хода текущего игрока

Поскольку ничейных исходов не бывает, то все состояния игры распадаются на два класса: выигрышные и проигрышные. Выигрышные — это такие состояния, что найдётся ход текущего игрока, который приведёт к неминуемому поражению другого игрока даже при его оптимальной игре. Соответственно, проигрышные состояния — это состояния, из которых все переходы ведут в состояния, приводящие к победе второго игрока, несмотря на "сопротивление" первого игрока. Иными словами, выигрышным будет состояние, из которого есть хотя бы один переход в проигрышное состояние, а проигрышным является состояние, из которого все переходы ведут в выигрышные состояния (или из которого вообще нет переходов).

Теорема. Текущий игрок имеет выигрышную стратегию тогда и только тогда, когда XOR-сумма размеров кучек отлична от нуля. В противном случае текущий игрок находится в проигрышном состоянии. (XOR-суммой чисел называется выражение , где — операция побитового исключающего или)

Теорема Шпрага-Гранди об эквивалентности любой игры ниму

Теорема Шпрага-Гранди. Рассмотрим любое состояние некоторой равноправной игры двух игроков. Пусть из него есть переходы в некоторые состояния (где ). Утверждается, что состоянию этой игры можно поставить в соответствие кучку нима некоторого размера (которая будет полностью описывать состояние нашей игры — т.е. эти два состояния двух разных игр будут эквивалентны). Это число — называется значением Шпрага-Гранди состояния .

Более того, это число можно находить следующим рекурсивным образом: посчитаем значение Шпрага-Гранди по каждому переходу , и тогда выполняется:

где функция от множества чисел возвращает наименьшее неотрицательное число, не встречающееся в этом множестве (название "mex" — это сокращение от "minimum excludant").

Таким образом, мы можем, стартуя от вершин без исходящих рёбер, постепенно посчитать значения Шпрага-Гранди для всех состояний нашей игры. Если значение Шпрага-Гранди какого-либо состояния равно нулю, то это состояние проигрышно, иначе — выигрышно.

Применение теоремы Шпрага-Гранди

Функция, которая каждому состоянию игры ставит в соответствие ним-число, называется функцией Шпрага-Гранди.

Итак, чтобы посчитать функцию Шпрага-Гранди для текущего состояния некоторой игры, нужно:

Выписать все возможные переходы из текущего состояния.

Каждый такой переход может вести либо в одну игру, либо в сумму независимых игр.

В первом случае — просто посчитаем функцию Гранди рекурсивно для этого нового состояния.

Во втором случае, когда переход из текущего состояния приводит в сумму нескольких независимых игр — рекурсивно посчитаем для каждой из этих игр функцию Гранди, а затем скажем, что функция Гранди суммы игр равна XOR-сумме значений этих игр.

После того, как мы посчитали функцию Гранди для каждого возможного перехода — считаем от этих значений, и найденное число — и есть искомое значение Гранди для текущего состояния.

Если полученное значение Гранди равно нулю, то текущее состояние проигрышно, иначе — выигрышно.

Таким образом, по сравнению с теоремой Шпрага-Гранди здесь мы учитываем то, что в игре могут быть переходы из отдельных состояний в суммы нескольких игр. Чтобы работать с суммами игр, мы сначала заменяем каждую игру её значением Гранди, т.е. одной ним-кучкой некоторого размера. После этого мы приходим к сумме нескольких ним-кучек, т.е. к обычному ниму, ответ для которого, согласно теореме Бутона — XOR-сумма размеров кучек.

Закономерности в значениях Шпрага-Гранди

"Крестики-крестики"

Условие. Рассмотрим клетчатую полоску размера клеток. За один ход игроку надо поставить один крестик, но при этом запрещено ставить два крестика рядом (в соседние клетки). Проигрывает тот, кто не может сделать ход. Сказать, кто выиграет при оптимальной игре.

Решение. Когда игрок ставит крестик в какую-либо клетку, можно считать, что вся полоска распадается на две независимые половинки: слева от крестика и справа от него. При этом сама клетка с крестиком, а также её левый и правый сосед уничтожаются — т.к. в них больше ничего нельзя будет поставить.

Следовательно, если мы занумеруем клетки полоски от до , то, поставив крестик в позицию , полоска распадётся на две полоски длины и , т.е. мы переходим в сумму двух игр и . Если же крестик ставится в позицию или , то это особый случай — мы просто перейдём в состояние .

Таким образом, функция Гранди имеет вид (для ):

Т.е. получается как от множества, состоящего из числа , а также всевозможных значений выражения .

Итак, мы получили решение этой задачи за .

На самом деле, посчитав на компьютере таблицу значений для первой сотни значений , можно увидеть, что, начиная с , последовательность становится периодичной с периодом . Эта закономерность сохраняется и дальше

"Крестики-крестики — 2"

Условие. Снова игра ведётся на полоске клеток, и игроки по очереди ставят по одному крестику. Выигрывает тот, кто поставит три крестика подряд.

Решение. Заметим, что если и мы оставили после своего хода два крестика рядом или через один пробел, то противник следующим ходом выиграет. Следовательно, если один игрок поставил где-то крестик, то другому игроку невыгодно ставить крестик в соседние с ним клетки, а также в соседние с соседними (т.е. на расстоянии и ставить невыгодно, это приведёт к поражению).

Тогда решение получается практически аналогичным предыдущей задаче, только теперь крестик удаляет у каждой половинки не по одной, а сразу по две клетки.

"Пешки"

Условие. Есть поле , на котором в первом и третьем ряду стоят по пешек — белых и чёрных, соответственно. Первый игрок ходит белыми пешками, второй — чёрными. Правила хода и удара — стандартные шахматные, за исключением того, что бить (при наличии такой возможности) обязательно.

Решение. Проследим, что происходит, когда одна пешка сделает ход вперёд. Следующим ходом противник будет обязан съесть её, затем мы будем обязаны съесть пешку противника, затем снова он съест, и, наконец, наша пешка съест вражескую пешку и останется, "упёршись" в пешку противника. Таким образом, если мы в самом начале пошли пешкой в колонке , то в результате три колонки доски фактически уничтожатся, и мы перейдём к сумме игр размера и . Граничные случаи и приводят нас просто к доске размера .

"Lasker's nim"

Условие. Имеется кучек камней заданных размеров. За один ход игрок может взять любое ненулевое число камней из какой-либо кучки, либо же разделить какую-либо кучку на две непустые кучки. Проигрывает тот, кто не может сделать ход.

Решение. Записывая оба вида переходов, легко получить функцию Шпрага-Гранди как:

Однако можно построить таблицу значений для малых и увидеть простую закономерность:

Здесь видно, что для чисел, равных или по модулю , и для чисел, равных и по модулю . Доказать это можно по индукции.

"The game of Kayles"

Условие. Есть кегель, выставленных в ряд. За один удар игрок может выбить либо одну кеглю, либо две рядом стоящие кегли. Выигрывает тот, который выбил последнюю кеглю.

Решение. И когда игрок выбивает одну кеглю, и когда он выбивает две — игра распадается на сумму двух независимых игр.

Нетрудно получить такое выражение для функции Шпрага-Гранди:

Посчитаем для него таблицу для нескольких первых десятков элементов:

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

Grundy's game

Условие. Есть кучек камней, размеры которых мы обозначим через . За один ход игрок может взять какую-либо кучку размера как минимум и разделить её на две непустые кучки неравных размеров. Проигрывает тот, кто не может сделать ход (т.е. когда размеры всех оставшихся кучек меньше либо равны двум).

Решение. Если , то все эти несколько кучек, очевидно, — независимые игры. Следовательно, наша задача — научиться искать функцию Шпрага-Гранди для одной кучки, а ответ для нескольких кучек будет получаться как их XOR-сумма.

Для одной кучки эта функция строится также легко, достаточно просмотреть все возможные переходы:

Чем эта игра интересна — тем, что до сих пор для неё не найдено общей закономерности. Несмотря на предположения, что последовательность должна быть периодичной, она была просчитана вплоть до , и периодов в этой области обнаружено не было.

"Лестничный ним"

Условие. Есть лестница с ступеньками (занумерованными от до ), на -ой ступеньке лежит монет. За один ход разрешается переместить некоторое ненулевое число монет с -ой на -ую ступеньку. Проигрывает тот, кто не может сделать хода.

Решение. Если попытаться свести эту задачу к ниму "в лоб", то получится, что ход у нас — это уменьшение одной кучки на сколько-то, и одновременное увеличение другой кучки на столько же. В итоге мы получаем модификацию нима, решить которую весьма сложно.

Поступим по-другому: рассмотрим только ступеньки с чётными номерами: . Посмотрим, как будет меняться э