ИГРА НА ОСНОВЕ ТОЧНЫХ РАСЧЕТОВ

Эта игра известна более полувека – ее используют в качестве упражнения для начинающих программистов. Еще 15 лет назад Роберт Монио называл ее «почетным ветераном». Играют в одиночку (на самом деле это скорее набор головоломок) против безжалостного компьютерного противника: Сборщика налогов.

Для начала запишите все натуральные числа от 1 до какого-то предела, скажем до 12.

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

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

Продолжайте, пока у еще невыбранных чисел не останется делителей, не доставшихся Сборщику налогов.

Естественно, цель состоит в том, чтобы победить Сборщика налогов.

Полезная отправная точка – «жадный алгоритм»: каждый раз выбирайте число, которое принесет вам наибольшее количество очков. Например, в игре с числовым рядом от 1 до 15 лучший первый ход – выбрать 13 (это даст вам преимущество в 12 очков).

Но иногда, руководствуясь этой стратегией, вы упускаете лучший ход. Например, после 13 лучше всего, казалось бы, выбрать 15 (получив преимущество в 7 очков). Но тогда вы упускаете девятку, которая позже достанется Сборщику налогов. Лучше выбрать вначале 9, а уже потом 15.

Для игры с небольшими числами вы можете использовать карты (например, если потолок 12, то выкладывайте карты с двойки до 10, плюс туз = 1, валет = 11, дама = 12). В эту игру даже лучше, чем в другие, играется под песню Beatles «Сборщик налогов».