Презентация для урока информатики "Решение олимпиадных задач. Игра Баше"

Пример игры Баше для 13 карандашей ( 4N+1)

Таблица перехода из одного класса в другой

Количество

взятых

предметов

Классы предметов, в зависимости от остатка при делении n на 4

1

4m

4m+3

2

4m+1

4m+2

3

4m

4m+2

4m+1

4m+1

4m+3

4m+3

4m+2

4m+2

4m

4m+3

4m+1

4m

Операнды, используемые для составления алгоритмов и программ и зависимость между ними

• N – число предметов
• P – число предметов, взятых первый раз первым игроком P = (N-1) mod 4
• Y - число предметов, взятых вторым игроком
• C – число предметов, взятых первым игроком
• Y + C = 4 – зависимость между Y и C
• N – C – Y – число оставшихся предметов после очередных ходов
• Н = 1 если ход делает первый игрок
• Н = 2 если ход делает второй игрок

Два варианта алгоритма задачи Баше

• Начинает игру первый игрок (человек или компьютер), игра прерывается, если при заданном количестве предметов N , первый игрок при правильной игре выиграть не может.
• Второй игрок (человек) выбирает, кто делает первый ход, игра продолжается даже если при правильной стратегии для данного количества предметов первый игрок (человек или компьютер) выиграть не может.

Алгоритм решения первого варианта задачи Баше

1 шаг

Попросите Вашего партнера назвать количество предметов N , если он назвал неверное число N , попросите выбрать другое и идти на ШАГ 2

Алгоритм решения первого варианта задачи Баше

2 шаг

Найти остаток от деления N – 1 на 4

P:=(N-1) mod 4

и идти на шаг 3

Алгоритм решения первого варианта задачи Баше

3 шаг

Сравнить P с 0. Если P = 0 , то сообщить партнеру что при правильной игре вы выиграть не можете, прекратить игру и идти на ШАГ 12

Если P 0 то идти на ШАГ 4

Алгоритм решения первого варианта задачи Баше

4 шаг

Сообщить «Я делаю первый ход» и идти на ШАГ 5

Алгоритм решения первого варианта задачи Баше

5 шаг

N:= N – C

Сообщить «Я беру С предметов»

Идти на ШАГ 6

Алгоритм решения первого варианта задачи Баше

6 шаг

N:= N – C

Сообщить «Осталось N предметов»

Идти на ШАГ 7

1 то сообщение «Ваш ход» Идти на ШАГ 8" width="640"

Алгоритм решения первого варианта задачи Баше

7 шаг

Сравнить N с 1, если N то идти на ШАГ 11

Если N 1 то сообщение «Ваш ход»

Идти на ШАГ 8

Алгоритм решения первого варианта задачи Баше

8 шаг

Вывод «Сколько предметов Вы берете?»

Y = количество предметов взятых вторым

(Если он взял неверное (больше 3) – попросить взять еще раз)

Идти на ШАГ 9

Алгоритм решения первого варианта задачи Баше

9 шаг

Высчитать 4 - Y

Вывод «Я беру 4 – Y предметов»

Идти на ШАГ 10

Алгоритм решения первого варианта задачи Баше

10 шаг

Высчитать N:= N-4

Вывод «Осталось N предметов»

Идти на ШАГ 7

Алгоритм решения первого варианта задачи Баше

11 шаг

Вывод «Ваш ход. Вы проиграли!»

Идти на ШАГ 12

Алгоритм решения первого варианта задачи Баше

12 шаг

Вывод «Хотите сыграть еще?»

Если да, то идти на ШАГ 1, если нет, то на ШАГ 13

Алгоритм решения первого варианта задачи Баше

13 шаг

Закончить игру

Блок-схемы алгоритма игры Баше (второй вариант)

• Алгоритм MoveK

• Алгоритм MoveI

Блок-схемы алгоритма игры Баше (второй вариант)

• Блок-схема основного алгоритма игры Баше