|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Kostya Sudilovsky 2:452/64.4 13 Jun 2001 23:20:14
To : Wowa Savin
Subject : Магический квадpат
--------------------------------------------------------------------------------
Я заметил, что в Среда Июнь 13 2001, Wowa Savin писал:
WS>>> Дан квадpат NxN, где N - нечётно! Расположить в нём числа от
WS>>> 1 до N^2, что бы их сyмма по веpтикали, гоpизонтали и диагоналям
WS>>> были одинаковы!
KS>> Распалогаеш цифpы бyквой Г, считая что стенки пpозpачны:
WS> Hепpавильно:
Блин, вот лапухнулся ;(
вот на вскидку написал перебор для n=3 на c++:
#include <iostream.h>
#include <iomanip.h>
int a[3][3],was[10]={0};
void go(int i,int j){
if (i==3) {
if (a[0][0]+a[1][0]+a[2][0]==15 && // ветикали
a[0][1]+a[1][1]+a[2][1]==15 && // лень в цикл запинуть
a[0][2]+a[1][2]+a[2][2]==15 &&
a[0][0]+a[1][1]+a[2][2]==15 && // диагонали
a[0][2]+a[1][1]+a[2][0]==15){
for (int ii=0;ii<3;ii++){
for (int jj=0;jj<3;jj++)
cout<<setw(10)<<a[ii][jj];
cout<<'\n';
}
cout<<"------------------------------------------------------\n";
};
return;
}
for (a[i][j]=1;a[i][j]<=9;a[i][j]++) // если есть горизонать
if (!was[a[i][j]] && (j!=2 || a[i][0]+a[i][1]+a[i][2]==15)){
was[a[i][j]]=1;
if (j==2) go(i+1,0); else go(i,j+1);
was[a[i][j]]=0;
}
};
void main(){ go(0,0); };
И вот все маг. квадраты для n=3:
2 7 6
9 5 1
4 3 8
------------------------------------
2 9 4
7 5 3
6 1 8
------------------------------------
4 3 8
9 5 1
2 7 6
------------------------------------
4 9 2
3 5 7
8 1 6
------------------------------------
6 1 8
7 5 3
2 9 4
------------------------------------
6 7 2
1 5 9
8 3 4
------------------------------------
8 1 6
3 5 7
4 9 2
------------------------------------
8 3 4
1 5 9
6 7 2
как видно в углу 1 брать нельзя :( в общем можно устроить перебор для поиска
места для 1, а потом - как я расказывал, только попадаются случаи, когда цифры
налаживаются, тогда надо применить симметричную Г:
010 010 0*0 сим. 010 010 016 016 сим. 016 816
000 -> 300 -> 300 -> 300 -> 350 -> 350 -> 350 -> 357 -> 357
002 002 002 402 402 402 *02 402 492
и того, сложность алгоритма - O(n^4) - вполне можно посчитать для n<100.
для n>3 я не проверял - лень :) хотя проверить стоит.
Digitally yours, Sudilovsky Kostya.
--- GoldED+/W32 1.1.4.5
* Origin: Gomel State Univesity (2:452/64.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
