Mitenkä tallainen tehtävä ratkaistaan? 5x4-matriisin alkiot ovat kokonaislukuja väliltä 0,...,9. Siitä muodostetaan lukuja valitsemalla jokin numero ensimmäiseksi, valitsemalla jokin kahdeksasta suunnasta ja kuljetaan sitä pitkin niin paljon kuin halutaan. Esimerkiksi matriisista
1244
2343
1233
3464
6576
voi lukea vaikkapa luvut 1334, 2343, 266, mutta 264:ää ei, sillä lukiessa jouduttaisiin kääntymään. Miten osoitetaan, että matriisin 20-numeroa voidaan valita siten, että siitä voi lukea lukujen 0,...,20 neliöt?
Erityisen matriisin olemassaolo
matriisilaskija
4
79
Vastaukset
- Brute Force
Tällainen tehtävä osoitetaan konstruktivistisesti. Eli teet sellaisen 5x4 matriisin joka koostuu luvuista 0,...,9 ja ympyröit vaikkapa lukujen 0,...20 neliöt.
Kannattanee ympyröinti suorittaa selvyyden vuoksi useampaan eri matriisiin (sama matriisi mutta uusiksi kirjoitettuna)
Jos taas pitäisi osoittaa että ei ole mahdollista niin homma on vaikeampi.
Se voitaisiin ohjelmoida tietokoneelle periaatteessa joka tutkisi kaikki 10^20 matriisia (tai itse asiassa alle) ja todeta ettei löytynyt ehdot täyttäviä matriiseja. Aikaa kuluisi tuhottomasti, mutta perustelu olisi riittvä. - matriisilaskija
Ookei. Mulla taitaa olla hidas algoritmi kun en löydä kyseistä matriisia.
Tässäpä esimerkkiratkaisu:
1,5,3,1
4,2,6,0
4,9,1,0
1,4,8,4
6,5,2,2- matriisilaskija
OK. Taitaa toimia. Olisi kiinnostavaa tietää, millaisella algoritmilla löysit ratkaisun? Löysin probleeman osoitteesta http://stackoverflow.com/questions/3382859/solving-a-recreational-square-packing-problem ja päätin tutkia joitain pienempiä tapauksia ensin. Myös alkuperäinen ongelma on ratkeamatta.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Riikka Purra lupasi Suomen kansalle 1 euron bensaa, hinta nyt 2 euroa
Vasemmistolaisen Marinin hallituksen aikana bensa ei maksanut kuin 1,3 euroa litralta. Ministerin pitäisi perustuslain m2375143Suvi Lindenillä 5 366 päivän putki
Täytyy kyllä myöntää vaikka olen itsekin innokas, niin en ole tuollaiseen yli kymmenen vuoden putkeen kyennyt. Välillä o1194181- 583843
Mistä se kertoo
Näin miehen pitkästä aikaa. Samantien iski sellainen paineen tunne rintaan, sitä ei ole ollut vuosiin. Ja nyt olen siitä363609- 513550
Rakkaalle miehelle
Terveiset rakas. Ikävä on edelleen. Suru valtaa sydämen, kun en saa lähestyä sinua. En saa vastauksia, en soittoa, viest413295Muistatteko kuinka Marinin hallituksen aikaan kansalaisilla oli varaa kuluttaa?
Tavallisella perheelläkin oli rahaa käydä sääännöllisesti ravintoloissa syömässä, koska vahvat ammattiliitot olivat neuv72704Nyt on sanottava että sattuu kipeästi
Jos, sinä aikana kun olen kaivannut ja odottanut sinua ja olet tiennyt sen, niin jos valitsit toisen miehen. Katsot minu202596- 232436
SDP:n kansanedustaja Nazima Radmyar uhriutuu somessa saamistaan viesteistä.
https://www.is.fi/politiikka/art-2000011854410.html Miksi Razmyar ei kestä kansan palautetta oikean kansanedustajan tavo602388