1.6 Алгоритм программы
Рисунок 12 Алгоритм работы программы в целом
Рисунок 13 Построение МК согласно "индийскому" алгоритму
Рисунок 14 Общий алгоритм построения МК с четным размером стороны (методРаус-Болла)
Приведенные здесь схемы алгоритмов являются формализованным описанием математических алгоритмов, описанных ранее естественным языком. Для разработки программы, функционирующей по данному алгоритму, необходимо оформить блоки ввода вывода данных как процедуры, обрабатывающие работу пользователю с элементами управления, а процесс вычислений в ходе работы алгоритма представить в виде последовательности инструкций Delphi.
2. Описание программы
Программа работает по стандартной схеме работы Windows-приложений: приложение управляется событиями.
При создании приложения StringGrid, отображающий МК, изначально не содержит данных.
Он заполняется после построения МК.
Программа функционирует следующим образом:
1) пользователь вводит в текстовое поле размер стороны квадрата
2) пользователь нажимает на кнопку «Заполнить» - происходит проверка размера стороны квадрата на то, что размер больше либо равен 2-м
3) если условие не выполняется, то выдается сообщение об ошибке и процедура заканчивается
4) если условие выполняется, то далее происходит проверка размера стороны на четность-нечетность и построение МК в соответствии с одним из описанных выше алгоритмов
Основными процедурами/функциями приложения являются:
№ п.п. |
Название процедуры и ее параметры |
Назначение |
1 |
procedure Button1Click(Sender:TObject);
|
Процедура обрабатывает нажатие на кнопку «Заполнить», выполняя построение МК заданного размера и заполняяStringGrid данными |
2 |
procedure N2Click(Sender: TObject);
|
Обработка выбора пункта «Меню» выход меню «Файл» - выход из приложения |
3 |
procedure N5Click(Sender: TObject);
|
Обработка выбора пункта «О программе» выход меню «Помощь» - открывает диалог с информацией о программе и разработчике |
4 |
procedure N4Click(Sender: TObject);
|
Обработка выбора пункта «Помощь» выход меню «Помощь» - вызов справки приложения |
5 |
procedure Edit1KeyDown(Sender:TObject; var Key: Word; Shift: TShiftState);
|
Вызов контекстной справки при нажатии клавиши «F1», когда элемент управления, предназначенный для ввода размера стороны МК имеет фокус ввода |
6 |
procedure Edit2KeyDown(Sender:TObject; var Key: Word; Shift: TShiftState);
|
Вызов контекстной справки при нажатии клавиши «F1», когда элемент управления, предназначенный для вывода «магической» суммы имеет фокус ввода |
7 |
procedure Button1KeyDown(Sender:TObject; var Key: Word; Shift: TShiftState);
|
Вызов контекстной справки при нажатии клавиши «F1», когда кнопка запуска процедуры построения МК имеет фокус ввода |
8 |
procedure sgKeyDown(Sender: TObject;var Key: Word; Shift: TShiftState); |
Вызов контекстной справки при нажатии клавиши «F1», когдаStringGrid имеет фокус ввода |
Выход из приложения может быть осуществлен 3-мя способами:
1) «крестик» в системном меню
2) кнопка с надписью «Close»
3) пункт «Выход» меню «Файл»
Приложение представлено двумя формами: Form1 и Form2. Первая форма отображает данные приложения и предназначена для ввода данных пользователем. Вторая форма отображает информацию о программе и ее разработчике.
Опишем подробно порядок решения поставленных в ходе выполнения курсовой работы задачи.
Для решения поставленной задачи загрузим систему Delphi (версию 6 или выше), определим заголовок формы: "Магические квадраты" (свойство Caption), поместим на нее компонент панель Panel1, выбрав в ее свойстве Align значениеalBottom, чтобы панель занимала нижнюю часть формы, и очистим ее свойствоCaption.
Разместим на панели слева редактор Edit1 для ввода порядка n квадрата, запишем число 3 в качестве начального значения его свойства Text; над редактором расположим метку label1, установив в ее свойство Caption строку "Введите n", далее на панели поместим кнопку Button1, определив слово "Заполнить" в качестве ее свойства Caption.
Правее поместим на панель еще один редактор Edit2 для вывода магической суммы квадрата, очистив его свойство Text. Над ним поместим метку Label2 со строкой "Магическая сумма" в качестве значения ее свойства Caption.
В правой части панели поместим кнопку BitBtn1 (со страницы компонентAdditional), в качестве ее свойства Kind выберем значение bkClose, тогда щелчок мышью по этой кнопке автоматически позволит выйти из программы.
Теперь на форму поместим компонент TStringGrid (со страницы Additional), установим в его свойство Align значение alClient, что позволит занимать всю свободную часть формы для построения магического квадрата, очистим свойствоCaption, для свойства Name выберем строку sg, в качестве размеров клетки таблицы DefaultColWidth и DefaultRowHight возьмем числа соответственно 40 и 20, что позволит разместить на форме магический квадрат порядка 16, для свойствFixedCols и FixedRows определим значение 0, чтобы в таблице не было заголовочных столбцов и строк.
Добавим в приложение меню и создадим обработчики его команд.
На этом закончим конструирование формы.
Вся основная работа по созданию магического квадрата порядка n<=255 будет связана с вводом числа n и нажатием кнопки "Заполнить" (Button1). Для этого создадим обработчик события OnClick для этой кнопки. Вывод полученного магического квадрата выполним с помощью обработчика события OnShow для формы:
procedure TForm1.FormShow(Sender: TObject); begin button1.Click; end;
Чтобы написать процедуру Button1Click, надо алгоритмы построения магических квадратов перевести на язык Delphi. Клетки магического квадрата порядка n будем обозначать парами целых чисел (i,j), где i - номер строки, j - номер столбца, на пересечении которых находится данная клетка. Числа i и j будем называть координатами клетки. При этом строки квадрата нумеруем сверху вниз, а столбцы - слева направо. Для описания магического квадрата в программе используем массив: var a: array [1..mn,1..mn] of integer, где константа mn=255 (максимальное значение числа n).
Наиболее простым методом построения магических квадратов нечетного порядка является видимо самый древний "индийский" алгоритм:
1. Числа от 1 до n2 поочередно вписываются в клетки квадрата.
2. Число 1 вписывается в среднюю клетку верхней строки.
3. Если число k вписано в клетку (i,j) и k делится на n, то число k+1 вписывается в клетку (i+1,j).
4. Если число k вписано в клетку (i,j) и k не делится на n, то число k+1 вписывается в клетку (i-1,j+1). Если при этом правило требует вписать число в клетку с координатой i=0 или j>n, то число вписывается в клетку с координатой i=n или соответственно j=1.
Фрагмент процедуры Button1Click для построения нечетного квадрата можно написать так:
if n mod 2=1 then {построение квадрата нечетного порядка} begin i:=1; j:=(n div 2)+1; {вычисляем координаты клетки для 1} for k:=1 to n*n do begin a[i,j]:=k; if k mod n =0 then {правило 3} i:=i+1 else {правило 4} begin dec(i);
inc
(j); if i=0 then i:=n; if j>n then j:=1 end; end; end ┘
Для построения квадратов четного порядка применим метод Раус- Бола, описанный в [14]. Он начинается с того, что квадрат заполняется слева направо и сверху вниз числами от 1 до n2 в их естественном порядке. Затем выполняются перестановки чисел в некоторых клетках, после чего квадрат становится магическим. Сначала рассмотрим случай "четно-четного" n=2m=4r, где m и r - натуральные числа. Правила построения четно-четного магического квадрата таковы:
1. Разделить заполненный числами от 1 до n2 квадрат на четыре квадрата порядка m осями симметрии.
2. В каждой строке и столбце верхнего левого квадрата порядка m отметить rклеток ( всего mr клеток). Это можно сделать, применив "шахматный" порядок, начиная с клетки (1,2).
3. Для каждой из отмеченных клеток (i,j) отметить симметричную ей относительно вертикальной оси клетку (i, n-j+1), и содержимое каждой из m2отмеченных клеток переставить с содержимым соответствующей центрально-симметричной ей клетки.
После этих перестановок получится магический квадрат.
Соответствующий фрагмент процедуры Button1Click для построения четно-четного квадрата можно написать так:
if n mod 4=0 then {построение четно-четного квадрата} begin k:=1; {заполняем квадрат числами от 1 до n2} for i:=1 to n do for j:=1 to n do begin a[i,j]:=k; inc(k) end; j:=2; m:=n div 2;{отмечаем клетки в верхнем левом квадрате в шахматном порядке и выполняем перестановки } for i:=1 to m do for k:=1 to m div 2 do begin if j=m+1 then j:=2 else if j=m+2 then j:=1; s:=n-i+1; b:=n-j+1; t:=a[i,j]; a[i,j]:=a[s,b]; a[s,b]:=t; t:=a[i,b]; a[i,b]:=a[s,j]; a[s,j]:=t; j:=j+2; end; end┘
Рассмотрим теперь случай n=2m, где m=2r+1 - нечетное число. Если m>1, то магические квадраты порядка n существуют и называются "четно-нечетными". Построение четно-нечетного магического квадрата производится аналогично построению четно-четного квадрата, но в этом случае применяется три типа перестановок чисел в клетках. Правила построения четно-нечетного магического квадрата порядка n=2m, где m=2r+1>1 таковы:
1. Разделить заполненный числами от 1 до n2 квадрат на четыре квадрата порядка m осями симметрии.
2. В левом верхнем квадрате порядка m выделить 3 группы клеток, пометив их знаками +, - и | соответственно. В каждой строке и каждом столбце нужно выделить r клеток первой группы. Это можно сделать, выделив первые r клеток в первой строке и затем сдвигать на 1 клетку вправо соответствующую группу клеток в следующих строках. Клеток второго и третьего типа надо выделить по одной в каждой строке и каждом столбце. В качестве клеток второй и третьей групп можно взять клетки, расположенные на диагоналях, начинающихся с r+1 и r+2 клеток первой строки и направленных вправо и вниз.
3. Для клеток первой группы находим симметричные клетки относительно вертикальной оси, помечаем их тоже знаком + и содержимое каждой из 2mг таких отмеченных клеток обмениваем с содержимым соответствующей ей центрально-симметричной клетки.
4. Содержимое каждой из m клеток, отмеченных знаком минус, обмениваем с содержимым симметричной относительно горизонтальной оси клетки.
5. Содержимое каждой из m клеток третьей группы обмениваем с содержимым симметричной относительно вертикальной оси клетки. После этих перестановок получится четно-нечетный магический квадрат.
Рассмотрим, например, случай n=10. В этом случае m=5, r=2. Ниже на левой таблице показана разметка левого верхнего квадрата порядка 5 и магический квадрат порядка 10, построенный по указанным правилам:
|
|
Рисунок 17 Построение четно-нечетного МК порядка 10
Соответствующий фрагмент процедуры Button1Click для построения четно-нечетного квадрата можно написать так:
if (n mod 4 =2 ) and (n<>2) then {построение четно-нечетного квадрата} begin k:=1; {заполняем квадрат числами от 1 до n2} for i:=1 to n do for j:=1 to n do begin a[i,j]:=k; inc(k) end; r:=(n div 2 -1) div 2; m:=n div 2; {перестановка клеток первого типа} for i:=1 to m do begin j:=i; for k:=1 to r do begin if j>m then j:=1; s:=n-i+1; b:=n-j+1; t:=a[i,j]; a[i,j]:=a[s,b]; a[s,b]:=t; t:=a[i,b]; a[i,b]:=a[s,j]; a[s,j]:=t; inc(j) end; end; {перестановка клеток второго типа} i:=1; j:=r+1; for k :=1 to m do begin if j>m then j:=1; s:=n-i+1; t:=a[i,j]; a[i,j]:=a[s,j]; a[s,j]:=t; inc(i); inc(j) end; {перестановка клеток третьего типа} i:=1; j:=r+2; for k:=1 to m do begin if j>m then j:=1; b:=n-j+1; t:=a[i,j]; a[i,j]:=a[i,b]; a[i,b]:=t; inc(i); inc(j) end; end┘
Очевидно, при n=2 магический квадрат построить нельзя. В этом случае используем глобальную логическую переменную p, присвоив ей начальное значение true. Если n=2, положим p=false и в этом случае выведем в окно редактора Edit2 строку "не существует". Описание константы mn и переменной pпоместим в начале раздела implementation модуля формы:
const mn=16; var p:boolean=true;
При выводе магического квадрата на форму в таблицу sg нужно учесть, что нумерация строк и столбцов в этом компоненте по умолчанию начинается с нуля и первый индекс клетки таблицы sg является индексом столбца. При n=2 в клетках таблицы можно поместить число 0, чтобы было понятно, что магический квадрат не существует.
Приведем теперь полностью текст процедуры Button1Click:
procedure TForm1.Button1Click(Sender: TObject); var n,i,j,k,s,t,b,r,m:integer; a:array[1..mn,1..mn] of integer; begin Edit1.SetFocus; {подготовка окна к вводу нового значения n} n:=StrToInt(Edit1.Text); Sg.Colcount:=n; Sg.Rowcount:=n; if n mod 2=1 then {построение квадрата нечетного порядка} begin i:=1; j:=(n div 2)+1; for k:=1 to n*n do begin a[i,j]:=k; if k mod n =0 then i:=i+1 else begin dec(i);inc(j); if i=0 then i:=n; if j>n then j:=1 end; end; end else if n mod 4=0 then {построение четно-четного квадрата} begin k:=1; for i:=1 to n do for j:=1 to n do begin a[i,j]:=k; inc(k) end; j:=2; m:=n div 2; for i:=1 to m do for k:=1 to m div 2 do begin if j=m+1 then j:=2 else if j=m+2 then j:=1; s:=n-i+1; b:=n-j+1; t:=a[i,j]; a[i,j]:=a[s,b]; a[s,b]:=t; t:=a[i,b]; a[i,b]:=a[s,j]; a[s,j]:=t; j:=j+2; end; end else if n<>2 then {построение четно-нечетного квадрата} begin k:=1; for i:=1 to n do for j:=1 to n do begin a[i,j]:=k; inc(k) end; r:=(n div 2 -1) div 2; m:=n div 2; {перестановка клеток первого типа} for i:=1 to m do begin j:=i; for k:=1 to r do begin if j>m then j:=1; s:=n-i+1; b:=n-j+1; t:=a[i,j]; a[i,j]:=a[s,b]; a[s,b]:=t; t:=a[i,b]; a[i,b]:=a[s,j]; a[s,j]:=t; inc(j) end; end; {перестановка клеток второго типа} i:=1; j:=r+1; for k :=1 to m do begin if j>m then j:=1; s:=n-i+1; t:=a[i,j]; a[i,j]:=a[s,j]; a[s,j]:=t; inc(i); inc(j) end; {перестановка клеток третьего типа} i:=1; j:=r+2; for k:=1 to m do begin if j>m then j:=1; b:=n-j+1; t:=a[i,j]; a[i,j]:=a[i,b]; a[i,b]:=t; inc(i); inc(j) end; end else p:=false; if p then begin for i:=1 to n do for j:=1 to n do Sg.cells[j-1,i-1]:=IntToStr(a[i,j]); Edit2.Text:=IntToStr((1+n*n)*n div 2); Edit1.SetFocus end else {магический квадрат со стороной=2 не существует} begin for i:=1 to n do for j:=1 to n do Sg.cells[j-1,i-1]:=IntToStr(0); Edit2.Text:='не существует'; p:=true; Edit1.SetFocus end; end;
3. Описание применения
Для запуска программы необходимо:
1) операционная система семейства Windows (98/2000/Millenium/XP)
2) CPU 700 MHz и выше
3) 128 Мб оперативной памяти
4) От 1-го Мб свободного места на HDD
Для установки программы необходимо переписать ее файл «Project1.exe» и прилагающиеся файлы справки («myhelp.hlp» и «contents.cnt») в одну директорию на жестком диске.
Программа запускается обычным для среды Windows способом.
После запуска программы пользователь видит ее главное окно:
Рисунок 18 Начальное состояние программы
Для построения МК со стороной размера n необходимо ввести значение n в соответствующее поле ввода и нажать кнопку «Заполнить».
Таблица, занимающая большую часть окна программы, будет заполнена числами, стоящими в ячейках МК. В поле с надписью «Магическая сумма» будет выведено значение «магической» суммы для построенного квадрата.
Для повторного построения МК такого же порядка необходимо снова нажать кнопку «Заполнить».
Для построения МК другого порядка необходимо выполнить те же действия, что были описаны выше, предварительно введя новое значение n.
Для получения помощи по работе программы можно воспользоваться пунктом меню «Помощь» меню «Помощь». Будет показана справка программы. Кроме того, можно получить контекстную помощь по работе определенных элементов управления программы. Для этого необходимо, чтобы элемент, по назначению которого должна быть получена подсказка, имел фокус ввода (был выделен серой рамкой). После получения требуемым элементом фокуса необходимо нажать клавишу «F1» для получения оперативной контекстной помощи.
Для того, чтобы установить фокус ввода на кнопке, необходимо нажимать клавишу «Tab» до тех пор, пока требуемая кнопка не получит фокус.
Работу выполнила |
Студентка ФИТУ 3-4а Погосян Светлана Ковалевская Татьяна |
Работу принял |
Доц. каф. ИИСиТ Воробьев С.П. |
Дата |
12.09.14 |