Государственный комитет Российской Федерации по высшему и среднеспециальному образованию

Красноярский Государственный Технический Университет

Курсовая работа

по курсу

Математическая логика и теория алгоритмов

Выполнил студент гр. ВТ27-4

Попов А.В.

Проверила:

Пестунова Т.М.

1998

Содержание.

1. Постановка задачи (стр.3).
2. Построение модели (стр.3).
3. Описание алгоритма (стр.4).
4. Доказательство правильности алгоритма (стр.7).
5. Блок-схема алгоритма (стр.8).
6. Описание переменных и программа (стр.9).
7. Расчёт вычислительной сложности (стр.11).
8. Тестирование (стр.11).
9. Список литературы (стр.12).

Постановка задачи.

Перечислить все способы расстановки n ферзей на шахматной доске n на n, при которых они не бьют друг друга.

Построение модели.

Очевидно, на каждой из n горизонталей должно стоять по ферзю. Будем называть k-позицией (для k = 0, 1,...,n) произвольную расстановку k ферзей на k нижних горизонталях (ферзи могут бить друг друга). Нарисуем "дерево позиций": его корнем будет единственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в (k+1)-позиции. Эти n позиций отличаются положением ферзя на (k+1)-ой горизонтали. Будем считать, что расположение их на рисунке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее.

Дерево позиций для n = 2

Данное дерево представлено только для наглядности и простоты представления для n=2.

Среди позиций этого дерева нам надо отобрать те n-позиции, в которых ферзи не бьют друг друга. Программа будет "обходить дерево" и искать их.
Чтобы не делать лишней работы, заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.

Точнее, назовем k-позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции.

Описание алгоритма.

Разобьем задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимых позиций.

Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева. Он умеет выполнять команды:

вверх_налево (идти по самой левой из выходящих вверх стрелок) вправо (перейти в соседнюю справа вершину) вниз (спуститься вниз на один уровень)

вверх_налево вправо вниз