Логические и стратегические задачи, формализация условий
Разбор домашнего задания. Темы предполагаются для самостоятельного освоения с разбором на следующем занятии.
? тема по Linux
?? необязательная тема
Пример: формализация ввода для задачи 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 игра
Домашнее задание
? теоретическое задание
? новая тема
Имеется логическая задача (из пробного варианта ЕГЭ по информатике и ИКТ):
- Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:
- Володя: ?Это сделал Саша?.
- Аня: ?Володя лжет!?
- Егор: ?Маша разбила?.
- Саша: ?Аня говорит неправду!?
- Рома: ?Разбила либо Маша, либо Нина...?
- Маша: ?Это я разбила!?
- Нина: ?Маша не разбивала!?
- Коля: ?Ни Маша, ни Нина этого не делали?.
- Олег: ?Нина не разбивала!?
- Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?
- Придумать способ формализации условий подобных задач, и написать программу, на вход которой подается формализованное условие, а на выходе ? ответ.
Имеется задача на исследование стратегии (из пробного варианта ЕГЭ по информатике и ИКТ):
- Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет 4 камня в какую-то кучу. Игрок, после хода которого общее число камней в двух кучах становится больше 25, проигрывает.
- Кто выигрывает при безошибочной игре обоих игроков ? игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
- Написать программу, на вход которой подается 5 параметров: начальное количество камней в кучках, множитель, приращение и рубежное количество камней (для приведенной выше задачи: 3, 4, 2, 4, 25), после чего программа либо успешно играет в игру (на каждом ходе вводится номер кучки и номер действия, выводится состояние кучек)
- Вариант: кучек произвольное количество, типов ходов также произвольное количество, условие конца игры и определения победителя задаются отдельно (см. выше формализацию)
Решение (формализацию пришлось дополнить, см. текст программы): stones.py
- Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет 4 камня в какую-то кучу. Игрок, после хода которого общее число камней в двух кучах становится больше 25, проигрывает.
- Решить классическую задачу: написать непобедимую программу игру в ?крестики-нолики 3x3?. Условие: нельзя за одну игру вычислять выигрышность одной и той же позиции более одного раза.