Алгоритмы и алгоритмические языки - Программирование, компьютеры и кибернетика контрольная работа

Задача о восьми ферзях как широко известная задача по расстановке фигур на шахматной доске. Характеристика алгоритмов решения задачи для доски 8х8. Рассмотрение особенностей программы, использующей алгоритм Лас-Вегаса, проведения статистического анализа.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
" А лгоритмы и алгоритмические языки"
задача ферзь алгоритм статистический
Задача о восьми ферзях -- широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Какими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу, т.е. никакие два не стояли на одной вертикали, горизонтали и диагонали и сколько таких способов?» Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.
В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8?8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».
Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.
Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.
Конечная цель, поставленная перед решающим задачу, может формулироваться в нескольких вариантах:
1) Построить одно, любое решение задачи.
2) Аналитически доказать, что решение существует.
4) Построить все возможные решения.
5) Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N?N клеток (при этом при 1 3 на доске NxN можно расставить n не угрожающих друг другу ферзей.
На доске 4x4 существует одна основная расстановка, причем дважды симметрическая: a2, b4, c1, d3, т.е. всего имеется два решения. На доске 5x5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Общее число расстановок равно десяти, причем из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполняют все поля доски 5х5.
Заметим, что в общем случае N расстановок (решений задачи) могут заполнить при наложении всю доску NхN только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.
Классическим решением задачи N ферзей является прямой перебор с отсечением. Прямой перебор заключается в испытании на конфликтность всех возможных комбинаций. Например, на доске существуют N^2 позиции, таким образом, мы имеем N^2 возможных позиций для первого ферзя, N^2-1 для второго и т.д. Общее число возможных расположений всех ферзей составляет (N^2, N) = (N^2)!/((N^2-N)! * n!). Если перебрать все эти позиции, можно найти все правильные решения. Для n=10 число всех позиций равно ~1.73*10^13.
Поскольку в неконфликтном расположении на одной горизонтали может стоять только один ферзь, то мы можем ограничиться расстановкой одного ферзя на первой горизонтали, второго - на второй и т.д. Это дает нам N возможных положений для каждого ферзя и N^N различных расположений. Для N=10 это будет 10^10. Заметим, что на каждой вертикали также может быть только один ферзь: i-й ферзь имеет только n-i+1 возможных положений, поскольку предыдущие i-1 ферзей уже заняли i-1 вертикалей. Теперь общее количество возможностей сократилось до N! или 3.6*10^6 вариантов для n=10.
И последний способ уменьшить количество возможных вариантов - контролировать положение ферзей на одной диагонали. Хотя это просто запрограммировать, бывает трудно дать оценку количества перебираемых вариантов.
2 .2 Алгоритмы Лас-Вегаса или Алгоритм поиска с возвратом
Если решать более общую задачу об N ферзях, то такой перебор вариантов даже с использованием описанных выше сокращений будет весьма долго работать уже при N = 20, так как 20! = 2.433?10^18.
Эвристический алгоритм (эвристика) -- алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве практически значимых случаев. Эвристический алгоритм -- это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно
редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.
Для решения поставленной задачи эвристический алгоритм будет выглядеть так:
1) Разделить N на 12 и запомнить остаток (N будет равно 8 для задачи о восьми ферзях).
2) Занести в список все четные числа от 2 до N по порядку.
3) Если остаток равен 3 или 9, перенести 2 в конец списка.
4) Добавить в список все нечетные числа от 1 до N по порядку, но, если остаток равен 8, перевернуть пары соседних чисел (например: 3, 1, 7, 5, 11, 9, …).
5) Если остаток равен 2 и N ? 3, поменять местами 1 и 3, затем, если N ? 5, перенести 5 в конец списка.
6) Если остаток равен 3 или 9, переместить 1 и 3 (именно в этом порядке, а не в котором они сейчас) в конец списка.
7) Разместить ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем поместить следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т.д..
8 ферзей (остаток 8): 2, 4, 6, 8, 1, 3, 5, 7.
14 ферзей (остаток 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
15 ферзей (остаток 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
20 ферзей (остаток 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
Анализируя данные алгоритмы нужно отметить, что их эффективность напрямую зависит от размера «доски». При небольшом размере по эффективности преобладает Алгоритм Лас-Вегаса. А при увеличении размера преобладают рекуррентный и эвристический. Но, т.к. эвристический правилен не при всех значениях N, то самым эффективным из предложенных является рекуррентный.
1.М. Гарднер Математические досуги. - 2-е изд., испр. и доп. М: Мир, 2000. - 444 с.
2.Дж. Макконел Основы современных алгоритмов. - 2-е изд., М: Техномир, 2004. - 368c.
3.Е. Корнилов Программирование шахмат и других логических игр. - 1-ое изд., C-Пб: БХВ-Петербург, 2005. - 272c.
4.А. Левитин Введение в анализ и разработку алгоритмов - М: Вильямс, 2006. - 576c.
5.Вирт Н. Алгоритмы и структура данных - C-Пб.; Невский Диалект, 2005. - 352с.
6.А. Ахо, Дж. Хопфорт, Дж. Ульман Построение и анализ вычислительных алгоритмов - М: Мир, 1979. - 135c.
7.Д. Кнут Искусство программирования т.2 - М:1968. - 788c.
I , q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 , n : integer ;
function boy ( c : integer ) : boolean ;
res :=res or ( ( c=j ) or ( q [ c ]=q [ j ] ) or
( ( c+q [ c ] )=( j+q [ j ] ) ) or ( ( c-q [ c ] )=( j-q [ j ] ) ) ) ;
for i :=1 to 8 do writeln ( '(' , i , ',' , q [ i ] , ') ' , boy ( i ) ) ;
Определение понятия алгоритмов, принципы их решения людьми и всевозможными техническими устройствами. Применение компьютера для решения задач. Особенности использования метода последовательного укрупнения при создании шахматной доски по алгоритму. презентация [1,1 M], добавлен 06.02.2012
Задача о кратчайшем пути как одна из важнейших классических задач теории графов. Общий обзор трех наиболее популярных алгоритмов для решения задачи о кратчайшем пути. Написание программы, которая реализует алгоритм Дейкстры и алгоритм Форда-Беллмана. курсовая работа [2,1 M], добавлен 23.06.2014
Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ. презентация [441,5 K], добавлен 19.10.2014
Методика и основные этапы разработки программы, которая бы наглядно продемонстрировала варианты размещения ферзей на шахматной доске, удовлетворяя правилам задачи. Исследование свойств расстановок мирных ферзей. Написание текста программы и ее листинг. контрольная работа [81,1 K], добавлен 29.04.2011
Нормальный алгоритм Маркова. Тезис Маркова и машина Тьюринга. Гипотеза теории алгоритмов. Алгоритмически неразрешимые проблемы. Задача эквивалентности двух слов в ассоциативном исчислении. Задача распознавания выводимости. Линейная оценка сложности. методичка [57,0 K], добавлен 06.07.2009
Обзор алгоритмов решения задачи: точные методы, генетический и жадный алгоритмы. Характеристика жадного алгоритма: его описание, анализ точности приближения, вычислительной сложности. Программная реализация и проверка корректности и быстродействия. курсовая работа [228,7 K], добавлен 14.10.2017
Алгоритм решения функциональной задачи. Выбор системы команд специализированной ЭВМ. Форматы команд и операндов. Содержательные графы микропрограмм операций АЛУ. Разработка объединенной микропрограммы работы АЛУ. Закодированные алгоритмы микропрограмм. курсовая работа [265,5 K], добавлен 17.11.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Алгоритмы и алгоритмические языки контрольная работа. Программирование, компьютеры и кибернетика.
Доклад по теме Озеро Байкал (Доклад)
Реферат На Тему Українська Національна Кухня
Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников
Доклад по теме Тайна Котельнича разгадана
Реферат Философско Правовой Либерализм
Курсовая работа по теме Поляризация электромагнитных волн и поляризационная оптика
Курсовая работа по теме Медицинское страхование в России, проблемы его развития
Доклад: Айсберги
Учебное пособие: Выписка из рабочей программы и методические указания к выполнению лабораторных работ втаблице приведен перечень лабораторных работ и объем часов для каждой работы, а также распределение по семестрам
Реферат: Strange Things About City Life Essay Research
Реферат: Россия и мировой экономический кризис 2008 года
Учебное Пособие На Тему Постійний Електричний Струм
Курсовая работа по теме Вторичные ресурсы в автомобильном хозяйстве и требования к ним
Курсовая работа по теме Анализ структуры издержек производства продукции промышленных предприятий и методики их формирования
Реферат: Методические рекомендации по их выполнению и оформлению. Криминалистика
Реферат: Внешний и внутренний долг России
Реферат: GenerationX Essay Research Paper Davis 1 Tommy
Курсовая работа по теме Теория возникновение и виды денег
Реферат по теме Виникнення й розвиток соціальної психології в першій половині ХХ століття
Юридическая Служба Реферат
Английский парк в Мюнхене - Культура и искусство презентация
Дослідження передавальних характеристик коаксіального шунта - Коммуникации, связь, цифровые приборы и радиоэлектроника курсовая работа
Африканский континент - География и экономическая география презентация