Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели



Скачать 38.94 Kb.
Дата26.07.2014
Размер38.94 Kb.
ТипЛабораторная работа
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НГТУ

Кафедра ПСиБД

Лабораторная работа № 1

по дисциплине СИИ

Факультет: ПМИ

Группа: ПМ - 73

Студенты: Безбородов Б.Е.

Преподаватели: Волкова В.М.,

Цильковский И.А.

Новосибирск 2011

Цель работы

Изучение основных стратегий решения задач. Приобретение навыков выбора адекватных стратегий в зависимости от типа задачи. Выбор инструмента для реализации этих стратегий. Применение базовых стратегий решения задач для программирования игр двух лиц с полной информацией.



Задание

Задача о ферзях. Задача состоит в отыскании всех расстановок N ферзей на пустой шахматной доске размера NxN, таких, в которых ни один из ферзей не находится под боем другого.



Представление в пространстве состояний

Будем представлять позицию на доске в виде 4-x списков:

X – координаты x

Y – координаты y

U – координаты восходящей диагонали

V – координаты нисходящей диагонали

Каждый такой элемент будет описывать то поле доски, на котором стоит соответствующий ферзь. Решение задачи сводится к отысканию списка координат (Y), удовлетворяющего требованию отсутствия нападения. Так как ферзи не могут находиться на вертикальных линиях более, чем по одному, то мы можем сразу зафиксировать первые координаты в списке, пронумеровав их согласно очередности координат в списке (поэтому будем искать только координату Y ).

Для решения задачи будем использовать поиск в глубину. Для этого необходимо представить задачу в пространстве состояний и выделить исходную и целевую точку в данном пространстве. В качестве исходной точки будем считать доску без ферзей. В качестве целевой точки – полный набор ферзей на доске (N штук), кроме того пространство состояний должно учитывать, что ферзи не бьют друг друга.

Вершины пространства состояний – позиции, в которых представлено несколько (возможно, 0) ферзей, расположенных в некотором допустимом порядке на шахматной доске (ни один из них не бьет другого).

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



Текст программы
solution(N, S):-

% область определения x,y

gen(1, N, Dxy),

Nu1 is 1-N,

Nu2 is N-1,

% область определения восходящей диагонали

gen(Nu1, Nu2, Du),

Nv2 is N+N,

% област определения нисходящей диагонали

gen(2, Nv2, Dv),

sol(S, Dxy, Dxy, Du, Dv).
sol([],[], _, _, _).

sol([Y|Ylist],[X|Dx1],Dy, Du, Dv) :-

% чтоб не повторялись

del(Y, Dy, Dy1),

U is X-Y,

del(U, Du, Du1),

V is X + Y,

del(V, Dv, Dv1),

sol(Ylist, Dx1, Dy1, Du1, Dv1).
% удаление

del(Item, [Item|List], List).

del(Item, [First|List], [First| List1]) :-

del(Item, List, List1).


% генерация

gen(N, N, [N]).

gen(N1, N2, [N1|List]):-

N1

gen(M, N2, List).

Результат

N = 8

N = 10

N = 12

P = [1, 5, 8, 6, 3, 7, 2, 4] ;

P = [1, 3, 6, 8, 10, 5, 9, 2, 4|...] ;

P = [1, 3, 5, 8, 10, 12, 6, 11, 2|...] ;

P = [1, 6, 8, 3, 7, 4, 2, 5] ;

P = [1, 3, 6, 9, 7, 10, 4, 2, 5|...] ;

P = [1, 3, 5, 10, 8, 11, 2, 12, 6|...] ;

P = [1, 7, 4, 6, 8, 2, 5, 3] ;

P = [1, 3, 6, 9, 7, 10, 4, 2, 8|...] ;

P = [1, 3, 5, 10, 8, 11, 2, 12, 7|...] ;

P = [1, 7, 5, 8, 2, 4, 6, 3] ;

P = [1, 3, 9, 7, 10, 4, 2, 5, 8|...] ;

P = [1, 3, 5, 11, 8, 10, 12, 4, 2|...] ;

P = [2, 4, 6, 8, 3, 1, 7, 5] ;

P = [1, 4, 6, 9, 3, 10, 8, 2, 5|...] ;

P = [1, 3, 6, 8, 11, 5, 12, 10, 4|...] ;

P = [2, 5, 7, 1, 3, 8, 6, 4] ;

P = [1, 4, 7, 10, 2, 9, 5, 3, 8|...] ;

P = [1, 3, 6, 11, 9, 4, 12, 10, 2|...] ;

P = [2, 5, 7, 4, 1, 8, 6, 3] ;

P = [1, 4, 7, 10, 3, 9, 2, 5, 8|...] ;

P = [1, 3, 6, 11, 9, 12, 5, 2, 4|...] ;

P = [2, 6, 1, 7, 4, 8, 3, 5] ;

P = [1, 4, 7, 10, 6, 9, 2, 5, 3|...] ;

P = [1, 3, 6, 12, 10, 2, 11, 5, 8|...] ;

P = [2, 6, 8, 3, 1, 4, 7, 5] ;

P = [1, 4, 7, 10, 8, 2, 5, 3, 6|...] ;

P = [1, 3, 7, 11, 2, 12, 10, 6, 4|...] ;

P = [2, 7, 3, 6, 8, 5, 1, 4] .

P = [1, 4, 7, 10, 8, 3, 5, 9, 2|...] .

P = [1, 3, 8, 2, 9, 12, 10, 5, 11|...] .

……………………………………..

……………………………………..

……………………………………..


Похожие:

Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа по химии. «p металлы». Косяк Анна Факультет: нук рлм группа: бмт2 12
Ознакомление со свойствами химических элементов, простыми веществами и соединениями бора и алюминия
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа по химии. «d металлы». Часть II косяк Анна Факультет: нук рлм группа: бмт2 12
Ознакомиться с такими металлами как железо, кобальт, никель (Fe, Co, Ni), являющимся d – элементами и изучить их свойства
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа по химии. «Определение жесткости воды». Косяк Анна Факультет: нук рлм группа: бмт2 12
Растворенные в воде компоненты находятся друг с другом в равновесии, образуя комплексы различного состава
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа №25 по дисциплине "Информатика" т ема : субд access. Создание многотабличной базы данных. Задание
Группа – содержит информацию о студентах
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЭвенки знают свой язык и культуру
Сибирского федерального университета. В июле группа исследователей, в состав которой входили преподаватели, аспиранты и студенты...
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа №1 по дисциплине «Сети ЭВМ и средства телекоммуникации» Утилиты tcp/ip алексашенков Д. В. Группа с-65
Цель работы: практически освоить работу с утилитами tcp/IP, необходимыми в следующих работах
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа №1 Работа в Oracle Database Express Edition 1 Лабораторная работа №6
Лабораторная работа Выполнение расчетов с использованием программирования в среде Visual Basic for Applications
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа №4 по дисциплине «Информатика» Арифметические задачи Группа: авт-010
Число называется совершенным, если оно равно сумме всех своих делителей, например, 6=1+2+3, 28=1+2+4+7+14. Найти все совершенные...
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа №17 по дисциплине " Методы и средства гидрометеорологических измерений". Устройство осциллографов
Устройство осциллографов. Лабораторная работа №17 по курсу “Гидрометеорологические измерения”. С. Петербург: рггму, 2002, 14 с
Лабораторная работа №1 по дисциплине сии факультет: пми группа: пм 73 Студенты: Безбородов Б. Е. Преподаватели iconЛабораторная работа №16 по дисциплине " Методы и средства гидрометеорологических измерений". Измерение радиоактивности
Лабораторная работа №16. Измерение радиоактивности. По дисциплине “Методы и средства гидрометеорологических измерении”. – С. Петербург.:...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org