Fórum Root.cz
Práce => Studium a uplatnění => Téma založeno: juhelak 19. 05. 2014, 18:00:09
-
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.
-
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.
-
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.
-
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í? :-)
-
Ř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á. 8) :D
-
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 :-)
-
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.
-
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?
-
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.
-
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 :D
-
Nakreslil bych si od toho vetsi oblast. Ona se v tom nejaka pravidelnost najde.
-
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 :D
vlaste ne nebude, podivej je na ctverice vedle sebe, 0110, 2332, 4554; 2332, 0110, 4554 ...? :)
-
No nevim, mam sice uz v sobe pres 3/4 l cerveneho, ale kdyz sem si tu matici napsal binarne:
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
A[m,n]=A[m,n]
A[n,n]=0
A[0,n]=n
A[n,0]=n
tak na mne hned vypadlo toto:
A[x,y]=A[x,0] ^ A[0,y] = x ^ y
Dava to smysl? Nejsem nahodou prolog? A nebo lepsi ?!?!?
:-)
-
No nevim, mam sice uz v sobe pres 3/4 l cerveneho, ale kdyz sem si tu matici napsal binarne:
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
A[m,n]=A[m,n]
A[n,n]=0
A[0,n]=n
A[n,0]=n
tak na mne hned vypadlo toto:
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
-
reseni jsem nehledal, ale po prvnim precteni se mi vybavilo tohle:
http://www.keithschwarz.com/interesting/code/?dir=factoradic-permutation
-
ak pod A[x,y]=x^y myslis A[x,y]= x XOR y tak si lepsi, vynasiel si to skor ako ja
Samozrejmne, klasicke hardcore C/C++ XOR!!!
Ja si neuvedomil, ze dneska uz vetsina lidi patla sve vytvory ve 'vyssich' programovacich jazycich :-)
-
ak pod A[x,y]=x^y myslis A[x,y]= x XOR y tak si lepsi, vynasiel si to skor ako ja
Samozrejmne, klasicke hardcore C/C++ XOR!!!
Ja si neuvedomil, ze dneska uz vetsina lidi patla sve vytvory ve 'vyssich' programovacich jazycich :-)
napriklad Assembler? XOR ax,bx ;-)
-
Jestli začínáš nebude jednodušší zkusit KSP-Z které je přímo určené pro začátečníky? Případně pošli své řešení (jakkoliv špatné, žádný učený z nebe nespadl) a uvidíš.
-
napriklad Assembler? XOR ax,bx ;-)
Masochisti a milovnici x86 pisu rovno 0x31 0xc3 ;). Vyslanim motyla (http://xkcd.com/378/)