Tässä on uusi putkapostitehtävä:
https://www.ohjelmointiputka.net/postit/tehtava.
Tehtävän aihe on aika perinteinen: tiettyjä lukuja yhdistää jokin merkillinen matemaattinen ominaisuus, ja tehtävänä on laatia riitävän tehokas ohjelma näiden lukujen etsintään.
Jokaisen luulisi löytävän vähintään 10 lukua.
Kestipäs kauan keksiä mistä puuttuvat 8 lukua piilekseli :) Taisi liittyä juurikin noihin ezulin mainitsemiin 10 lukuun, joiden kaikkien piti löytää.
Hauska tehtävä. Tehokas algoritmi löytyi helposti: suoritusaika 1,3 s vanhalla koneella, kielenä Python.
Aika helppo tosiaan. Jaksankohan koodata ohjelman, kun on niin paljon muuta hommaa.
Chiman kirjoitti:
suoritusaika 1,3 s vanhalla koneella.
Siis mitä? Koneesiko on 1,3 s vanha?
Jaska kirjoitti:
Siis mitä? Koneesiko on 1,3 s vanha?
Olisikin. 130 Ms on lähempänä.
ezuli kirjoitti:
Jokaisen luulisi löytävän vähintään 10 lukua.
Itse asiassa niitä onkin 11. Alunperin olisi ollut 12, mutta Antti rajasi tehtävän luonnollisiin lukuihin.
*Wipii! Eka putkis minkä sain ratkaistua. Pythonilla 1.2s, tosin kone on 2GHz ja pari apulukua laskin erillään Pythonin rajoituksista johtuen.
(Muokkausaika ummessa.)
Sain optimoitua tuon oikeaoppisemmaksi, eli ei ylimääräisiä apulukuja. Aikakin parani heti 0,9 sekuntia.
VB:llä voi suoraan räknätä vain 29 numeroisia lukuja joten tarvi pientä kikkailua merkkijonojen kanssa jotta pääsee tuohon 50 numeroon. lopultakin kaikki 104 löytyi 0,83 sekunnissa.
Pienellä lisävirityksellä 0,51 s.
Hehe.. taidan olla käsi tai ajatus ei kulje.
Noh.. tää mun räpellys räknää kyllä oikein... Mutta kauan..... zzzZZZ
Taitaapi vaatia hieman optimointia..
Ja minä kun en tuohon mitään algoritmia keksi... :(
Tuo mun algoritmi ei varmaan niitä tehokkaimpia ole mutta pahin hidaste on muutama raskas funktio jota käytän..
Niistä kun pääsisi eroon.. Ongelmia tuottaa lukualueen suuruus.
Kannattaa oppia analysoimaan, miten kauan algoritmin suoritus suunnilleen kestää. Ensiksi miettimäni algoritmi oli kanssa tolkuttoman hidas. Nykyisellä algoritmilla ratkaisun saa hetkessä. On vaan niin paljon hommaa opiskelussa, että en juuri ehdi koodaamaan.
ezuli kirjoitti:
pari apulukua laskin erillään Pythonin rajoituksista johtuen.
Huomasinpa taas, että ohjelmointikielissä on hyvä olla jotain rajoituksia. Luvun 10**50 sijaan yritin käyttää 10**50 numeroista lukua, joka olisi tarvinnut melko paljon muistia. Olisi varmaan jäänyt putkis ratkaisematta, jos olisin tuolla suurehkolla testiluvulla saanut ohjelmaani testata.
*ps. Itsensä kanssa on helppo keskustella, ei tule vastaväitteitä.
ezuli kirjoitti:
*ps. Itsensä kanssa on helppo keskustella, ei tule vastaväitteitä.
No sitten ei ole tarpeeksi itsekriittinen :)
Kuitenkin, tähän voisikin jopa osallistua ja jotakin vääntää kun vaihteeksi vaikuttaa tehtävältä, joka on jopa omien ratkaisukykyjeni ulottuvissa.
Oma softa tekee varmaan hitaus ennätyksen...
Jos viikoksi jätän laskemaan niin saan kyllä kaikki.. :)
Mutta enpä taida vaivautua...
Sen sijaan keskityn keksimään järkevämpää tapaa laskea koska sellainen varmasti on.
Kokeilin Pythonilla ja erinäisten yritysten ja erehdysten jälkeen sain kuin sainkin tulkin tottelemaan. Aikaa meni kumsumin ratkaisuun 1,8 s tulosteineen, Ilman tulosteita (arvot tallennettuina merkkijonoon) 0,88 s. VB:llä pääsin alle 0,44 s. tulosteineen. Ilman tulostusta 0,37 s. Python on näemmä hidas tulostuksessa.
Olipas tämä helppo :)
Pythonilla 0,84 s tiedostoon tallentaen.
Pistetäämpä tänne ihan vertailun vuoksi omien ohjelmieni suoritusaikoja.
C:llä erästä näppärää suurten lukujen pyörittelemiseen kelpaavaa kirjastoa käyttävä ohjelma ratkaisee tämän vain 15 millisekuntissa.
Samanlainen PHP:llä tehdyn samaista kirjastoa käyttävän ohjelman suoritus puolestaan kestää 0.390 sekuntia (josta user-aika Linuxissa tosin 0.300 sekuntia).
Suorittimena Pentium 4 2.8GHz kummassakin tapauksessa ja ohjelmat tulostivat luvut näytölle (PHP:llä tehty ohjelma tulosti ne jopa suuruusjärjestyksessä).
15 ms :O
Kaipa tuon omankin virityksen algoritmiä voisi optimoida, mutta loppujen lopuksi aika pieni merkitys noin käytännössä :p
<bleep>
Tässä on joku kikka.
Löytyis ny edes sopiva kirjasto isojen numeroiden kanssa kikkailuun.
Jaksaiskohan sitä bruteforcen koodailla...
Ainut tapa mitä keksisin olisi tämmöinen suunnilleen:
For i = 0 To (10 ^ 50) ' tähän tarkistus Next i
KingOfTheWorld kirjoitti:
Ainut tapa mitä keksisin olisi tämmöinen suunnilleen:
For i = 0 To (10 ^ 50) ' tähän tarkistus Next i
Mikäs idea tässäkin viestissä oli?
Draiz kirjoitti:
Mikäs idea tässäkin viestissä oli?
Jotain informaatiota siinäkin oli. Moderaattorit, voisko noita kirosanoja siivota?
setä kirjoitti:
voisko noita kirosanoja siivota?
Voihan nuo, jos niin halutaan.
Kirosanat on osa suomenkieltä ja oiva tehostus keino.
Mitä niitä nyt turhaan sensuroimaan. :P
Täällä on enimmäkseen asialliset keskustelut ja värikästä kieltä mutta kirosanat rumentavat. Huono tehostuskeino julkisilla sivuilla.
Missä täällä on muka kirosanoja? o_O
Ei niitä olekaan, kun Blaze sensuroi ne.
No, mutta minusta kirosanoja ei pitäisi sensuroida, paitsi jos 70% virkkeestä koostuu niistä. Kyllä pieninä annoksina voimasanat ovat OK.
pakko lainata viznutia, kun paremmin sen pisti, että kirosanat ovat sinänsä ok, mutta ei niitä välimerkkeinä pidä käyttää.
Aivan. Edellinen ukkosenjumala jonka nakkasin oli humoristinen turhautumisen ilmaisu. :D
Mutta takaisin itse asiaa.. Mathematicalla kikkailin ja sain melkoisen määrän sopivia lukuja.. Pitäisi kehitellä siitä vielä oma ohjelma.
Tämäkin tehtävä oli varsin mielenkiintoinen ja tulin vaihteeksi vähän viritelleeksi ohjelmaani. Lukualueesta 10**5000 näyttäisi löytyvän 4566 sopivaa lukua. Noiden laskemiseen meni javalla ja hiukan modatulla apfloat-kirjastolla noin 43 min AMD Athlon 3000+:lla.
KingOfTheWorld kirjoitti:
Ainut tapa mitä keksisin olisi tämmöinen suunnilleen:
For i = 0 To (10 ^ 50) ' tähän tarkistus Next i
En mäkään parempaa keksiny. Oon ihan huono enkä vaan osaa ajatella mitään :(
Lukuja löytyy kiitettävästi mutta pyöritys kestää tuhat vuotta.
Ehkei brute force ollutkaan järkevä vaihtoehto, ei vaan tullut muuta mieleen :P
Minä suunnittelin brute-force haun, kun ei muuta tullut mieleen. Ensiksi testataan luvut 1,2,3,..., sitten 1^2,2^2,3^2,... ja niin edelleen kasvattaen eksponenttia koko ajan 1:llä.
ajobenchmarkeista päätellen löytyy paljon optimaalisempikin tapa..
Pitäisi melkein sensuroida tuo Jaskan paljastus, tuohan on melkein valmis ratkaisu.
Jaa ei tuollasella brutettamisella pääse mihinkään.
Tai no.. ehkä viikossa.
Metabolix kirjoitti:
Pitäisi melkein sensuroida tuo Jaskan paljastus, tuohan on melkein valmis ratkaisu.
Eikös se kilpailuaika mennyt jo?
Ei, vastauksiahan voi lähettää vielä useampaankin postiin. Ne päättyvät vasta, kun vastaussivu ei hyväksy vastauksia ja malliratkaisut julkaistaan. (Ja eiväthän ne kilpailuja ole, vai kuinka?)
Saatte sensuroida tuon minun viestini vapaasti. Mielestäni malliratkaisut voisivat kyllä tulla huomattavasti nopeammin.
Oma viritys on suhteellisen optimoitu bruteforce eikä sillä todellakaan pitkälle pötkitä..
Aihe on jo aika vanha, joten et voi enää vastata siihen.