|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ihor Bobak 2:5020/400 13 Jun 2001 21:30:46
To : All
Subject : Re: Магический квадpат
--------------------------------------------------------------------------------
> Задача:
> Дан квадpат NxN, где N - нечётно!
> Расположить в нём числа от 1 до N^2,
> что бы их сyмма по веpтикали, гоpизонтали
> и диагоналям были одинаковы!
Я нашел в своем архиве описание и реализацию этого алгоритма.
Автор - не я, так что ответственности за правильность не несу.
MAGIC SQUARES
-------------
A magic square of order N is a square matrix N x N containing the
integers from 1 to N? in such a way, that the sum of the elements on
each row, column, and diagonal equals N*(N?+1)/2.
To solve the problem of generating a magic square of a given order
N, we will use an algorithm that examines three cases for N.
a) N is odd (1,3,5,...) Having an odd N, we put the numbers from
1 to N? in order, starting from the middle column of the first row
and moving one step up and left on each move. When we get ot of
position 0 we go to position N and when we get out of position N+1 we
go to position 1. When we reach an already visited item, we move
one step down. Here is an illustration of how this algorithm works
for N=3:
- 1 - - 1 - - 1 - - 1 - - 1 - - 1 6 - 1 6 8 1 6 8 1 6
- - - - - - 3 - - 3 - - 3 5 - 3 5 - 3 5 7 3 5 7 3 5 7
- - - - - 2 - - 2 4 - 2 4 - 2 4 - 2 4 - 2 4 - 2 4 9 2
If we precalculate some expressions, the algorithm can be realized
with only two loops, as is done with the example source.
b) N is even, of the form 4*K (4,8,12,...) This case involves a
completely different algorithm.
(1) The cells denoted with '*' in the figure on the left below are
filled with their linear numbers as shown (for N=8).
* * - - - - * * 1 2 - - - - 7 8
* * - - - - * * 9 10 - - - - 15 16
- - * * * * - - - - 19 20 21 22 - -
- - * * * * - - - - 27 28 29 30 - -
- - * * * * - - - - 35 36 37 38 - -
- - * * * * - - - - 43 44 45 46 - -
* * - - - - * * 49 50 - - - - 55 56
* * - - - - * * 57 58 - - - - 63 64
k : 2k : k
Note that the sizes of the regions with and without asterisks ('*')
are in a ratio 1:2:1 (in this case 2:4:2). Generally, all cells
for which ((x<=k) or (x>N-k)) AND ((y<=k) or (y>N-k)) /those are
the cells in the four courners/ as well as the cells for which
((x>k) and (x<=N-k)) AND ((y>k) and (y<=N-k)) /the cells in the
center/, where k=N/4, are marked with asterisks.
(2) Traverse the empty cells in the table right to left, starting
from the bottom line, filling the cells with those numbers from
1 to N? that have not been filled-in already.
1 2 62 61 60 59 7 8
9 10 54 53 52 51 15 16
48 47 19 20 21 22 42 41
40 39 27 28 29 30 34 33
32 31 35 36 37 38 26 25
24 23 43 44 45 46 18 17
49 50 14 13 12 11 55 56
57 58 6 5 4 3 63 64
This way the smallest unused numbers show up in the bottom lines,
and the largest - in the top lines. This makes the sums on the
horizontals, verticals, and diagonals equal, and therefore yields
the solution of the problem.
c) N is even, of the form 4*k+2 (6,10,14,...) This case involves a
much more complicated algorithm. We start similarly to the previous
algorithm.
(1) We fill the cells denoted with '*' in the table with their
corresponding linear addresses. The empty cells are now those for
which
((x<k)) and (x<=N-k)) AND ((y>k) and (y<=N-k))
as well those for which
((x<=k+1) or (x>N-k-1)) AND ((y<=k+1) or (y>N-k-1))
1 2 - - 5 6 ї
7 8 9 10 11 12 Щ k+1
- 14 15 16 17 - ї
- 20 21 22 23 - Щ 2k
25 26 27 28 29 30 ї
31 32 - - 35 36 Щ k+1
k+1 2k k+1
Note that the sizes of the regions are k+1,2k,k+1, where k = (N-2)/4.
(2) We fill the rest of the cells (the empty ones) with the unused
numbers, just like we did in the previous algorithm - left to right,
starting from the bottom line. We get the following square, which
unfortunatelly is not yet magic.
1 2 34 33 5 6
7 8 9 10 11 12 U
24 14 15 16 17 19
18 20 21 22 23 13
25 26 27 28 29 30 D
31 32 4 3 35 36
L R
In order to fit the table for our purposes, we need to alter it
a little. Let U denote the row number k+1, D - the row number N-k,
L - the column number k+1, and R - the column numbered N-k.
(3) We convert the columns L and R. We reverse the order of the
elements in column R, keeping row U and D intact (3a). We then swap
the middle rows of the L and R colums (the rows between U and D) (3b).
After this, we swap those elements of the colums L and R, whcih
lie right below the center of the matrix.
(4) We convert row 1. We reverse the order of the numbers from the
middle colums of row 1 (the columns between L and R) (4a). We swap
the first k with the last k elements of row N/2+k-1 (4b).
(5) We convert rows U and D. We reverse the order of the elements in
rows U and D, keeping the columns L and R intact (5a). We swap the
elements from the middle columns of rows U and D (5b). We then swap
the first elements of rows U and D (5c).
(6) Our magic square now becomes magic indeed.
The sample program is tested and works properly for N=1..1000.
The complexity of the algorithm (in the worst case) is N*N.
This algorithm is realized following step by step
instructions downloaded from the Internet.
}
CONST MaxN = 100;
VAR T: array[1..MaxN,1..MaxN] of integer;
N: integer;
Procedure OddMagicSquare; {Algorithm a for odd values of N}
Var i,j,x,y,Num: integer;
Begin
Num:= 0;
for i:= 0 to N-1 do
for j:= 0 to N-1 do
begin
x:= 1 + (j-i+N*3 div 2) mod N;
y:= 1 + (i*2-j+N) mod N;
Inc(Num); T[x,y]:=Num;
end;
End;
Procedure Even_4_8_12_MagicSquare; {Algorithm b for even values of N}
Var Used: array[1..MaxN*MaxN] of boolean;
x,y,k,index: integer;
Begin
FillChar(Used,SizeOf(Used),false);
FillChar(T,SizeOf(T),0);
{1}
k:= N div 4;
for x:= 1 to N do
for y:= 1 to N do
if ( ((x>k)and(x<=n-k)) AND ((y>k)and(y<=n-k)) ) or
( ((x<=k)or(x>n-k)) AND ((y<=k)or(y>n-k)) ) then
begin
T[x,y]:= (y-1)*N + x;
Used[(y-1)*N + x]:= true;
end;
{2}
index:=0;
for y:= N downto 1 do
for x:= N downto 1 do
if T[x,y] = 0 then
begin
repeat inc(index); until not Used[index];
T[x,y]:=index;
end;
End;
Procedure Even_6_10_14_MagicSquare; {Algorithm c for even N}
Procedure Swap(x1,y1,x2,y2:integer);
Var Tmp: integer;
Begin
Tmp:=T[x1,y1]; T[x1,y1]:=T[x2,y2]; T[x2,y2]:=Tmp;
End;
Var Used: array[1..MaxN*MaxN] of boolean;
x,y,k,index: integer;
Begin
FillChar(Used,SizeOf(Used),false);
FillChar(T,SizeOf(T),0);
{1}
k:= N div 4;
for x:= 1 to N do
for y:= 1 to N do
if ( ((x>k)and(x<=n-k)) AND ((y>k)and(y<=n-k)) ) or
( ((x<=k+1)or(x>n-k-1)) AND ((y<=k+1)or(y>n-k-1)) ) then
begin
T[x,y]:= (y-1)*N + x;
Used[(y-1)*N + x]:= true;
end;
{2}
index:=0;
for y:= N downto 1 do
for x:= N downto 1 do
begin
inc(index);
if T[x,y] = 0 then
T[x,y]:=index;
end;
{3-a}
for y:= 1 to N div 2 do
if y <> k+1 then
Swap(N-k,y, N-k,N-y+1);
{3-b}
for y:= k+2 to N-k-1 do
Swap(k+1,y, N-k,y);
{3-c}
Swap(k+1,N div 2+1, N-k,N div 2+1);
{4-a}
for x:= k+2 to N div 2 do
Swap(x,1, N-x+1,1);
{4-b}
for x:= 1 to k do
Swap(x,N div 2+k-1, N-x+1,N div 2+k-1);
{5-a}
for x:= 1 to N div 2 do
if x <> k+1 then
Swap(x,k+1, N-x+1,k+1);
for x:= 1 to N div 2 do
if x <> k+1 then
Swap(x,N-k, N-x+1,N-k);
{5-b}
for x:= k+2 to N-k-1 do
Swap(x,k+1, x,N-k);
{5-c}
Swap(1,k+1, 1,N-k);
End;
Procedure PrintSquare;
Var X,Y: integer;
Begin
for Y:= 1 to N do
begin
for X:= 1 to N do
Write(T[X,Y]:3,' ');
WriteLn;
end;
End;
BEGIN
Write('N = '); ReadLn(N);
WriteLn;
if Odd(N) then
OddMagicSquare
else if (N mod 4) = 0 then
Even_4_8_12_MagicSquare
else Even_6_10_14_MagicSquare;
PrintSquare;
END.
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
