В игру Ним играют двое.
Есть N (2<=N<=100) кучек камешков. Игроки поочередно берут камешки из кучек.
Выигрывает тот, кто берет последний камешек. На каждом ходу игрок может
брать камешки не больше чем из K (1<=K<=N) кучек, но должен взять хотя бы
один камешек. В начале игры в каждой кучке 0 < H[i] < 1000000000 камешков.
Задача
Напишите программу, которая будет играть в Ним и,
по возможности, выигрывать.
Технические условия
Во время проверки к Вашей программе будет присоединен (linked) модуль
проверки, которая называется CHECK.* (PAS, C или CPP). Этот модуль содержит
3 функции: InitGame, JudgeTurn, PartTurn.
Функция InitGame используется для считывания входных данных из
тестового файла. Она имеет 4 исходных параметры: N и K - количества кучек,
массив H - количества камешков в кучках, First - кто первый ходит. После
вызова этой функции N и K получат соответствующие значения, в первых N
элементах массива H будут количества камешков в кучках, а First принимает
значение 0, если первой ходит программа проверки (жюри), и 1, если первой
ходит программа участника. Обратите внимание, что Ваша программа не должна
самостоятельно читать входные данные, это нужно делать только с
помощью функции InitGame.
Функцию JudgeTurn Ваша программа будет вызвать, если ей нужно будет
получить очередной ход жюри. Единственный выходный параметр этой функции -
массив T, первые N элементов которого содержат количества камешков, которые
проверяющая программа берет из кучек. Соответствие хода условиям игры
гарантируется.
Функцию PartTurn Ваша программа будет вызывать, чтобы сообщить
проверяющей программе свой ход. Запишите свой ход в первые N элементов
массива T.
Любая из этих функций возвращает 1, если все в порядке , или 0,
если возникла ошибка, и Ваша программа может прекращать работу.
На полученной Вами дискете будет модуль проверки (CHECK.*) и главный
модуль (NIM_KBD.*). Они предоставляются только для того, чтобы Вы могли быстро
начать работу над решением, не теряя время на технические проблемы. Модуль
CHECK выполняет считывание данных с клавиатуры, проверку ходов участника и
последовательности вызовов функции, но очень плохо играет. Жюри при
проверке будет использовать другой. Модуль NIM_KBD выполняет функции
модуля CHECK в нужной последовательности, но вместо вычисления следующего
хода участника читает его с клавиатуры. Ваша задача и состоит в том, чтобы
функция MakeTurn вычисляла следующий ход. Жюри не настаивает на использовании
упомянутых файлов, но Ваше решение должно корректно взаимодействовать с
модулем CHECK.
Примечание
При проверке среди тестов будут такие частичные случаи:
1) N = 2, K = 1; 2) N = 3, K = 1; 3) N > 3, K = 1.
Файлы на дискетах C C++ Pascal
Главный модуль NIM_KBD.C NIM_KBD.CPP NIM_KBD.PAS
Модуль проверки CHECK.C, CHECK.CPP, CHECK.PAS
CHECK.H CHECK.H
Файл проекта NIM.PRJ NIM.PRJ нет
Программа-решение - NIM.PAS, NIM.CPP или NIM.C.
Пример
N = 4, K = 2, First = 1, H = (3,4,5,6).
Участник: (1,1,0,0), осталось (2,3,5,6)
Жюри: (0,0,1,1), осталось (2,3,4,5)
Участник: (0,0,1,1), осталось (2,3,3,4)
Жюри: (1,1,0,0), осталось (1,2,3,4)
Участник: (0,0,0,4), осталось (1,2,3,0)
Жюри: (0,0,1,0), осталось (1,2,2,0)
Участник: (1,2,0,0), осталось (0,0,2,0)
Жюри: (0,0,2,0), осталось (0,0,0,0)
Выиграло жюри (но участник имел шанс !!!)
|
