Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 31. 12. 2014 12:08

vitrica
Zelenáč
Příspěvky: 16
Škola: mff uk
Reputace:   
 

Pascal-magické čtverce

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 :(:(

Offline

 

#2 03. 01. 2015 12:22

Eratosthenes
Příspěvky: 1912
Reputace:   120 
 

Re: Pascal-magické čtverce

↑ vitrica:

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


Nejraději chodím bos, když mé boty uvíznou v řiti nějakého hňupa.

Offline

 

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

ewer12
Příspěvky: 68
Reputace:   
 

Re: Pascal-magické čtverce

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 :)

Offline

 

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

Eratosthenes
Příspěvky: 1912
Reputace:   120 
 

Re: Pascal-magické čtverce

↑ 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í :-)


Nejraději chodím bos, když mé boty uvíznou v řiti nějakého hňupa.

Offline

 

#5 01. 03. 2017 18:25

maoap
Zelenáč
Příspěvky: 9
Škola: MFF UK
Pozice: student
Reputace:   
 

Re: Pascal-magické čtverce

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á.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson