Магистерская диссертация на тему: Постановка задачи. Построение модели. Описание алгоритма. Доказательство правильности алгоритма

Введение

Построенная по описанному алгоритму программа при различных n выдаёт следующие данные:

Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости от n количества решений (R)

Оглавление

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

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

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

- Доказательство правильности алгоритма

- Блок-схема алгоритма

- Описание переменных и программа

- Расчёт вычислительной сложности

- Тестирование

- 9. Список литературы

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

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

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

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

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

Список литературы

1. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988.

2. Евстигнеев В.А. Применение теории графов в программировании. - М.:Наука, 1984.

3. Основной алгоритм находился на BBS "Master оf Univercity" в файле shen.rar в файловой области "Bardak" (тел. 43-27-03; время работы 21.00 - 7.00; FTN адрес - 2:5090/58).