Номер варианта 44. Нужно к 31.03.

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

Математическая логика и теория алгоритмов Содержание. Постановка задачи. Построение модели. Описание алгоритма Доказательство правильности алгоритма Блок-схема алгоритма Описание переменных и программа Расчета вычислительной сложности Испытаний библиография Постановка задачи.

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

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

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

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

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

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

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

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

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

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

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

справа перейдите на соседа справа=)

вниз (спуститься вниз на один уровень)

вверх_налево

справа

ниже

и проверки, соответствующие возможности выполнить каждую из команд, называемые "есть_сверху", "есть_справа", "есть_снизу" (последняя истинна всюду, кроме корня). Пожалуйста, обратите внимание, что команда "вправо" позволяет перейти лишь к "родному брату", но не к "двоюродному".