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
4
60
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.
- MattiKSinisalo
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
Mihin Ilkka Kanerva kuoli?
Kun näin jokin aika sitten kuvan riutuneen näköisestä Kanervasta, sanoin vaimolle että haimasyövältä vaikuttaa. Vaimon isä oli kuollut kyseiseen tauti27717688Oho! Susanna Laine uudessa hiustyylissä - Julkkismeikkaajalta tiukka palaute: "Ihan sama..."
Ex-Salkkarit tähti ja juontaja Susanna Laine on monessa mukana. Ex-missi tunnetaan pitkistä, vaaleista hiuksistaan . Mitäs tykkäät uudesta hiustyylist245676- 1232642
Yllätyspaljastus: Poppari Robin Packalen kiittää urastaan iskelmätähti Juha Tapiota: "Jos mä en..."
Oi, mikä tarina. Juha Tapio ja Robin ovat kyllä symppiksiä molemmat. Kumpi heistä on suosikkisi? https://www.suomi24.fi/viihde/yllatyspaljastus-poppar172162Venäjän lippulaiva Moskva upotettu Mustallamerellä
Venäjän laivaston lippulaiva Mustalalmerellä on 180 m pituinen, Neuvostoliiton aikana rakennettu Moskva-niminen risteilijä. Ukraina ilmoitti eilen saa3361795Pikkaraiskan puhelut
Mitä tuo jätkä hakee sillä että julkaisee kuinka kauan on puhunut puhelimessa? Tekee itsestään vieläkin idiootimman tuolla vai mikä tää juttu?1111047- 59973
Hossein Najaf juotti lapset humalaan ja käytti häikäilemättä hyväkseen
Keski-Suomen käräjäoikeus on tuominnut 60-vuotiaan Hossein Najafin neljän vuoden vankeusrangaistukseen. Ensimmäisen tytön kanssa hän oli useita kerto32941Sofia Belorf ja Sonja Aiello
Viihtyvät yhdessä dinnerillä. Pienet piirit. Mitä ajatuksia herättää ?45941