Siis, miten noita putkaposteja pitäis ratkoa? :o
Jotkut on puhunu kaikenlaisista kaavoista ja ohjelmista, mut pitäiskö kehittää jollain kielellä joku ohjelma, mikä ratkaisisi tehtävän?
Muutenkin, en tajunnu mitään tosta tämänhetkisestä putkapostin selityksestä.
Tehtävänannot ovat sellaisia, että niiden ratkaisu ei ole käytännössä mahdollista ellet ohjelmoi ohjelmaa, joka ratkaisee sen.
Voit ajatella noita pieninä ohjelmointikilpailuina.
CyantLeap kirjoitti:
pitäiskö kehittää jollain kielellä joku ohjelma, mikä ratkaisisi tehtävän?
Kyllä.
Ilmeisesti siis pseudokoodiratkaisut ei kelpaa?
No jos se pseudo-koodisi ratkaisee tehtävän, niin kelpaahan se. Kyse ei ole siitä miten se oikea ratkaisu kysymykseen löydetään, vaan että se oikea ratkaisu löytyy. Tottakai noita saa laskea vaikka päässä, mutta kysymykset ovat luonteeltaan sellaisia, että parhaiden tulosten aikaansaaminen kyllä edellyttää hyvien algoritmienkin lisäksi sen verran laskentaa, että se on järkevintä toteuttaa ohjelmallisesti.
Ei muuten ole tämänhetkisessä tehtävässä ("Lukujenvihaaja") lainkaan mahdotonta tuo päässälaskukaan :) Tai ehkä paperilla ennemmin, mutta siis ilman ohjelmointia kuitenkin.
Paperilla voisi onnistua ihan hyvin, mutta jos on vielä taskulaskinkin käytössä, niin sitten ei ainakaan pitäisi tuottaa mitään ongelmia kunhan vain on ensin keksinyt kunnollisen algoritmin.
Binäärilukujen tunteminen ja käyttäminen auttaa tuossa tehtävässä erittäin paljon, mutta käyttötavan saat keksiä itse.
Hmm. Sain ratkaistua tehtävälle yleisen algebrallisen summalausekkeen. Pahus kun päässälaskutaito loppuu kesken!
no, selvä. Voisi tuon putkapostin tehtävän idean paremminkin selittää. En tajunnut mikä tossa on tarkotus. Vaikea silloin kehitellä ohjelmaa..
Kyllä tuo tehtävä ihan selkeä on. Myös ongelman hahmottaminen sanallisesta muodosta on tärkeä taito ratkaisun keksimisen ohella.
Tehtävässä oli muuten annettu vielä paljon selkeyttävä pöytämalli, mitä käytännössä haettiin:
Tehtävä
Jokaisessa testitapauksessa on joukko lukuja väliltä 1 - n, jotka kaikki täytyy hävittää. Jos n on 5, hävitettävänä on siis luvut 1, 2, 3, 4 ja 5. Silloin ykkösiä täytyy vähentää yhteensä 1 + 1 + 2 + 1 + 2 = 7 kertaa. Nämä määrät on laskettu tehtävän alussa kuvatun menetelmän avulla.
Hmm, alkaa nykimään 3.5 minuuttia mun perl koodilla ja lasketaan vasta 8 numeroa :P Pitää keksiä joki kiva jippo tuon ajan lyhentämiseen. Taulukointia tai jotain.
En ihan tajunnut tuota tehtävää.
Siis jos mul olis luku 8 hajotettavana ni pitäskö sit hajottaa 1, 2, 3, 4, 5, 6, 7, 8 vai pelkästään 8?
juha127 kirjoitti:
En ihan tajunnut tuota tehtävää.
Siis jos mul olis luku 8 hajotettavana ni pitäskö sit hajottaa 1, 2, 3, 4, 5, 6, 7, 8 vai pelkästään 8?
Eiköhän se siellä tehtävänannossa lue:
tehtävänanto kirjoitti:
Jokaisessa testitapauksessa on joukko lukuja väliltä 1 - n, jotka kaikki täytyy hävittää.
Eli esimerkissäsi luvut 1-8, ei pelkästään 8. Muuten tehtävä olisi aivan liian helppo, suurinkin noista annetuista luvuista on hajotettavissa sekunnin murto-osassa.
lapm kirjoitti:
Hmm, alkaa nykimään 3.5 minuuttia mun perl koodilla ja lasketaan vasta 8 numeroa :P Pitää keksiä joki kiva jippo tuon ajan lyhentämiseen. Taulukointia tai jotain.
Siis piti sanoa että 12345678, eli kahdeksan numeroista numeroa :P Netistä löytyi näppärä algoritmi joka pudotti tuonkin laskenta ajan 47 sekuntiin brute forcella.
Oma C++ toteutettu laskuri ei saanut oikeaa tulosta kuin 1 ja, kun kokeilin lukua 12345 laskemiseen kului about 1 min ja 14 sekkaa, eikä tulos kaiketi ollut oikein. Jotain pientä hiomista löytyy. :D
juha127 kirjoitti:
Oma C++ toteutettu laskuri ei saanut oikeaa tulosta kuin 1 ja, kun kokeilin lukua 12345 laskemiseen kului about 1 min ja 14 sekkaa, eikä tulos kaiketi ollut oikein. Jotain pientä hiomista löytyy. :D
Kokeiles 1-12 väliä, paperi+kynällä laskien kyisesellä välillä tulee 22 vähennystä. Helppo tapa testata joskos algoritmi toimisi oikein.
Meneekö se siis jotenkin näin?
n = 5;
5 - 1 = 4
4 - 2 = 2
2 - 1 = 1
1 - 1 = 0
Ja sitten lasketaan 4 + 2 +1 +0 = 7;
Ei mene.
n = 5; // Hajotettavana 1, 2, 3, 4, 5. // Hajotetaan yksi 1 - 1 = 0 // 1. vähennys // (Yksi vähennys) // Hajotetaan kaksi 2 / 2 = 1 1 - 1 = 0 // 2. vähennys // (Yksi vähennys) // Hajotetaan kolme 3 - 1 = 2 // 3. vähennys 2 / 2 = 1 1 - 1 = 0 // 4. vähennys // (Kaksi vähennystä) // Hajotetaan neljä 4 / 2 = 2 2 / 2 = 1 1 - 1 = 0 // 5. vähennys // (Yksi vähennys) // Hajotetaan viisi 5 - 1 = 4 // 6. vähennys 4 / 2 = 2 2 / 2 = 1 1 - 1 = 0 // 7. vähennys // (Kaksi vähennystä) // Yhteensä siis 7 vähennystä
Jooh... Ei ihme että oma ohjelmani antaa väärän tuloksen:$
Se laske kuinka montakertaa pitää jakaa ja vähentää yhteensä.
onko tuo 123 sitten 30
Ei, paljon enemmän.
Näkeehän sen jo luvusta. Ennen 123:sta on jo selvästi yli 30 paritonta lukua, joissa siis pitää jo ensi töikseen vähentää ykkönen.
toihan oli todella helppo!
kertokaa jos haluutte mun ohjelman!
njoo, piirtämällä tuokin selvis.
NanoSoft kirjoitti:
toihan oli todella helppo!
kertokaa jos haluutte mun ohjelman!
Lähettele ihmeessä ohjelmasi antamia tuloksia tarkistuslaitteelle, tällä tavoin vastaajien lukumäärä nousisi mukavasti 17*2 = 34:ään.
No eihän ole temppu eikä mikään kirjoittaa vaikka C:llä ohjelma, joka laskee n:stä ne vähennysten määrät. Ongelmia tulee vastaan siinä, kun n alkaa olla suurempi kuin 1234567898...
Raviable kirjoitti:
No eihän ole temppu eikä mikään kirjoittaa vaikka C:llä ohjelma, joka laskee n:stä ne vähennysten määrät. Ongelmia tulee vastaan siinä, kun n alkaa olla suurempi kuin 1234567898...
Vain brute-forcella (tai muulla vastaavalla algoritmilla) alkaa ilmenemään ongelmia jo tässä vaiheessa. Sopivan algoritmin avulla ongelmia alkaa tulemaan vasta sitten kun kokonaislukumuuttujan (64 bittiä) koko loppuu kesken. Tämänkin jälkeen vähennykset pystyy hyvinkin laskemaan sopivan kirjaston avulla lähes niin pitkälle kuin haluaa (n > ihan liikaa ja vähän päälle).
Niin, täytyy keksiä jotain muuta. :)
Aihe on jo aika vanha, joten et voi enää vastata siihen.