Matematické Fórum

vitrica · 31. 12. 2014 12:08

Magický čtverec o velikosti N je čtvercová matice celých čísel o rozměrech NxN obsahující všechna čísla 1..N2 (tedy každé z těchto čísel právě jednou), a vyznačuje se tím, že všechny řádky, všechny sloupce, i obě hlavní diagonály mají stejný součet. Úkolem je sestavit magický čverec dané velikosti, pokud některá čísla v něm jsou již pevně zadána.

Vstupní data načtěte ze vstupního textového souboru 'square.in' (tak přesně se musí jmenovat). Na prvním řádku vstupního souboru bude celé kladné číslo N, které udává rozměr magického čtverce (N <= 10). Pak následuje N řádků a na každém N celých nezáporných čísel oddělených mezerami - tím je určena matice o rozměrech NxN. Kladná čísla jsou vždy z rozsahu 1..N2 a každé se v matici vyskytuje nejvýše jednou. Umístění těchto kladných čísel ve čtverci se již nesmí měnit, zatímco nuly ve vstupním souboru znamenají, že příslušné políčko čtverce je dosud prázdné.

Program má zjistit, zda existuje takové doplnění čísel do prázdných políček zadané matice, že vznikne magický čtverec. Na standardním výstupu se má objevit buď řetězec ANO, nebo NE.

Příklad vstupu:
3
0 0 0
2 4 0
0 3 0
Správný výstup: NE

Příklad vstupu:
5
0 0 0 7 4
0 1 0 0 8
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
Správný výstup: ANO

(Řešením je např. tento magický čtverec: )
14 15 25 7 4
16 1 19 21 8
13 22 3 9 18
2 17 12 23 11
20 10 6 5 24

prosím moc o pomoc, jsem bezradný a ani nwm,jak začít :(:(

Eratosthenes · 03. 01. 2015 12:22

↑ vitrica:

Nenapadá mě nic lepšího, než zneužít hrubou sílu počítače a vyzkoušet všechny možnosti.

ewer12 · 03. 01. 2015 16:50 — Editoval ewer12 (03. 01. 2015 17:15)

Možná by se to dalo řešit jako soustava rovnic, docela pomůže když víš, že součet každého řádku, sloupce a hlavní diagonály je roven $n^2(n^2+1)/2n = (n^3+n)/2$

Příklad:
0 1 a b
2 0 c d
n = 5

součet prvního řádku:
a + 1 = 5
součet prvního sloupce:
a + 2 = 5

V tuto chvíli by už program věděl, že soustava nemá řešení, protože si 2 rovnice odporují.

Nebo:
0 1
0 0
a + 1 = 5
a + c = 5 => a+1=a+c => c = 1 => nemá řešení, hodnotu 1 už má b

Nejsem si ale úplně jistý tím, jak by program postupoval u složitějších případů(nedourčená soustava rovnic) a asi by nebylo moc jednoduché tento proces zautomatizovat.

Pokud nějakým způsobem zjistíš správný postup, mohl bys ho sem stručně napsat? Docela by mě to zajímalo :)

Eratosthenes

↑ ewer12:

Vzoreček je samozřejmě hezký, ale obávám se, že by jen rychleji vylučoval špatné možnosti a na principu ↑ Eratosthenes: by toho mnoho nezměnil.

PS: Přece jen mě něco napadlo: máš čtverec n x n s r zadanými čísly, tedy n x n - r neznámých a má ti sedět 2n+2 součtů. Máš tedy 2n+2 rovnic pro n x n - r neznámých. Můžeš sestavit její matici a převést na trojúhelníkový tvar. Bude-li se hodnost matice rovnat hodnosti matice rozšířené, pak má soustava řešení. Mohou-li být složky řešení navzájem různé, pak čtverec existuje.

Je ovšem otázka, zda je napropgramování něčeho takového jednodušší, než projítí všech možností :-)

maoap · 01. 03. 2017 18:25

Ahoj, letos (tento týden) se tato úloha znovu objevila mezi domácími úlohami v Codexu, takže je toto téma zase aktuální. Takže sem píšu nové informace o této úloze, kdyby se někomu ještě hodily:
Všechny vstupy jsou velikosti 3 nebo 4. To je zásadní věc, kterou v zadání nezmínili... Tím jsem si jist (dejte v programu halt(N), kde N je vstup a zjistíte to taky), takže co se týče náročné časové složitosti, tak to tak špatné není. Moje řešení pomohlo: Procházet po řádcích, postupně ořezávat, pokud prozatímní součet + ty nejmenší volný byl větší než magická konstanta, případně prozatímní součet + ty největší volný je menší než magická konstanta (tzn. ukončit tuhle větev a dosadit tam jiné číslo). Samozřejmě každý řádek průběžně testovat, jestli je součet roven magické konstantě.

Mimochodem pro tu matici 5x5 program v rozumném čase výsledek nedá.

Matematické Fórum

#1 31. 12. 2014 12:08

Pascal-magické čtverce

#2 03. 01. 2015 12:22

Re: Pascal-magické čtverce

#3 03. 01. 2015 16:50 — Editoval ewer12 (03. 01. 2015 17:15)

Re: Pascal-magické čtverce

#4 03. 01. 2015 18:43 — Editoval Eratosthenes (03. 01. 2015 20:59)

Re: Pascal-magické čtverce

#5 01. 03. 2017 18:25

Re: Pascal-magické čtverce

Zápatí