[al-Khwārazmī])
- точный набор инструкций, описывающих порядок действий исполнителя для
достижения результата решения задачи за конечное время. В старой трактовке
вместо слова «порядок» использовалось слово «последовательность», но по мере
развития параллельности в работе компьютеров слово «последовательность» стали
заменять более общим словом «порядок». Это связано с тем, что работа каких-то
инструкций алгоритма может быть зависима от других инструкций или результатов
их работы. Таким образом, некоторые инструкции должны выполняться строго после
завершения работы инструкций, от которых они зависят. Независимые инструкции
или инструкции, ставшие независимыми из-за завершения работы инструкций, от
которых они зависят, могут выполняться в произвольном порядке, параллельно или
одновременно, если это позволяют используемые процессор и операционная система.
Ранее часто писали «алгорифм», сейчас такое
написание используется редко, но, тем не менее, имеет место (например,
Нормальный алгорифм Маркова).
Часто в качестве исполнителя выступает некоторый
механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма
необязательно относится к компьютерным программам, так, например, чётко
описанный рецепт приготовления блюда также является алгоритмом, в таком случае
исполнителем является человек.
Понятие алгоритма относится к первоначальным,
основным, базисным понятиям математики. Вычислительные процессы
алгоритмического характера (арифметические действия над целыми числами,
нахождение наибольшего общего делителя двух чисел и т. д.) известны
человечеству с глубокой древности. Однако, в явном виде понятие алгоритма
сформировалось лишь в начале XX века.
Частичная формализация понятия алгоритма
началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem),
которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации
были необходимы для определения эффективных вычислений или «эффективного
метода»; среди таких формализаций - рекурсивные функции Геделя - Эрбрана -
Клини 1930, 1934 и 1935 гг., λ-исчисление
Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга.
В методологии алгоритм является базисным понятием и получает качественно новое
понятие как оптимальности по мере приближения к прогнозируемому абсолюту. В
современном мире алгоритм в формализованном выражении составляет основу
образования на примерах, по подобию. На основе сходства алгоритмов различных
сфер деятельности была сформирована концепция (теория) экспертных систем.
Неформальное определение
Каждый алгоритм предполагает существование
начальных (входящих) данных и в результате работы приводит к получению
определенного результата. Работа каждого алгоритма происходит путем выполнения
последовательности некоторых элементарных действий. Эти действия называют
шагами, а процесс их выполнения называют алгоритмическим процессом. Таким
образом проявляется свойство дискретности алгоритма. Важным свойством
алгоритмов является массовость, или возможность применения к различным входным
данным. То есть, каждый алгоритм призван решать класс однотипных задач.
Необходимым условием, которому удовлетворяет алгоритм, является
детерминированность, или определенность. Это означает, что выполнение команд
алгоритма происходит по единому образцу и приводит к одинаковому результату для
одинаковых входных данных. Входные данные алгоритма могут быть ограничены
набором допустимых входных данных. Применение алгоритма к недопустимым входным
данным может приводить к тому, что алгоритм никогда не остановится или попадет
в тупиковое состояние (зависание), из которого не сможет выйти.
Формальное определение
Разнообразные теоретические проблемы математики
и ускорение развития физики и техники поставили на повестку дня точное
определение понятия алгоритма. Первые попытки уточнения понятия алгоритма и его
исследования осуществляли в первой половине XX века Алан Тьюринг, Эмиль Пост,
Жак Эрбран, Курт Гедель, Андрей Марков, Алонзо Чёрч. Было разработано несколько
определений понятия алгоритма, но впоследствии было выяснено, что все они
определяют одно и то же понятие (см. Тезис Чёрча - Тьюринга).
Формальные свойства алгоритмов
Различные определения алгоритма в явной или
неявной форме содержат следующий ряд общих требований:
Дискретность - алгоритм должен представлять
процесс решения задачи как последовательное выполнение некоторых простых шагов.
При этом для выполнения каждого шага алгоритма требуется конечный отрезок
времени, то есть преобразование исходных данных в результат осуществляется во
времени дискретно.
Детерминированность (определённость) - в каждый
момент времени следующий шаг работы однозначно определяется состоянием системы.
Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех
же исходных данных. В современной трактовке у разных реализаций одного и того
же алгоритма должен быть изоморфный граф. С другой стороны, существуют
вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего
состояния системы и генерируемого случайного числа. Однако при включении метода
генерации случайных чисел в список «исходных данных», вероятностный алгоритм
становится подвидом обычного.
Понятность - алгоритм для исполнителя должен
включать только те команды, которые ему (исполнителю) доступны, которые входят
в его систему команд.
Завершаемость (конечность) - при корректно
заданных исходных данных алгоритм должен завершать работу и выдавать результат
за конечное число шагов. С другой стороны, вероятностный алгоритм может и
никогда не выдать результат, но вероятность этого равна 0.
Массовость (универсальность) - алгоритм должен
быть применим к разным наборам исходных данных.
Результативность - завершение алгоритма
определёнными результатами.
Алгоритм содержит ошибки, если приводит к
получению неправильных результатов либо не даёт результатов вовсе.
Алгоритм не содержит ошибок, если он даёт
правильные результаты для любых допустимых исходных данных.
Наличие исходных данных и некоторого результата
Алгоритм - это точно определённая инструкция,
последовательно применяя которую к исходным данным, можно получить решение
задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в
качестве исходных данных. Например, в алгоритме деления вещественных чисел
делимое может быть любым, а делитель не может быть равен нулю. Алгоритм служит,
как правило, для решения не одной конкретной задачи, а некоторого класса задач.
Так, алгоритм сложения применим к любой паре натуральных чисел. В этом
выражается его свойство массовости, то есть возможности применять многократно
один и тот же алгоритм для любой задачи одного класса. Для разработки
алгоритмов и программ используется алгоритмизация - процесс систематического
составления алгоритмов для решения поставленных прикладных задач.
Алгоритмизация считается обязательным этапом в процессе разработки программ и
решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально
важны детерминированность, результативность и массовость, а также правильность
результатов решения поставленных задач. Алгоритм - это понятное и точное
предписание, исполнительно совершить последовательность действий, направленных
на достижение цели.
1.2 Сведения об игре «пятнашки»
Пятна́шки
- популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет
собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в
квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны
костяшек для набора из 15 элементов, соответственно в коробке остаётся
незаполненным одно квадратное поле. Цель игры - перемещая костяшки по коробке
добиться упорядочивания их по номерам, желательно сделав как можно меньше
перемещений.
Суть самой игры заключается в следующем:
- Игрок на экране видит табло, которое разбито на
16 клеток. В пятнадцати из них расположены неповторяющиеся цифры, в случайном
порядке от 1 до 15 и одна пустая.
В общем виде данное табло можно представить в
виде таблицы 1:
Таблица 1 - Образец
|
2
|
8
|
6
|
1
|
|
3
|
4
|
9
|
5
|
|
12
|
11
|
14
|
15
|
|
7
|
10
|
13
|
Игрок должен перемещать по одной клетки с цифрой
на пустое место.
- Так происходит до тех пор, пока пользователь не
выстроит последовательную комбинацию цифр (Таблица 2), и лишь после этого игрок
считается победителем.
Таблица 2 - Правильное заполнение табло
|
1
|
2
|
3
|
4
|
|
5
|
6
|
7
|
8
|
|
9
|
10
|
11
|
|
13
|
14
|
15
|
|
Математическое описание.
Пятнашки представляют собой классическую задачу
для моделирования эвристических алгоритмов. Обычно задачу решают через количество
перемещений и поиск манхеттенского расстояния между каждой костяшкой и её
позицией в собранной головоломке. Для решения используются алгоритмы наподобие
алгоритма A*.
Нерешаемая комбинация, предложенная Ноем
Чепменом - рисунок 1.
Рисунок - 1
Можно показать, что ровно половину из всех
возможных 1 307 674 368 000 (=15!) начальных положений пятнашек невозможно
привести к собранному виду: пусть квадратик с числом i расположен до (если
считать слева направо и сверху вниз) k квадратиков с числами меньшими i. Будем
считать ni = k, то есть если после костяшки с i-м числом нет чисел, меньших i,
то k = 0. Также введем число e - номер ряда пустой клетки (считая с 1).
Если сумма
является нечётной, то решения головоломки не
существует.
Для обобщённых пятнашек (с бо́льшим,
чем 15, количеством костяшек) задача поиска кратчайшего решения является
NP-полной.
Если допустить поворот коробки на 90 градусов,
при котором изображения цифр окажутся лежащими на боку, то можно перевести
неразрешимые комбинации в разрешимые (и наоборот). Таким образом, если вместо
цифр на костяшки нанести точки и не фиксировать положение коробки, то
неразрешимых комбинаций вообще не окажется.
2. Функциональное описание
В курсовой работе используются основные
возможности языка в работе со структурами, файлами, графикой.
В данной игре предполагалось создание:
1) интуитивно понятного интерфейса;
) скромного, но графически точного табло, где
осуществляется перемещение цифр;
) удобного для пользователя управления.
алгоритм комбинация игра число
Заключение
В ходе выполнения курсового проекта разработана
программа, реализующая игру «пятнашки».
Внешний вид окна программы представлен в
приложении А, исходный текст программы представлен в приложении Б.
Список использованных источников
1. «Delphi.
Программирование на языке высокого уровня» Фаронов В.В., СПб.: Питер, 2011 -
640с.: ил. [Текст]
2.
«Библия Delphi - 2-е издание» Фленов М., С.-Пб, БХВ-Петербург, 2008г. [Текст]
Приложение А
Основное окно программы на рисунке 2. Окно с
окончанием игры на рисунке 3.
Рисунок
2 - основное окно
Рисунок 3 - победа
Приложение Б
Листинг программы:main;
, Messages, SysUtils, Classes, Graphics,
Controls, Forms,, StdCtrls, Menus, XPMan, ExtCtrls;
= class(TForm): TMainMenu;: TMenuItem;:
TMenuItem;: TTimer;: TLabel;FormCreate(Sender: TObject);FormShow(Sender:
TObject);N1Click(Sender: TObject);N2Click(Sender: TObject);tmr1Timer(Sender:
TObject);ButClicked(Sender:
TObject);CreatFishkas();KillOldFihkas();position(const x, y: integer):
integer;victopia();
{ Private declarations }
{ Public declarations };
Tfish = TButton; // указываем тип фишек
= 80; // ширина фишки= 10; // растояние между
фишками= D + W; // растояние между "х" у фишек= 3; // размер поля
4х4= 1; M = 9; // размерность массива фишек= 10; POLEL = 10; //начальные
позиции поля фишек на форме= 'Fishka';
: TForm1;: array[N..M] of Tfish;: array[N..M] of
boolean;, zeroY: integer;: array[1..M, 1..2] of integer;:TDateTime;
{$R *.dfm}
//размер формы
FormSize;.Width := (POLEL * 2) + (L *
NXM);.Height := (L * NXM) + POLET +
90;.Lbl1.Left:=Round(Form1.Width/2)-35;.Lbl1.Top:=Form1.Height-90;;
TForm1.FormCreate(Sender: TObject);i, ty, lx:
integer;:=time;; i := 0;
// заполняем массив координатами на которые
будут случайным образом ставиться
// фишки при начале новой игры:= POLET; lx :=
POLEL;i := N to M do begin[i, 1] := lx;[i, 2] := ty;:= lx + L;i mod NXM = 0
then begin:= ty + L;:= POLEL;;;();;
TForm1.FormShow(Sender: TObject);();;
// клик по пункту меню - "новая игра"
TForm1.N1Click(Sender: TObject);();
();();:=time;;
{ сбрасывает все элементы массива в true,
массив отвечает за неповторяющиеся порядковые
номера фишек
которые выбираются случайным образом
нужно при иницилизации новой игры}
dump(): boolean;i: integer;:= 0;i := N to M
do[i] := true; ;;
//алгоритм выборки неповторяющихся значений
случайным образом
choose(): integer;i: integer;:= 0;:= random(M) +
1;sorseAr[result] = false do:= random(M) + 1;[result] := false;;
TForm1.CreatFishkas;
// НОВАЯ ИГРА, создание игрового поля, ty, lx,
ch: integer;;();
// But.Enabled:=false; BitBtn1.Enabled:=true;
BitBtn2.Enabled:=true;:= POLET; lx := POLEL;i := N to M do begin
[i] := Tfish.Create(Self);[i].Width :=
W;[i].Height := W;[i].Font.Size := 34;[i].Font.Name := 'Garamond Premr
Pro';[i].Font.Style := [fsBold];
:= choose(); // получаем случайным образом число
1-16, числа не повторяются
[i].Left := XYmatrix[ch, 1]; // получаем
координату Х[i].Top := XYmatrix[ch, 2]; // получаем координату У[i].Tag := ch;
// в Tag - текущее положение фишки[i].Name := prefix + inttostr(i);
i <> M then begin[i].Caption :=
inttostr(i);[i].OnClick := ButClicked;else begin // пустая кнопка[i].Caption :=
'';:= btn[i].Left; zeroY := btn[i].Top;;
[i].Parent := Self;
;;
// определяет позицию на которой стоит фишка в
данный момент по ее координатам
TForm1.position(const x, y: integer): integer;i:
integer;:= 0;:= -32;i := N to M do begin((XYmatrix[i, 1] = x) and (XYmatrix[i,
2] = y)) then begin:= i; break;;;;
TForm1.ButClicked(Sender: TObject);X, Y, ps:
integer;:= Tfish(Sender).left; Y := Tfish(Sender).Top;((X = zeroX + L) and (Y =
zeroY)) or
((X = zeroX - L) and (Y =
)) or
((X = zeroX) and (Y = zeroY + L)) or
((X = zeroX) and (Y = zeroY - L)) then begin
(Sender).Left := zeroX;(Sender).Top := zeroY;
(FindComponent(prefix + inttostr(M))).left :=
X;(FindComponent(prefix + inttostr(M))).top := Y;
:= position(zeroX, zeroY);ps <> -32
then(Sender).Tag := ps else('Ошибка в логике программы, координаты');
:= X; zeroY := Y;
(); // проверка - ПОБЕДА или играем дальше;;
// проверка - ПОБЕДА или играем дальше...
TForm1.victopia;i: integer; b: boolean;:= true;
i := 0;i := N to M - 1 dostrtoint(Tfish(FindComponent(prefix +
inttostr(i))).Caption) <>(FindComponent(prefix + inttostr(i))).Tag then:=
false; break;;;b then ShowMessage('ПОБЕДА! ТаДаМ))) Ваше
время:'+TimeToStr(Time-timtemp));;
TForm1.KillOldFihkas;
// уничтожаем кнопки-фишки, нужно перед началом
новой игрыi: integer;i := N to M do
(btn[i]);;TForm1.N2Click(Sender:
TObject);.Terminate();;
TForm1.tmr1Timer(Sender: TObject);
.Refresh;.Caption:=TimeToStr(Time-timtemp);;
end.