Автор не бросает своих заказчиков даже по истечении гарантийного срока.
Информация о работе
Подробнее о работе
Расставить на шахматной доске размера NxN M ферзей так, чтобы ни один ферзь не угрожал другому.
- 9 страниц
- 2010 год
- 666 просмотров
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Расставить на шахматной доске размера NxN M ферзей так, чтобы ни один ферзь не угрожал другому.
1. Исходная постановка задачи.
2. Анализ и пример решения задачи.
2.1. Анализ задачи.
2.2. Пример решения задачи.
3. Спецификация программы.
3.1. Исходные данные.
3.1.1. Исходные данные, их расположение.
3.1.2. Ограничения на исходные данные.
3.2. Выходные данные.
4. Структуры данных и алгоритмы.
4.1. Алгоритмы.
4.2.Модель структур данных.
5. Код программы
6. Вывод
1. Исходная постановка задачи.
Расставить на шахматной доске размера NxN M ферзей так, чтобы ни один ферзь не угрожал другому.
2. Анализ и пример решения задачи.
2.1. Анализ задачи.
Для решения задачи используем алгоритм перебора с возвратом (backtracking). Для осуществления перебора заметим, что каждый ферзь должен стоять на отдельной вертикали, горизонтали и диагонали.
2.2. Пример решения задачи.
Пусть дана шахматная доска 5х5. Одно из решений имеет вид:
*
*
*
*
*
3. Спецификация программы.
3.1. Исходные данные.
3.1.1. Исходные данные, их расположение.
В качестве исходных данных рассматриваем размерность N шахматной доски, вводимую пользователем.
3.1.2. Ограничения на исходные данные.
Размерность доски не должна быть 2х2 и 3х3.
3.2. Выходные данные.
В качестве выходных данных пользователь получает все возможные расстановки ферзей на доске.
4. Структуры данных и алгоритмы.
4.1. Алгоритмы.
Алгоритм поиска с возвращением.
ЦИКЛ ПОКА ( k > 0 ) {пока не все решения найдены}
ЦИКЛ ПОКА (Sk ¹ Æ)
{продвижение вперед}
ak := элемент из Sk; {выбор очередного элемента из Sk}
Sk := Sk - {ak} {формируем новое множество для выбора}
count := count + 1 {увеличиваем число просмотренных вершин}
ЕСЛИ ((a1,…, ak-1,ak) – решение)
ТО фиксировать решение
ИНАЧЕ { переход к следующему уровню }
k := k + 1;
вычислить Sk;
КОНЕЦ ЦИКЛА
k := k-1 {переход на предыдущий уровень}
КОНЕЦ ЦИКЛА {все решения найдены; count – число обследованных узлов}
4.2.Модель структур данных.
Решение задачи хранится в виде элементов массива a, где ai – номер горизонтали на i-ой вертикали, на пересечении которых стоит ферзь.
5. Код программы
6. Вывод:
Ответы, выдаваемые программой, совпадают с ожидаемыми. Программа работает правильно. В результате выполнения работы получена программа, которая в полной мере выполняет поставленные задачи.
лекции по СИАОД и все такое)
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
