Цель урока: изучить метод перебора с возвратом на примере задачи обхода лабиринта
Задачи:
- формировать умение составлять рекурсивный алгоритм для решения задачи методом перебора с возвратом
- развивать у учащихся познавательный интерес и критическое мышление
- развивать творческие способности
- прививать учащимся навыки самостоятельной и исследовательской работы
План урока
Организационный момент.
Изучение нового материала.
Практическая работа на компьютере.
Подведение итогов урока.
Домашнее задание.
Ход урока
1. Организационный момент
Учитель приветствует учащихся, отмечает отсутствующих, проверяет готовность учащихся.
2. Изучение нового материала
Задача обхода лабиринта. Постановка задачи. (Слайд 4).
<Рисунок1>
Имеется лабиринт прямоугольной формы. Нужно найти путь из заданной клетки (вход) в другую заданную клетку (выход). Ходы разрешается делать только по горизонтали и вертикали, и только по проходам. Гарантируется, что путь существует. Найти решение.
Учитель задает вопрос: Каким способом можно решить задачу? Учащиеся предлагают варианты решения, учитель их подводит к мысли о необходимости изучить метод Перебора с возвратом (backtrack) , общего метода упорядоченного перебора.
(Слайд 5)
Метод перебора с возвратом использует два правила:
- В каждой клетке выбирать еще не исследованный путь.
- Если из исследуемой клетки не ведут неисследованные пути, вернуться на одну клетку назад по последнему пройденному пути.
Перебор с возвратом применяется для решения комбинаторных задач, в которых приходится организовывать полный перебор возможных вариантов.
Перебор с возвратом особенно удобен для решения задач, требующих проверки потенциально большого, но конечного числа решений.
Идея метода - при поиске решения многократно делается попытка продолжить текущее частичное решение. Если расширение невозможно, происходит возврат к предыдущему более короткому частичному решению, и делается попытка его продолжить другим возможным способом.
Далее учитель объясняет суть метода поиска решения на примере (Слайд 6), знакомит с общей схемой рекурсивного перебора (Слайд 7).
Итак, метод решения задачи выбран.
Начинается следующий этап решения задачи.
Учитель задает вопросы ученикам «Что нужно задать, чтобы решить задачу?», «Какие еще нужны данные для решения задачи?», «Как представить результат?». Учитель и ученики обсуждают возможные варианты ответов.
Учитель задает вопросы учащимся «Как представить лабиринт?», «Как обозначить стены и проходы?», «Как оградить лабиринт внешними стенами?», «Как организовать смещение по лабиринту?» и др. Учащиеся самостоятельно или при помощи наводящих вопросов отвечают на поставленные вопросы. (Слайды 8-10).
Далее учащиеся составляют словесный алгоритм решения задачи.
Следующий слайд знакомит их с рекурсивным алгоритмом решения задачи. Учащиеся читают готовую программу и комментируют ее. (Слайды 11-15).
program pattern;
{$mode objfpc}{$H+}
uses
CRT,FileUtil; {Подключаем библиотеку, содержащую функцию UTF8ToConsole()}
const maxn=20;
dx: array [1..4] of integer = (-1, 0, 1, 0);
dy: array [1..4] of integer = ( 0, -1, 0, 1);
var
a: array [0..maxn+1, 0..maxn+1] of integer;
n, m, { размеры лабиринта }
sx, sy, { начальное положение }
fx, fy: integer;
procedure init;
var Labirint : Text;
i, j: integer;
begin
for i := 0 to maxn+1 do { барьеры }
for j := 0 to maxn+1 do
a[i, j] := -1;
read(n, m, sx, sy, fx, fy);
AssignFile(Labirint,'lab.txt');
Reset(Labirint);
for i := 1 to m do
for j := 1 to n do
read(Labirint,a[i, j]);
CloseFile(Labirint);
end;
procedure print_labirint;
var
i, j: integer;
begin
writeln;
for i := 1 to n do
begin
for j := 1 to m do
write(a[i, j]:4);
writeln;
end;
end;
procedure search(x, y, k: integer);
var
i: integer;
begin
a[y, x] := k; { запись варианта }
if (x = fx) and (y = fy) then { решение найдено }
begin
print_labirint; { вывод решения }
Write(UTF8ToConsole('Нажмите ...'));
ReadLn;
halt;
end
else
for i := 1 to 4 do { перебор всех вариантов }
if a[y+dy[i], x+dx[i]] = 0 then { вариант подходит }
search(x+dx[i], y+dy[i], k+1); { рекурсивный вызов }
a[y, x] := 0; { стирание варианта }
end;
{$IFDEF WINDOWS}{$R pattern.rc}{$ENDIF}
begin
init;
search(sx, sy, 1);
Write(UTF8ToConsole('Нажмите ...'));
ReadLn
end.
В заключении учитель предлагает следующие задания:
- Назовите достоинства и недостатки метода перебора с возвратом
- Назовите недостатки рассмотренного решения
- Как можно их исправить?
- Как можно переформулировать задачу?
Учащиеся отвечают на вопросы.
Учитель предлагает задания для самостоятельной работы:
- Выполните предложенный алгоритм и проверьте на различных тестах.
- Попытайтесь доработать алгоритм, устранив недостатки.
- Решите с помощью метода перебора с возвратом следующую задачу:
Сгенерировать обход конем шахматной доски, так чтобы покрыть всю область.
3. Практическая работа на компьютере
Учащиеся должны выполнить первое и второе задание для самостоятельной работы. (Второе задание не является обязательным и по желанию учащихся может быть выполнено дома).
4. Подведение итогов
Учитель подводит итоги урока, отмечает учащихся, успешно справившихся с работой.
5. Домашнее задание
Выполнить третье задание для самостоятельной работы.
Источники
- Материалы Проекта «Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в Приволжском федеральном округе» по направлению «Дополнительная подготовка школьников по дисциплине «Информатика и информационные технологии»». Раздел «Перебор с возвратом». Л.П. Жильцова. 2011 год (Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Нижегородский государственный университет им. Н.И. Лобачевского)
- Мозговой М.В. Занимательное программирование: Самоучитель. – СПб.: Питер, 2004.
- http://borisvolfson.h11.ru/book/backtracking.php