Monthly Archives: March 2007

Задача: из N чисел одного не хватает, какого?

Димариус приволок ещё одну задачу. Не в пример проще игры Витгофа, конечно. Любой ламер-программист её должен решить достаточно быстро. Димариус утверждал – даётся минута. Я потратил по заверениям публики секунд 15, значит на самом деле около полминуты. Из них, правда, секунд 15 я потратил на нытьё, что никаким лимитам времени я подчиняться не хочу ^_^

Значит, я ещё не отупел окончательно.

Задача действительно проста: дано множество всех целых чисел от 1 до N. Из этого множества дан неупорядоченный набор чисел количеством N-1 штук. Одного не хватает, стало быть. Задача – определить какого. Сложность алгоритма – O(n), то есть порядка N шагов, если по-русски. Так что вариант “перебирать числа от 1 до N и каждое искать в заданном наборе” – не прокатит, так как тут порядок O(n^2).

Решение задачи о камнях

О-о-о-о-о-о-о-о!!! Я её решил, причём как! И аналитическое решение нашёл, которым можно по заданному k найти n за константное время, и за O(log n) итераций можно проверить, если не доверяем вещественной арифметике, хотя практика показала что тут точности более чем хватает.

Решив, полез в инет искать решения. Выяснил, что задачка была придумана неким Витгофом аж в 1907 году. И он же нашёл решение. 100 лет назад получается, кстати.
Решение, длинное!

Задача о камнях

Нашёл себе занятие! Задача о камнях. Есть два игрока и две кучи камней, в одной их n1 штук, в другой – n2. Хотя бы одно из n1 или n2 не равно нулю (т. е. есть хотя бы один камень в одной из куч). Каждый игрок может за один ход взять любое количество камней из первой кучи либо любое из второй, либо из обеих куч, но одинаковое количество. Кто берёт последним, проигрывает. Задача – написать функцию, которая бы для заданных n1 и n2 находила бы ход, ведущий к победе, либо давала ответ, что ситуация проигрышная. Проигрышная ситуация – это такая ситуация, в которой противник может подобрать ходы так, что его невозможно будет обыграть.

Тривиальная проигрышная ситуация: (0, 1). Один камень в одной куче и ничего не остаётся, кроме как его взять. Менее тривиальная – (2, 2). Варианты ходов из неё:

Можно взять (1, 0), останется (1, 2). Противник берёт (0, 2) – мы оказываемся в проигрышной (1, 0).
Можно взять (1, 1), останется (1, 1). Противник берёт (0, 1) или (1, 0) – мы оказываемся в проигрышной (1, 0) или (0, 1).
Можно взять (2, 2) и проиграть тут же ^_^
Можно взять (0, 1) – будет аналогично (1, 0).
Можно взять (0, 2), останется (2, 0). Противник берёт (1, 0) и ставит нас в (1, 0).
Аналогично (2, 0).

Вообще в этой игре все ситуации симметричны, так как первая куча ничем не отличается от второй. Так что если мы знаем ответ для (n1, n2), то для (n2, n1) он будет аналогичный.

Далее. Если мы возьмём любую проигрышную ситуацию (n1, n2) и прибавим к одному или к обеим числам некое k > 0, то получим ситуацию заведомо выигрышную. Потому что:

Из (n1 + k, n2) мы берём (k, 0) – получается (n1, n2) – напоминаю, она проигрышная, так что наш противник уже проиграл.
Из (n1 + k, n2 + k) мы берём (k, k) – получается опять та же проигрышная (для противника) ситуация. Мы в любом случае в выигрыше.

Отсюда следует, что все ситуации n1 = n2, кроме (2, 2) – выигрышные. (0, 0) мы не рассматриваем, хотя её можно считать выигрышной, так как попадём мы в неё только если противник взял последние камни, то есть уже проиграл. (1, 1) выигрышная, так как забрав один камень, мы ставим противника в проигрышную (1, 0). А (2 + k, 2 + k) выигрышная, так как забрав по k камней из каждой кучи мы поставим противника в проигрышную (2, 2).

Так как задача симметрична, будем считать, что n1 < n2. Обозначим n2 – n1 = k > 0, а n1 обозначим n. Получаем, что начальное условие у нас (n, n + k). Так и будем дальше работать.
Продолжение, длинное!