Seuraa 
Viestejä565
Liittynyt10.10.2013

En tiedä kiinnostaako se keitään muita, mutta tutkin lapsellisesti sattumanvaraisesti kuvaan aseteltuja ympyröitä. Kivaa oli ohjelmoida.

 

Olkoon kuvan leveys 1280 pixeliä ja korkeus 720. Arvotaan sattumanvaraisesti kuvaruudulle paikkoja ympyröille, joiden säde on 20. Lasketaan ensin hyvin hypoteettiset ala- ja ylärajat. Kuinka monta ympyrää enintään kuvaruudulle mahtuu? Kuinka monta vähintään eli mikä on vähimmäismäärä, minkä jälkeen yhtään ympyrää ei enää mahdu? Ympyrät eivät siis saa osua toistensa päälle. Kaksi samankokoista ympyrää osuvat päällekkäin jos niiden keskipisteiden etäisyys on vähemmän kuin 2*säde. 

 

Ensimmäinen tehtävä on helppo. Ympyröitä mahtuu maksimimäärä tietysti sellaisella asettelulla, että ympyrät ovat vieri vieressä 40*40 suuruisen neliön sisällä. 1280 levyiseen kuvaan mahtuu leveyssuunnassa 1280/40 = 34 neliötä ja pystysuunnassa 720 korkeuksiseen kuvaan 720/40 = 18 eli yhteensä neliöitä ja siten myös ympyröitä mahtuu maksimissaan 34*18 = 612 kpl. 

 

Entä vähiten? Voisi kuvitella, että vähiten mahtuu sellaisella asettelulla, että neljä vierekkäistä ympyrää vie juuri ja juuri niin paljon tilaa, että niiden "sisälle" ei mahdu viidettä ympyrää. Ympyrät ovat siis mahdollisimman harvassa, mutta eivät niin harvassa, että niiden väliin jäisi tilaa ympyrälle. Pythagoraan lausetta soveltaen:

voidaan yhtälöstä x^2 + x^2 = (4*säde)^2 laskea, että ympyröiden etäisyys täytyy olla enintään säde*4/Sqrt(2) = säde*2.828427125. Näin järjestettyjä ympyröitä mahtuu leveyssuunnassa noin 1280/(20*4/Sqrt(2)) = 22 ja pystysuunnassa noin 720/(20*4/Sqrt(2)) = 12 eli yhteensä noin 264 kpl.

 

Yritin tutkia ohjelmallisesti http://petke.info/ympyrat.r yhdellä koeajolla kuinka kauan kestää, että sattumanvaraisesti ympyröiden paikkoja arpova ohjelma saa kuvaan mahtumaan 380 kpl ympyröitä. Kärsivällisyyteni loppui kuitenkin 372 ympyrän kohdalla. Kun ympyröiden lukumäärä kuvassa oli ylittänyt noin 350 alkoi kestämään kauan ennekuin uudelle ympyrälle löydettiin arpomalla paikka. 350:nnen ympyrän kohdalla oli täytynyt arpoa jo 60577 paikkaa ja ennekuin 351.s ympyrä löysi paikkansa täytyi arpoa vielä 10253 paikkaa. Siitä eteenpäin vauhti tietysti vain hidastui. Miljoonas paikka oltiin arvottu 371 ja 372:nnen ympyrän välillä. Kun keskeytin ohjelman ajon, oltiin paikkoja arvottu jo yli 4 miljoonaa, eikä 373:lle ympyrälle ollut vielä paikkaa löytynyt vaikka ohjelmaa oli ajettu puolisen tuntia.

 

(a=arvottuja paikkoja, b=mahtuneita ympyröitä, c=aika)

a____ b__ c__________

60577 350 00:32.49

70830 351 00:37.753

70982 352 00:37.837

73908 353 00:39.357

76484 354 00:40.738

78856 355 00:41.921

80969 356 00:43.013

84181 357 00:44.664

99609 358 00:52.57

108397 359 00:56.96

133038 360 01:10.889

141408 361 01:15.2

160023 362 01:24.777

161679 363 01:25.62

329917 364 02:52.132

381150 365 03:19.783

635119 366 05:54.418

670380 367 06:13.735

705605 368 06:31.742

740559 369 06:49.387

777142 370 07:08.021

827937 371 07:33.98

1132078 372 10:09.476

4270017 xxx 29:56.692

 

372:sta ympyrästä tuli tällainen kuva:

http://petke.info/ymp02.png

Silmämääräisesti tarkasteltuna sieltä juuri ja juuri saattaisi vielä löytää parille ympyrälle paikka. No, siihen ei voi luottaa, joten pistin ohjelman http://petke.info/ympyra372lisaa.r tutkimaan pixeli pixeliltä ja sieltä ei löytynyt enää yhtään paikkaa, joten ei ihme, että ohjelma ei arpomalla löytänyt. Minun ennätykseni on tällä hetkellä siis 372. Jonain yönä aion pistää ohjelman rikkomaan sen.

Sitten alkoi kiinnostamaan, kuinka monta ympyrää keskimäärin voidaan kuvaan asettaa, ennenkuin ympyrä osuu johonkin aikaisempaan. Tein miljoona koeajoa. Sain aikaiseksi melko selkeän kuvaajakäyrän:

http://petke.info/graafi.png

 

Heti toinen ympyrä osui ensimmäiseen 11966 tapauksessa miljoonasta. Todennäköisyys sille, että näin käy on (pi*(2*20)^2) / ((1280-40) * (720-40)) = 0.00596127638252333 ja 11966/1000000 = 0.011966 mikä on melko tasan kaksi kertaa liian suuri arvo. Koodissani http://petke.info/ympyratekat.r täytyy olla virhe (tai laskussa), mutta en löytänyt sitä. Testasin koodia pienemmillä arvoilla ja aina sattui melko tasan kaksi kertaa liian usein heti toinen ympyrä osumaan ensimmäiseen. Suurimmaksi arvoksi sain 66. Kahdessa koeajossa vasta 66.s ympyrä osui johonkin aikaisempaan. Todennäköisimmin 14.s ympyrä osuu ensimmäisen kerran johonkin aikaisempaan.

Bernard Shawn: ”Tiede on aina väärässä: se ei koskaan ratkaise ongelmaa luomatta kymmentä lisää.”

Kommentit (1)

Keckuli
Seuraa 
Viestejä565
Liittynyt10.10.2013

Tein uuden ennätyksen. Kuvaan mahtui 377 ympyrää. Mutta sitten tarkistus ajossa olisi mahtunut vielä yksi lisää jos olisin vain jaksanut odottaa (koodin löytämä ympyrä punaisella kuvassa)

Bernard Shawn: ”Tiede on aina väärässä: se ei koskaan ratkaise ongelmaa luomatta kymmentä lisää.”

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat