Методика решения алгоритмической задачи с величинами
Основные типы учебных алгоритмических задач.
Комментарий:
Для закрепления основных понятий, связанных с определением алгоритма, полезно рассмотреть с учениками несколько заданий следующего содержания:
Выполнить роль исполнителя: дан алгоритм, формально исполнить его;
Определить исполнителя и систему команд для данного вида работы;
В рамках данной системы команд построить алгоритм;
Определить необходимый набор исходных данных для решения задачи.
В качестве примера задачи первого типа можно использовать алгоритм игры Баше, рассматриваемый в учебниках [1, стр. 60 № 8а)].
В книгах правила игры определены так: В игре используются 11, 16, 21, 26, ... предметов. За один ход можно брать от 1 до 4 предметов. Проигрывает тот игрок, который берет последний предмет.
Рассматривается алгоритм, благодаря которому всегда выигрывает игрок, берущий предметы вторым.
Задача 2.
«Разгадать загадку» алгоритма, т.е. объяснить, почему второй игрок всегда выигрывает?
Задача 3.
Составить алгоритм, по которому игрок, делающий ход вторым, может выиграть в том случае, если не ошибается.
Возможный диалог:
Деятельность педагога |
Деятельность ученика |
Состояние доски |
- Почему игрок, начинающий вторым всегда выигрывает? |
Существует выигрышная тактика, которая позволяет выигрывать |
|
- Давайте выявим «выигрышную» тактику? |
|
|
- Что дано в задаче? |
16 предметов
|
Дано 16 предметов |
- Что нам еще известно в задаче? |
Игроки по очереди вводят число от 1 до 4
|
n от 1 до 4 А: ввод числа от 1 до 4 В: ввод числа от 1 до 4 |
_ Что нам надо получить в итоге? |
- Проигрывает тот, кто берет последний предмет. |
Остался 1 предмет. В: ввод числа 1 Игра закончена. |
- Как мы достигнем того, чтобы второй игрок сделал ход последним? - «выигрышный» алгоритм игры Баше можно получить, если рассуждать «с конца игры», то есть рассмотреть сначала позицию перед последним ходом |
- надо чтобы перед последним ходом второго игрока остался 1 предмет предмета |
Если осталось N = 1 предметов, то В: взять n предметов (N =1)
|
- Сколько предметов должно остаться на предпоследнем ходу второго игрока? |
- Для выигрыша надо оставить противнику перед его последним ходом n + 1 предмет. Тогда, сколько бы он ни взял (больше n брать нельзя), своим ходом вы забираете последний предмет. |
Зарисовать предметы N + 1 2(N + 1) 3 (N + 1) |
- Что можно сказать о действиях игроков |
- они повторяются |
|
- До каких пор будут повторяться действия? |
Пока не останется один предмет |
Пока N >1
|
- Какую команду мы можем использовать? |
пока |
нц пока кц |
Как мы узнаем, что игра закончилась? |
Останется один предмет |
|
Какую команду мы можем применить, чтобы сообщить о количестве оставшихся предметах? |
вывод |
Вывод N |
Задание
Давайте составим алгоритм в виде блок схемы.
Возможный диалог:
Учитель: Что необходимо вспомнить, чтобы решить задачу?
Ученик: Описание величин: типы, виды величин; команда присваивания; команды алгоритмического языка: нц-пока-кц.
Учитель: Какие величины мы используем в данном алгоритме?
Ученик: Общее количество предметов; количество предметов, которые берет первый игрок за один ход; количество предметов, которые берет компьютер за один ход.
Учитель: Определите имя, тип и значение этих величин
Ученики:
N – общее количество предметов; вещ, N = 16.
b – количество предметов, которые берет первый игрок за один ход; вещ, b от 1 до 4.
a – количество предметов, которые берет компьютер за один ход; вещ, a от 1 до 4.
Учитель: Запишите последовательность действий, которые выполняют игроки.
Ученики:
И – игрок
К – компьютер
Комментарий: Заполнить таблицу.
Этапы |
команды |
состояние |
К: задает 16 предметов
|
N:=16 |
N:=16 |
И: берет b предметов
|
b:=n |
|
К: берет (5 – n) предметов
|
a:=5 – n |
|
К: количество предметов уменьшается на 5
|
N:=N – 5 |
N:=11 |
И: берет b предметов
|
b:=n |
|
К: берет (5 – n) предметов
|
a:=5 – n |
|
К: количество предметов уменьшается на 5
|
N:=N – 5 |
N:=6 |
И: берет b предметов
|
b:=n |
|
К: берет (5 – n) предметов
|
a:=5 – n |
|
К: количество предметов уменьшается на 5
|
N:=N – 5 |
N:=1 |
И: берет 1 предмет. Конец игре |
b:=n |
N:=0 |
Учитель: Какой цикл можно использовать для упрощения записи алгоритма
Ученик: Цикл пока