Задача 1. Восемь ферзей нужно расставить на шахматной доске так, чтобы ни один ферзь не угрожал другому. Контрольный пример 15863724.


Чтобы посмотреть этот 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 результатов решения задачи с колонкой количества проверок
безопасности позиций

(см.контрольный пример)
.



Приложенные файлы

  • pdf 44239238
    Размер файла: 696 kB Загрузок: 0

Добавить комментарий