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

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

  • {o} — тема по Linux

  • <!> ­— необязательная тема

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

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

Итого для 2.2:

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

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

  • {i} — теоретическое задание

  • {*} — новая тема

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

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

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

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


CategoryClass CategoryVmsh

LecturesVMSH/2011-04-20 (последним исправлял пользователь FrBrGeorge 2011-05-11 14:43:48)