Логические и стратегические задачи, формализация условий

Разбор домашнего задания. Темы предполагаются для самостоятельного освоения с разбором на следующем занятии.

Пример: формализация ввода для задачи 2.2

• Количество камней в кучках хранится в словаре H (индекс — номер кучки, начиная с 1)

  • Начальное значение задаётся списком через запятую в первой строке ввода

• Каждый тип хода описывается отдельной строкой как модификация H правилами вида индекс:новое_значение

  • Если за один ход изменяются несколько кучек, правила записываются в одну строку через запятую

  • Если правила параметрические, список A соответствует списку параметров, следующему после символа ; в конце всех правил (специальная переменная I означает для краткости A[0])

• Условие конца игры и определение победителя задаются в виде формул, разделённых символом ;. В конце этой строки стоит .

• Далее пользователь вводит номер правила и параметры (целые числа в виде списка через пробел), а программа выводит результат хода, свой ход и результат своего хода, либо объявляет победителя

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

Итого для 2.2:

3, 4
I:H[I]*2
I:H[i]+4
игра

Домашнее задание

1. Имеется логическая задача (из пробного варианта ЕГЭ по информатике и ИКТ):

   • Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:
   • Володя: «Это сделал Саша».
   • Аня: «Володя лжет!»
   • Егор: «Маша разбила».
   • Саша: «Аня говорит неправду!»
   • Рома: «Разбила либо Маша, либо Нина...»
   • Маша: «Это я разбила!»
   • Нина: «Маша не разбивала!»
   • Коля: «Ни Маша, ни Нина этого не делали».
   • Олег: «Нина не разбивала!»
     • Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?
   • Придумать способ формализации условий подобных задач, и написать программу, на вход которой подаётся формализованное условие, а на выходе — ответ.

2. Имеется задача на исследование стратегии (из пробного варианта ЕГЭ по информатике и ИКТ):

   • Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет 4 камня в какую-то кучу. Игрок, после хода которого общее число камней в двух кучах становится больше 25, проигрывает.
     • Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
   • Написать программу, на вход которой подаётся 5 параметров: начальное количество камней в кучках, множитель, приращение и рубежное количество камней (для приведённой выше задачи: 3, 4, 2, 4, 25), после чего программа либо успешно играет в игру (на каждом ходе вводится номер кучки и номер действия, выводится состояние кучек)
   • Вариант: кучек произвольное количество, типов ходов также произвольное количество, условие конца игры и определения победителя задаются отдельно (см. выше формализацию)

     • Решение (формализацию пришлось дополнить, см. текст программы): stones.py

3. Решить классическую задачу: написать непобедимую программу игру в «крестики-нолики 3x3». Условие: нельзя за одну игру вычислять выигрышность одной и той же позиции более одного раза.

   • ttt.py

CategoryClass CategoryVmsh