Алгоритмы генерации магических квадратов (стр. 4 из 5)
| 64 | 02 | 03 | 61 | 60 | 06 | 07 | 57 |
| 09 | 55 | 54 | 12 | 13 | 51 | 50 | 16 |
| 17 | 47 | 46 | 20 | 21 | 43 | 42 | 24 |
| 40 | 26 | 27 | 37 | 36 | 30 | 31 | 33 |
| 32 | 34 | 35 | 29 | 28 | 38 | 39 | 25 |
| 41 | 23 | 22 | 44 | 45 | 19 | 18 | 48 |
| 49 | 15 | 14 | 52 | 53 | 11 | 10 | 56 |
| 8 | 58 | 59 | 5 | 4 | 62 | 63 | 1 |
Константа этого магического квадрата равна 260, что подтверждается вычислением контрольных сумм элементов по строкам, столбцам и главным диагоналям.
2.3 Выводы
Существование общего алгоритма построения магических квадратов невозможно. Однако существуют частные алгоритмы, которые с увеличением порядка дают стремящееся к бесконечности число магических квадратов. Это частные методы составления магических квадратов, порядок которых является экспонентой 2 и квадратов нечетного порядка.
Глава 3. Программная реализация магических квадратов
Программная реализация основных магических квадратов основывается на уже известных словесных алгоритмах математиков и философов. Обычно это квадратная матрица, четная или нечетная. Также существует индивидуальный алгоритм заполнения каждого квадрата- или бесчисленного множества квадратов одного вида, но разных порядков. Рассмотрим некоторые из них.
3.1 Программная реализация квадратов нечетного порядка
Магические квадраты нечетного порядка можно построить с помощью метода французского геометра 17 в. А.де ла Лубера. Рассмотрим этот метод на примере квадрата 5-го порядка (рис. 3.1). Число 1 помещается в центральную клетку верхней строки. Все натуральные числа располагаются в естественном порядке циклически снизу вверх в клетках диагоналей справа налево. Дойдя до верхнего края квадрата (как в случае числа 1), продолжаем заполнять диагональ, начинающуюся от нижней клетки следующего столбца. Дойдя до правого края квадрата (число 3), продолжаем заполнять диагональ, идущую от левой клетки строкой выше. Дойдя до заполненной клетки (число 5) или угла (число 15), траектория спускается на одну клетку вниз, после чего процесс заполнения продолжается.[10]
Рис. 3.1
Ниже рассмотрим листинг программы, которая реализует данный квадрат на языке Паскаль.
progam algMR;
uses crt;
const n=5;
type mr:array[1..n,1..n]of integer;
var a:mr; b,i,j:integer;
begin
clrscr;
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;
i:=1;j:=(n div 2)+1;b:=1;
repeat
if i=n+1 then i:=1;if i=0 then i:=n;
if j=n+1 then j:=1;
if a[i,j]=0 then begin a[i,j]:=b;i:=i-1;j:=j+1;b:=b+1; end
else begin i:=i+1;a[i,j]:=b; b:=b+1;i:=i-1;j:=j+1;end;
until b=n;
for i:=1 to n do
begin
for j:=1 to n do
write(' ',a[i,j]);
writeln;
end;
end.
В программе использовался конечный массив элементов магического квадрата, что позволяет реализовать демонстрацию данного магического квадрата на уроках информатики в школе или ВУЗах.
3.2 Программная реализация квадратов четного порядка
Метод Ф.де ла Ира (1640–1718) основан на двух первоначальных квадратах. На рис. 2 показано, как с помощью этого метода строится квадрат 5-го порядка. В клетку первого квадрата вписываются числа от 1 до 5 так, что число 3 повторяется в клетках главной диагонали, идущей вправо вверх, и ни одно число не встречается дважды в одной строке или в одном столбце. То же самое мы проделываем с числами 0, 5, 10, 15, 20 с той лишь разницей, что число 10 теперь повторяется в клетках главной диагонали, идущей сверху вниз (рис. 2,б). Поклеточная сумма этих двух квадратов (рис. 2,в) образует магический квадрат. Этот метод используется и при построении квадратов четного порядка.[10]
Рис. 2
Ниже рассмотрим листинг программы, которая реализует данный квадрат на языке Паскаль.
progam algMR;
uses crt;
const n=5;
type mr:array[1..n,1..n]of integer;
var a,d,c:mr; b,i,j,z,k:integer;
begin
clrscr;
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;i:=1;j:=1;b:=1;
for k:= 1 to n do
repeat
if i=n+1 then i:=1;if i=0 then i:=n;
if j=n+1 then j:=1;
if a[i,j]=0 then begin a[i,j]:=b;i:=i+1;j:=j-1; end
else begin b:=b+1; i:=i+2;a[i,j]:=b; i:=i+1;j:=j-1;end;
until b=n+1;
i:=1;j:=2;b:=0;z:=-5;
for k:= 1 to n do
begin z:=z+5;
repeat
if i=n+1 then i:=1;if i=0 then i:=n;
if j=n+1 then j:=1;
if d[i,j]=0 then begin d[i,j]:=z;i:=i+1;j:=j-1;b:=b+1 end
else begin b:=b+1; i:=i+2;d[i,j]:=z; i:=i+1;j:=j-1;end;
until b=n*n;
for i:=1 to n do
for j:=1 to n do
c[i,j]:=a[i,j]+b[i,j];
for i:=1 to n do
begin
for j:=1 to n do
write(' ',c[i,j]);
writeln;
end;
end.
В программе использовалось уже три массива, и добавочные переменные. Это связано с облегчением задачи построения исходных матриц с последующим сложением оных. Также есть несколько иная программная реализация магических квадратов.
Uses Crt;
Const N = 127;
Var Mas : Array[1..N, 1..N] Of Word;
X, Y, X0, Y0 : Integer;
C : Longint;
Begin
ClrScr;
Assign(Output,'127x127.txt');
Rewrite(Output);
X:=(N - 1) Div 2 + 1;
Y:=X + 1;
X0:=X - 1;
Y0:=Y - 1;
While C < N*N Do
Begin
If (Mas[Y, X] <> 0) Then
Begin
X:=X0 - 1;
Y:=Y0 + 1;
If X < 1 Then X:=N;
If Y > N Then Y:=1;
End Else
Begin
Inc(C);
Mas[Y, X]:=C;
End;
X0:=X; Y0:=Y;
Inc(X); Inc(Y);
If Y > N Then Y:=1;
If X > N Then X:=1;
End;
For Y:=1 To N Do
Begin
For X:=1 To N Do
Write(Mas[Y,X]:6);
Writeln;
End;
Close(Output);
End.
Данный программный код будет работать быстрее, чем указанные выше, т.к. условие заполнения клетки оптимизировано.
3.3 Выводы
Алгоритмы генерации магических квадратов можно реализовать даже на самых простейших языках, например Pascal. Однако самый перспективный метод для распараллеливания это метод Ф. де ла Ира. Две матрицы можно заполнять по диагоналям сразу несколькими процессорами. Также можно выполнять поклеточное сложение. Метод Ф. де ла Ира работает как для квадратов четного, так и для квадратов нечетного порядка.
Заключение
Основные результаты выпускной квалификационной работы заключаются в следующем.
1. Рассмотрены все известные на данный момент виды магических квадратов. Также было выполнено ознакомление с историей магических квадратов.
2. Разобраны основные алгоритмы заполнения магических квадратов.
3. Проанализирована компьютерная реализация магических квадратов.
4. Сконструированы программы для основных методов заполнения магических квадратов. Выявлены наиболее подходящие алгоритмы для выполнения задач криптографии на многопроцессорных компьютерах.
Научная новизна результатов выпускной квалификационной работы заключается в следующем.
1. Рассмотрены все известные на данный момент алгоритмы заполнения магических квадратов.
2. Выявлен наиболее универсальный алгоритм заполнения магических квадратов- метод Ф. де ла Ира. Также этот метод может быть подвергнут преобразованиям для реализации его на многопроцессорных компьютерах.
3. Построены программные коды для основных алгоритмов генерации магических квадратов. Найден универсальный способ заполнения магических квадратов, подходящий для решения задач криптографии.
Приложение
С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. Наряду с традиционными применениями криптографии в политике, дипломатии и военном деле появляются и другие задачи - защита интеллектуальной собственности от преследований инквизиции или заимствований злоумышленников. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые в сущности задают правила перестановки букв в сообщении. В качестве ключа в шифрующих таблицах используются:
• размер таблицы;
• слово или фраза, задающие перестановку;
• особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение
ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ
записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рисунке ниже. После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам.
| Т | Н | П | В | Е | Г | Л |
| Е | А | Р | А | Д | О | Н |
| Р | Т | И | Е | Ь | В | О |
| М | О | Б | Т | М | П | Ч |
| И | Р | Ы | С | О | О | Ь |
Заполнение таблицы из 5 строк и 7 столбцов
Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение:
ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ
Естественно, отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. Следует заметить, что объединение букв шифртекста в 5-буквенные группы не входит в ключ шифра и осуществляется для удобства записи несмыслового текста. При расшифровании действия выполняют в обратном порядке. Несколько большей стойкостью к раскрытию обладает метод шифрования, называемый одиночной перестановкой по ключу. Этот метод отличается от предыдущего тем, что столбцы таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы.
Применим в качестве ключа, например, слово ПЕЛИКАН,
Таблицы, заполненные ключевым словом и текстом сообщения, а текст сообщения возьмем из предыдущего примера. На рисунке выше показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица - заполнению после перестановки. В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, они бы были пронумерованы слева направо. В правой таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа. При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение: