Магический квадрат

 

Кодирование

Program magicheskij_kvadrat;

Uses Crt;

Var A : Array [1..20, 1..20] of Integer;

     i, j, n : Integer;

     Standard, S : Integer;

     Otvet : Boolean; 

{------------------------------------------------------------------}

Procedure Vvod_vyvod; {Процедура ввода-вывода матрицы}

Begin 

  ClrScr;

  Write('Введите порядок квадрата ');

  ReadLn(n);

  For i := 1 to n do

    For j := 1 to n do

     begin

      Write('Введите A[',i,', ',j,'] = ');

      ReadLn(A[i,j])

     end; 

  ClrScr;

  WriteLn('Исходная матрица :');

  WriteLn;

    For i := 1 to n do

      begin

       For j := 1 to n do Write(A[i,j] : 5);

       WriteLn

      end;

  WriteLn

End; 
 
 

{------------------------------------------------------------------}

Procedure Proverka (Var Otvet:Boolean);

{Проверка, является ли квадрат  магическим}

Begin

 

{выбор  эталона суммы}

  Standard:=0;

  For i := 1 to n do Standard := Standard + A[i,i];

 

  Otvet:=TRUE;

  i:=1;

 

  {проверка строк}

  While (i<=n) and Otvet do

     begin

       S:=0;

       For j := 1 to n do S := S+A[i, j];

       If S<>Standard

          then Otvet := FALSE

          else i:=i+1

     end;

    

  {проверка столбцов}

  j:=1;

  While (j<=n) and Otvet do

    begin

      S:=0;

      For i := 1 to n do S:=S+A[i, j];

      If S<>Standard

          then Otvet := FALSE

          else j := j+1

    end; 

  {проверка побочной диагонали}

  If Otvet then

    begin

      S:=0;

      For i := 1 to n do S := S+A[i,n-i+1];

      If S<>Standard then Otvet := FALSE;

    end;

End; 

{------------------------------------------------------------------}

{основная программа}

BEGIN

  Vvod_vyvod; {Процедура ввода-вывода }

  Proverka (Otvet); {Вызов процедуры решения задачи }

  If Otvet then WriteLn('Это магический квадрат.')

               else WriteLn('Это не магический квадрат.');

  ReadLn

END. 

    Отладка

    Для удобства работы с данной программой мною была использована команда Uses Crt – вызов всплывающего окна ввода и вывода данных. Для того, чтобы ранее водимые данные не смешивались с текущей информацией, перед вводом и выводом матрицы было использована команда ClrScr – очистка диалогового окна. 
 

    Тестирование

     Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат  размером 3х3 (если не учитывать его  повороты). Количество магических квадратов 4х4 составляет уже 880, а количество магических квадратов 5х5 - около 250000. Поскольку общего алгоритма построения, подходящего под все виды магических квадратов не существует, то для тестирования программы мною были использованы квадратные матрицы, построенные по методу французского геометра 17 в. де ла Лубера, а также квадратная матрица размером 3х3, указанная выше. 
 
 
 
 
 
 

 

Глава 3. Использование  магических квадратов в современном  мире

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

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

     Магические  квадраты получили распространение  даже в сфере развлечений. На их основе созданы многие современные логические игры. Например, игра «Судоку». Игра представляет собой квадрат размером 3х3 клетки. В каждую клетку помещается одно число от 1 до 9 причем так, чтобы сумма чисел в любом столбце, строке и по диагонали равнялась 15.

     История судоку как игры восходит к имени  знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707 – 1783). В бумагах его архива, датированных 17 октября 1776 года, содержатся записи о том, как образовать магический квадрат с определенным числом ячеек, особенно 9, 16, 25 и 36. В другом документе, озаглавленном «Научное исследование новых разновидностей магического  квадрата» Эйлер помещал в  клетки латинские буквы (Латинский  квадрат), позже он заполнил клетки греческими буквами и называл  квадрат греко-латинским. Исследуя различные варианты магического  квадрата, Эйлер обратил внимание на проблему комбинации символов таким  образом, чтобы не один из них не повторялся ни в одной строке и  ни в одном столбце.

     В современном виде головоломки судоку впервые были опубликованы в 1979 году в журнале Word Games magazine. Автором головоломки  был Гарвард Гарис. Он использовал принцип латинского квадрата Эйлера, применил его в матрице размерностью 9х9 и добавил дополнительные ограничения, цифры не должны повторяться и во внутренних квадратах 3х3.

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

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

     Кроме того, магические квадраты используются при решении задач криптографии. С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. Наряду с традиционными применениями криптографии в политике, дипломатии и военном деле появляются и другие задачи - защита интеллектуальной собственности от преследований инквизиции или заимствований злоумышленников. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые в сущности задают правила перестановки букв в сообщении. В качестве ключа в шифрующих таблицах используются:

     • размер таблицы;

     • слово или фраза, задающие перестановку;

     • особенности структуры таблицы.

     Одним из самых примитивных табличных  шифров перестановки является простая  перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение

     ТЕРМИНАТОР  ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

     записывается  в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рисунке  ниже. После заполнения таблицы текстом  сообщения по столбцам для формирования шифртекста считывают содержимое таблицы  по строкам. 

 

     Заполнение  таблицы из 5 строк и 7 столбцов

     Если  шифртекст записывать группами по пять букв, получается такое шифрованное  сообщение:

     ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР  ЫСООЬ

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

     Применим  в качестве ключа, например, слово  ПЕЛИКАН,

     

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

     ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР  СОЫЬИ

     Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой  метод шифрования называется двойной  перестановкой. Пример выполнения шифрования методом двойной перестановки показан  на рисунке ниже. Если считывать  шифртекст из правой таблицы построчно  блоками по четыре буквы, то получится  следующее:

     ТЮАЕ  ООГМ РЛИП ОЬСВ

     Ключом  к шифру двойной перестановки служит последовательность номеров  столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно). 

     

     Однако  двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом  размере таблицы шифрования.

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