Поиск оптимального алгоритма решения задачи, и его реализация в ОС Windows. Разработка программы, генерирующей все конфигурации 8 ферзей на шахматной доске из 8x8 полей, так, чтобы ни один ферзь не мог взять другого ферзя. Проблемы хранения результатов.
Аннотация к работе
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) КАФЕДРА ТЕХНИЧЕСКИХ И ИНФОРМАЦИОННЫХ СРЕДСТВ СИСТЕМ УПРАВЛЕНИЯПри создании программ необходимо учитывать особенности их реализации на разных языках. От хорошего специалиста требуется не только знания языков программирование, но и знание оптимальных алгоритмических решений. Выбор оптимального алгоритма влияет на скорость выполнения и на затраты ресурсов компьютера. Не мало важным фактором является знание операционной системы для которой создается программа. Проведенная предварительно оценка необходимых затрат ресурсов для реализации данной программы с учетом конкретного опыта осуществления прикладных задач в различных языках программирования обосновывает данный выбор на взгляд автора.Задача состоит в том, чтобы сделать программу, генерирующую все конфигурации восьми ферзей на шахматной доске из 8x8 полей, так, чтобы ни один ферзь не мог взять никакого другого ферзя. Как результат, мы можем заключить, что каждая горизонталь будет содержать ровно одного ферзя. b) Аналогично мы заключаем, что каждая вертикаль будет содержать ровно одного ферзя. c) Есть 15 "восходящих" диагоналей, каждая из которых содержит не более одного ферзя, т. е. 8 восходящих диагоналей содержат ровно по одному ферзю, 7 восходящих диагоналей являются пустыми. d) Аналогично заключаем, что 8 нисходящих диагоналей содержат ровно по одному ферзю, а 7 являются пустыми. e) Если задана какая-то непустая конфигурация ферзей, в которой никакие два ферзя не могут взять друг друга, то удаление любого одного из этих ферзей приведет к появлению конфигурации, сохраняющей это свойство. Если мы начинаем с какого-то решения (которое является конфигурацией восьми ферзей из множества B1) и удаляем одного ферзя, то мы получаем конфигурацию семи ферзей из множества B1; удаление еще одного ферзя приведет снова к конфигурации из множества B1, и мы можем продолжать этот процесс, пока шахматная доска не опустеет. Для каждой позиции ферзя 0 ферзь 1 будет перемещаться слева направо в горизонтали 1 - перескакивая через клетки, которые находятся под угрозой ферзя 0; - для каждой комбинированной позиции первых двух ферзей ферзь 2 перемещается по горизонтали 2 слева направо, пропуская все клетки, находящиеся под угрозой предыдущих ферзей, и т. д.У нас есть 8 элементов массива X и в каждом может быть значения от 1 до 8, и нам нужно эти 8 элементов представить в виде одной переменной. Поскольку у нас 8 элементов которые могут принимать значения от 1 до 8, попробуем взять восьмизначное десятичное число в котором порядковый номер цифр будет соответствовать номеру элементов массива X, а числа соответственно значениям элементов массива X. Пронумеруем цифры в нашем числе слева на право. Таким образом для того чтобы получить значение i-того разряда искомого числа необходимо значение Х [i] * на его весовой коэффициент. Поскольку мы будем использовать номер элемента массива x в качестве номера весового коэффициента числа, то мы будем последовательно к Fr прибавлять значение x умноженное на z.Разобрав выше почти все аспекты написания нашего проекта, остается только уделить внимание его графической части.Delphi изначально предлагает готовое «окно» и библиотеку компонентов, что позволяет программисту уделить основное время на написание кода программы, а не ее графической части. На основном окне программы мы разместили стандартную кнопку и компонент LISTBOX позволяющий отображать список строк и выбирать из них нужную. Кнопка в нашем окне служит для запуска расчетов, LISTBOX для вывода найденных координат и выбора какой-либо из них для графического отображения на доске.x: array [0..8] of integer; //ферзи col: array [0..7] of boolean; //горизонтали up: array [-7..7] of boolean; //восходящие диагонали down: array [0..14] of boolean; //нисходящие диагонали fr:array [0..91] of integer;//для хранения координат ферзей mas: array[1..8] of integer; // x массив клеток доски mas1: array[1..8] of integer; // y массив клеток доски xr: array [1..8] of integer; //координаты для рисования ферьзей nfr: integer = 0; //для массива ферзей номер implementation Form1.Canvas.Rectangle(xn,y,xn 300,y 300); //рамка для букв Form1.Canvas.Pen.Color:=c1; //цвет рамки Form1.Canvas.Rectangle(xn 29,y 29,xn 271,y 271); //рамка доски form1.Canvas.Font.Size:=14; Form1.Canvas.Brush.Color:=CLBLACK; //рисование закрашенного ферзя form1.Canvas.Polygon([Point(x-7,y 25),Point(x-17,y), Point(x-7,y 10),Point(x,y), Point(x 7,y 10),Point(x 17,y),Point(x 7,y 25)]);Эта работа позволила автору познакомится и попробовать овладеть несколькими приемами в программировании. Один из которых имеет устоявшиеся название «обратное отслеживание». Идею обратного отслеживания можно применить к большому числу разных на первый взгляд задач.