Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Тема
4
:
Алгоритмы с возвратом. ЗАДАЧА О
ВОСЬМИ ФЕ
РЗЯХ
ПРОДОЛЖИТЕЛЬНОСТЬ:
4
час
а
аудиторных занятий и
2
час. самостоятельной
работы.
Задание 1.
Напишите и отладьте программу
задачи о
восьми ферзях
,
выдающую одно из возможных решений
.
Задача 1.
Восемь ферзей нужно расставить
на шахматной доске так, чтобы ни
один ферзь не угрожал другому.
Контрольны
й
пример
1 5 8 6 3 7 2 4
1.
Проверьте правильность работы программы в соответствии с контрольным
приме
ром
.
2.
На
рисуйте шахматную доску и расположение на ней восьми ферзей в
соответствии с решением.
Задание
2
.
Напишите и отладьте программу
задачи о
восьми ферзях
,
выдающую
все возможные решения
.
Задание
3
.
Видоизмените программу так, чтобы вслед за
печатью всех
решений
она печатала количество возможных решений
.
Задание
4
.
Видоизмените программу так, чтобы
она печатала лишь первые
12 решений.
Задания
для самостоятельной работы
Задание
5
.
Видоизмените
программу так, чтобы она
выдавала
12 первых
решений
и колич
ество проверок безопасности позиции для всех
этих
решений задачи о восьми ферзях.
Контрольный пример
(печать 12
-
ти первых решений)
Контрольный пример
(печать 12
-
ти первых решений
с указанием
количества проверок н
а безопасность
)
Методические указания для преподавателя
Можн
о напомнить алгоритм
получения одного решения
:
PROCEDURE
Try
ing
(
i
:
INTEGER
)
;
BEGIN
инициализация выбор
а
положения
i
-
го ферзя
;
;
REPEAT
выбор очередного
положения
;
IF
безопасное
THEN
поставить ферзя
;
IF
i
8
THEN
Try
ing(
i
+ 1)
;
IF
неудача
THEN
убрать
ферзя
END
END
END
UNTIL
удача
OR
(
м
ест
больше нет)
END
Также м
ожн
о напомнить алгоритм
получения
всех
решени
й
:
PROCEDURE
Try
ing
(
i
:
INTEGER
)
;
VAR k: INTEGER;
BEGIN
FOR k := 1 TO m DO
В
ыбор
k
-
го кандидата
;
IF
подходит
THEN
его запись
;
IF
i
n
THEN
Try
ing(
i
+ 1)
ELSE
печать
решения
END
;
стирание
записи
END
END
END
Содержание отчета:
1.
Ли
стинг программы
задачи о восьми ферзях, выдающей
одно решение
задачи.
2.
Результат решения задачи.
3.
Рисунок с расположением ферзей на
шахматном
поле в соответствие с
решение
м
.
4.
Листинг программы задачи о восьми ферзях, выдающую все решения
задачи.
5.
Листинг программы задачи о восьми ферзях, выдающую
первые 12
решений
задачи.
6.
Первые 12 результатов решения задачи.
7.
Листинг программы задачи о восьми ферзях, выдающ
ую
12 первых
решени
й
задачи и количество проверок безопасности позиций
для этих
решений
.
8.
Первые 12 результатов решения задачи с колонкой количества проверок
безопасности позиций
(см.контрольный пример)
.
Приложенные файлы
