На этом шаге мы рассмотрим несколько заданий и приведем их решения.
Приведем несколько примеров решения задач.
Задание 1. Мэри и Джон решили сыграть в игру с n камешками. Каждый игрок может удалить один, три или четыре камешка за раз. Выигрывает тот, кто забирает последние камешки. Каждый из игроков может победить, если при его ходе остаётся один, три или четыре камешка. Если же осталось два камешка, то это приводит к проигрышу, так как можно забрать только один из двух камешков. Если камешков больше четырёх, Мэри решила, что будет забирать всякий раз по четыре камешка, если это возможно, тогда как Джон решил забирать по одному камешку. Реализуйте две взаимно-рекурсивные функции, моделирующие игру соперников и возвращающие 1 в случае победы Джона и 0 в случае победы Мэри. Чья стратегия лучше, если 1 ≤ n ≤ 100? Считайте, что начать игру может любой игрок.
Раскрыть/скрыть решение и комментарии.
Эта задача очень похожа на задачу, приведенную на 132 шаге, но здесь есть некоторые особенности. Приведем сначала текст программы.
Вот текст программы:
Задание 1.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
def play_Mary(n): if n in [1, 3, 4]: return 0 elif n > 4: # Мэри убирает четыре камня return play_John(n - 4) # Ход переходит к Джону else: # Мэри убирает один камень return play_John(n - 1) # Ход переходит к Джону def play_John(n): if n in [1, 3, 4]: return 1 else: # Джон убирает один камень return play_Mary(n - 1) # Ход переходит к Мэри playMary = 0 # Количество побед Мэри playJohn = 0 # Количество побед Джона for i in range(1, 101): rez = play_Mary(i) # Мэри ходила первой print(i, 'камней. Ход Мэри: ', end='') if rez == 1: print('Джон победил. Ход Джона: ', end='') playJohn += 1 else: print('Мэри победила. Ход Джона: ', end='') playMary += 1 rez = play_John(i) # Джон ходил первым if rez == 1: print('Джон победил.') playJohn += 1 else: print('Мэри победила.') playMary += 1 # Итоговый результат print('Побед Мэри:', playMary, 'Побед Джона:', playJohn) |
Ниже представлен результат ее выполения, из которого можно сделать вывод, что стратегия Джона работает лучше: у него побед больше.
1 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 2 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 3 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 4 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 5 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 6 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 7 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 8 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 9 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 10 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 11 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 12 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 13 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 14 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 15 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 16 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 17 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 18 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 19 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 20 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 21 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 22 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 23 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 24 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 25 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 26 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 27 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 28 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 29 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 30 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 31 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 32 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 33 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 34 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 35 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 36 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 37 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 38 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 39 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 40 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 41 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 42 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 43 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 44 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 45 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 46 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 47 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 48 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 49 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 50 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 51 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 52 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 53 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 54 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 55 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 56 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 57 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 58 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 59 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 60 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 61 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 62 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 63 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 64 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 65 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 66 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 67 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 68 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 69 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 70 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 71 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 72 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 73 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 74 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 75 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 76 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 77 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 78 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 79 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 80 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 81 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 82 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 83 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 84 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 85 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 86 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 87 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 88 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 89 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 90 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 91 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 92 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 93 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 94 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 95 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 96 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 97 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. 98 камней. Ход Мэри: Джон победил. Ход Джона: Джон победил. 99 камней. Ход Мэри: Мэри победила. Ход Джона: Джон победил. 100 камней. Ход Мэри: Джон победил. Ход Джона: Мэри победила. Побед Мэри: 81 Побед Джона: 119
При очередном количестве камней каждый игрок ходит первым. Таким образом сеансов игры в сумме в два раза больше.
Кратко прокомментируем реализованные взаимно-рекурсивные функции.
В отличие от игры, приведенной на 132 шаге, функции должны возвращать 1 в случае победы Джона и 0 в случае победы Мэри, поэтому очередное обращение к функции помещено в оператор return, например:
return play_John(n - 1) # Ход переходит к Джону ,
Со следующего шага мы начнем рассматривать выполнение программы.
