Úloha ze semináře programování

[juhelak]

Ahoj,

potreboval bych pomoct se seminarem z programovani MatFyzu - KSP. Zasekl jsem se hned u prvni ulohy: http://ksp.mff.cuni.cz/tasks/26/tasks5.html#task1 - nejsem si uplne jisty resenim. Udelal bych to prave tak, ze bych zkontroloval vsechny cisla doleva a nahoru, jenze v pribehu stoji, ze hledame postup, aby prave toto postava v pribehu delat nemusela.

Nejsem si jist, zda jsem to jen spatne nepochopil, a ze chce proste algoritmus, kterym to udela (a ktery proste zkontroluje vse doleva a nahoru), nebo jestli je tam nejake lepsi reseni.

Zkousel jsem v cislech hledat matematicke posloupnosti, hned v druhem radku (1,0,3,2,5,4...) nejaka je (kazde sude cislo je o 1 nizsi, jak cislo pred nim a kazde liche o 2 vyssi, jak predchozi liche), ale v ostatnich uz zadne nenachazim. Jsou tam take urcite periodicity v diagonalach, ale zda se, ze v kazde diagonale jine.

Nechci od vas reseni, to by bylo trochu nesmyslne seminar vubec resit, jen prosim o mensi nakopnuti smerem k reseni. Diky vsem.

[Reklama]

[JS]

Pomahat ti nebudu, za svych mladych let jsem delal sice jen KS z fyziky, ale myslim, ze cela pointa byla prave v tom, poslat to nejlepsi reseni co mas, a vysledek (spravne reseni, je-li znamo) se dozvis pozdeji. Takze pokud te nenapadne lepsi algoritmus, zkus poslat alespon ten hrubou silou - a uvidis.

Nicmene - troufam si tvrdit, ze ta tabulka je jen priklad toho, jak vypada vstup do programu (ktery splnuje urcite zadane podminky); takze bych v ni rozhodne nehledal nejake posloupnosti. Myslim, ze ten vysledny algoritmus by mel fungovat pro libovolny vstup splnujici ty zadane podminky.

[fdvgdsfsda]

potrebujes funkci, ktera rekne jake cislo rele je na jake pozici [A,B] pro jakkoliv velkou desku relatek.

vidim v tom nasledujici vzor, ktery asi pujde nasimulovat nejak pomoci opakujicich se vzoru v binarnich cislech.

nulty radek (2^0=1 jednice) je 0,1,2,3,4,5............
v prvnim radku (2^1=2 dvojice cisel) 0,1 --> 1,0/2,3 --> 3,2/4,5 --> 5,4
v druhem radku jsou prohozene ctverice, v tretim radku (2^3=8) osmice cisel.

budu si to rozmyslet jak do toho zamontovat mocniny cisla 2 a cislo radku a zkusim jeste napsat reseni.

[kolemčumící]

Hm, hm, matice je symetrická. Takže když po mně bude chtít číslo relé[m,n], tak mu pošlu relé[n,m]. To by fungovalo na tu matici v zadání, ale spíš to bude jen tak chyták a obecně to platit nebude. Ale kdo ví? :-)

[Lol Phirae]

Řešení je triviální. Stačí ze zařízení odstranit tzv. kurvítko a pojede to. Výměna údajně spálených relé je zcela zbytečná. 

[Reklama]

[kolemčumící]

Dále vidím, že relé[m,n] padne vždy do intervalu m-n. Což by třeba pro relé[1000000,1] mohlo ulehčit výpočet. Místo hledání nejmenšího z 1000000 prvků(vždy je projít všechny), by stačilo hledat pokud 999999 nebo 1000001 jsou vyplňěná. Ale kdo ví?
Jsou to jen nástřely. Nejsem programátor ani si na něj nehraju. Pokud má odevzdávací systém neomezený počet pokusů, můžeš zkusit. Třeba dostaneš místo 0,1 bodů za brute force, 0,15 :-)
 

[fdvgdsfsda]

Hm, hm, matice je symetrická. Takže když po mně bude chtít číslo relé[m,n], tak mu pošlu relé[n,m]. To by fungovalo na tu matici v zadání, ale spíš to bude jen tak chyták a obecně to platit nebude. Ale kdo ví? :-)

musi fungovat pro jakoukoliv velikost matice, tj. prodlouzit doprava a dolu.

[kolemčumící]

Dále vidím, že relé[m,n] padne vždy do intervalu m-n

Jasně že m+-n
Ale úkol dobrý, je to podobné sudoku, co třeba použít upravenou nějakou techniku odtud?

[student]

budu si to rozmyslet jak do toho zamontovat mocniny cisla 2 a cislo radku a zkusim jeste napsat reseni.

Nepis - vsak aj OP pise

Nechci od vas reseni, to by bylo trochu nesmyslne seminar vubec resit, jen prosim o mensi nakopnuti smerem k reseni. Diky vsem.

[2012]

ja bych na pozici AB umistil rele, ktere je na pozici BA..., ale pokud A=B tak bych na pozici AB umistil a-1,b-1 nebo a+1,b+1, ovsem pokud budou spalena obe symetricka rele, tak je Jakob v hajzlu

[hmmm]

Nakreslil bych si od toho vetsi oblast. Ona se v tom nejaka pravidelnost najde.

[2012]

ja bych na pozici AB umistil rele, ktere je na pozici BA..., ale pokud A=B tak bych na pozici AB umistil a-1,b-1 nebo a+1,b+1, ovsem pokud budou spalena obe symetricka rele, tak je Jakob v hajzlu

vlaste ne nebude, podivej je na ctverice vedle sebe, 0110, 2332, 4554; 2332, 0110, 4554 ...?

[ogar]

No nevim, mam sice uz v sobe pres 3/4 l cerveneho, ale kdyz sem si tu matici napsal binarne:

Kód: [Vybrat]

0000 0001 0010 0011 0100 0101
0001 0000 0011 0010 0101 0100
0010 0011 0000 0001 0110 0111
0011 0010 0001 0000 0111 0110
0100 0101 0110 0111 0000 0001
0101 0100 0111 0110 0001 0000

a pod to axiomy, ktere plati

Kód: [Vybrat]

A[m,n]=A[m,n]
A[n,n]=0
A[0,n]=n
A[n,0]=n

tak na mne hned vypadlo toto:

Kód: [Vybrat]

A[x,y]=A[x,0] ^ A[0,y] = x ^ y

Dava to smysl? Nejsem nahodou prolog? A nebo lepsi ?!?!?
 :-)

[lobo]

No nevim, mam sice uz v sobe pres 3/4 l cerveneho, ale kdyz sem si tu matici napsal binarne:

Kód: [Vybrat]

0000 0001 0010 0011 0100 0101
0001 0000 0011 0010 0101 0100
0010 0011 0000 0001 0110 0111
0011 0010 0001 0000 0111 0110
0100 0101 0110 0111 0000 0001
0101 0100 0111 0110 0001 0000

a pod to axiomy, ktere plati

Kód: [Vybrat]

A[m,n]=A[m,n]
A[n,n]=0
A[0,n]=n
A[n,0]=n

tak na mne hned vypadlo toto:

Kód: [Vybrat]

A[x,y]=A[x,0] ^ A[0,y] = x ^ y

Dava to smysl? Nejsem nahodou prolog? A nebo lepsi ?!?!?
 :-)

ak pod A[x,y]=x^y myslis A[x,y]= x XOR y  tak si lepsi, vynasiel si to skor ako ja

[Ivan]

reseni jsem nehledal, ale po prvnim precteni se mi vybavilo tohle:
http://www.keithschwarz.com/interesting/code/?dir=factoradic-permutation