Keskustelu: Ohjelmointiputka: Putkaposti 31: Polttopuut

Uusi putkaposti on ilmestynyt:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ppuut

Jääkukkien ja alkukukkien jälkeen professori Viherkasvi on siirtynyt polttopuihin.

Hmm.. Taas sellainen tehtävä, että olen ihan pellolla. :D
Pitänee odottaa pari vuotta, että tajuaa noita.

1234567891011121314151617181920 20

Milläs tietotyypillä tuon laskeminen onnistuu? Ei taida löytyä C++:sta ainakaan valmiiksi?

Kolmen rivin python-koodilla löytyy 7 ekaan kohtaan ratkaisu. Sitten suoritusaika karkaa perusbrutella turhan suureksi.

long long int on 64 bittinen kokonaisluku, johon tuon pitäisi sopia.

Teuro kirjoitti:

long long int on 64 bittinen kokonaisluku, johon tuon pitäisi sopia.

cout << sizeof(long long int) << endl;

Tulostaa minulla 8.

Lisäksi seuraava koodi:

long long int a = 1234567891011121314151617181920;

Antaa virheilmoituksen:

koodi.cpp:17:21: warning: integer constant is too large for its type
koodi.cpp:17: virhe: kokonaislukuvakio on liian suuri tyypille ölongö

Onnea vaan niiden 64 bittisten lukujen kanssa kun sen toiseksi viimeisen vastaus vie >1900 bittiä.

P.S. Kuinka huijausta Wolfram|Alphan käyttäminen on tässä tehtävässä? :)

Itse tehtävä on helppo, mutta ei jaksa etsiä netistä kirjastoa dynaamisille tietotyypeille eikä toisaalta alkaa opettelemaan Pythoniakaan. Ei mielestäni kaikkein parhaiten valittu tehtävä.

Pitänee tehdä pythonill, ku c++ ei onnístu suoraan yli 64bittisten muuttujien käyttö... :(

Edit: Outoa, 3 ekaa menee ihan oikein, mutt sitten 5. ja 6 menevät väärin, vaikka niiden arvojen pitäisi kyll mahtua 64bittiseen unsigned long long int -tyyppiseen muuttujaan... :S

vehkis91 kirjoitti:

Edit: Outoa, 3 ekaa menee ihan oikein, mutt sitten 5. ja 6 menevät väärin, vaikka niiden arvojen pitäisi kyll mahtua 64bittiseen unsigned long long int -tyyppiseen muuttujaan... :S

Mulla kävi ihan samalla tavalla. Seitsemäs olikin sitten jo negatiivinen :D

Chiman kirjoitti:

Kolmen rivin python-koodilla löytyy 7 ekaan kohtaan ratkaisu. Sitten suoritusaika karkaa perusbrutella turhan suureksi.

Eihän tuossa 8. kohdassakaan mennyt vielä edes viittä minuuttia (Q8200 @ 2.8 GHz) :p

Grandi kirjoitti:

Itse tehtävä on helppo, mutta ei jaksa etsiä netistä kirjastoa dynaamisille tietotyypeille eikä toisaalta alkaa opettelemaan Pythoniakaan. Ei mielestäni kaikkein parhaiten valittu tehtävä.

Ehkä se vaikeus piilee siinä, että viimeiset kohdat saa laskettua inhimillisessä ajassa... Tällaiset tehtävät ovat juuri parhaita. Jokainen saa laskettua ensimmäisen kohdan vaikka käsin, mutta lopussa pitää jo miettiä jotakin älykkäämpää lähestymistapaa.

vehkis91 kirjoitti:

Pitänee tehdä pythonill, ku c++ ei onnístu suoraan yli 64bittisten muuttujien käyttö... :(

Edit: Outoa, 3 ekaa menee ihan oikein, mutt sitten 5. ja 6 menevät väärin, vaikka niiden arvojen pitäisi kyll mahtua 64bittiseen unsigned long long int -tyyppiseen muuttujaan... :S

Eikä muuten mahdu, ei ainakaan se tulos...

Mun koneesta loppuu mehut toss 8 kohdass, ku toteutin pythonill. :D Pitää varmaan säätää sitä algoritmia vähäsen. :D

Edit, Sami huomasin juu, ku tein pythonill. :P

Eikö noiden pitkien lukujen laskeminen onnistuisi ns. allekkainlaskualgoritmilla? Säilöisi ne numerot vaikka merkkijonoon josta aina muuttaa numeroksi kun täytyy suorittaa laskutoimitus ja sitten muuttaa stringiksi ja yhdistää isoon stringiin jossa on koko tulos.

Eihän noiden lukujen laskeminen ole mikään ongelma. En varsinkaan keksi, miksi millään kielellä pitäisi tehdä niin hankalasti, että pyörittelisi merkkijonojen kautta.

Varsinainen ongelma on, jos ei keksi tai osaa googlettaa sopivaa laskualgoritmia, niin 1234567891011121314151617181920 potenssiinkorotuksessa menee hitusen aikaa. Vaikka saisit tehtyä miljoona potenssiinkorotusta sekunnissa (joka tuskin on isomman pään luvuilla mahdollista) niin aikaa menisi silti 1234567891011121314151617,181920 sekuntia, eli yli 39122166849293961 vuotta. Eli voidaan siis sanoa, että isomman pään tehtäviä ei ole käytännössä mahdollista laskea yksinkertaisesti potensseja laskemalla ja näin saatuja tuloksia ynnäämällä.

Ihme_kala kirjoitti:

Eikö noiden pitkien lukujen laskeminen onnistuisi ns. allekkainlaskualgoritmilla?

Onnistuu. Tehtävän hankaluus ei ole siinä, miten isoilla luvuilla lasketaan, vaan siinä, että kaikkien 1234567891011121314151617181920 puun käyminen läpi yksitellen veisi kotikoneella triljoonia vuosia.