Keskustelu: Ohjelmointikysymykset: C++ ja lukujen käsittely

Terve, Olen ohjelmoinut C++ noin viikon, erittäin vähän siis. Ajattelin kuitenkin osallilstua ohjelmointiputkan kilpailuun, jossa on siis tarkoituksena etsiä lukuja, joiden summa korotettuna yhtä monenteen potenssiin kuin luvussa on numeroita on luku itse. Kukaan tuskin ymmärsi. ;) Eli siis esim. luku 81, 8 + 1 = 9 ja 9*9 on taas 81. Tai 512, 5 + 1 + 2 = 8 ja 8*8*8 = 512.

Ohjelmani testaa tällä hetkellä lukuja väliltä 100 000 000 - 999 999 999 ja löytää tasan yhden luvun joka on 671088640. Tämä luku ei toteuta ehtoa. Pienemmillä luvuilla ohjelma toimii hyvin. Mitä minun pitää tehdä? Niin ja koodi on tässä:

#include <iostream.h>
#include <cstdio>
#include <cstdlib>


int main()
{
    unsigned long int ekaluku;
    for (ekaluku = 100000000; ekaluku < 999999999  ; ekaluku = ekaluku + 1)
    {
    int ykkoset = ekaluku%10;
    int kymmenet = ((ekaluku-ykkoset)/10)%10;
    int sadat = ((ekaluku-ykkoset-kymmenet*10)/100)%10;
    int tuhannet = ((ekaluku-ykkoset-kymmenet*10-sadat*100)/1000)%10;
    int kymmenettuhannet = ((ekaluku - ykkoset - kymmenet*10 - sadat*100 - tuhannet * 1000)/10000)%10;
    int sadattuhannet = ((ekaluku - ykkoset - kymmenet*10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet*10000)/100000)%10;
    unsigned long int miljoonat = ((ekaluku - ykkoset - kymmenet * 10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet * 10000 - sadattuhannet * 100000)/1000000)%10;
    unsigned long int kymmenetmiljoonat = ((ekaluku - ykkoset - kymmenet * 10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet* 10000 - sadattuhannet * 100000 - miljoonat * 1000000)/10000000)%10;
    unsigned long int sadatmiljoonat = (ekaluku - ykkoset - kymmenet * 10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet * 10000 - sadattuhannet * 100000 - miljoonat * 1000000 - kymmenetmiljoonat * 10000000)/100000000;
    int summa = ykkoset + kymmenet + sadat + tuhannet + kymmenettuhannet + sadattuhannet + miljoonat + kymmenetmiljoonat + sadatmiljoonat;
    unsigned long int potenssi = summa * summa * summa * summa * summa * summa * summa * summa * summa;

    if (ekaluku == potenssi){
    cout << ekaluku;
    cout << "\n";
}

}

    cout << "Laskettu";
    system("PAUSE");

    return 0;
}

Ensinnäkin, ei tarvitse vähennellä niitä pienempiä numeroita. Tunnettu tosiseikka C:ssä on, että 9/10 = 0, eli pyöristys tapahtuu alas.

ykkoset = luku % 10;
kymmenet = (luku / 10) % 10;
sadat = (luku / 100) % 10;

Lisäksi summaan pääsee vielä tätäkin helpommin käsiksi. Kuten äsken todettiin, luku % 10 antaa sen viimeisen numeron. Eihän meidän toki tarvitse tietää, osoittaako numero ykkösiä vai kymmeniä, kun se kuuluu summaan kuitenkin. Kun luku jaetaan kymmenellä, sen kymmeniä osoittavasta numerosta tuleekin sen pienin numero.

summa = 0;
while (luku > 0) { // Kun luku on suurempi kuin nolla (muista, että 9 / 10 = 0, eli tämä loppuu kyllä)
    summa += luku % 10; // Lisätään siihen yksi numero
    luku /= 10; // Jaetaan luku kymmenellä, niin kymmenistä tulee ykkösiä
}

Sitten vielä, tuossahan et kokeile muita potensseja kuin yhdeksättä. Tarvitset silmukan, jossa kokeilet muutkin potenssit. Ja miksi noin isoista etsit? Tarkistaminenhan on helpompaa, kun laskee pienemmillä luvuilla. Virhe taas johtunee siitä, että 671088640:n numeroiden summa on 40, ja 40^9 = 262144000000000, joka taas ei mahdukaan integeriin.

Ja lopuksi vielä mainittakoon, että tuo on se tapa, jolla laskeminen kestäisi hyvin moninumeroisen määrän suuria määriä lukuisia vuosia.

Millaista muuttujaa pitäisi käyttää, että arvo mahtuisi lukuarvoalueelle? Etsin noista isoista siksi, että pienimmistä olen jo useita löytänytkin...

10^50 näyttäisi vaativan 167-bittisen muuttujan. Joudut hankkimaan jostakin apukirjaston (niitä on ihan helppokäyttöisiäkin) tai koodaamaan itse esimerkiksi luokan pitkille luvuille. Tyyppi unsigned long long tai MS:n kääntäjässä __uint64 riittää sinne 10^10 kokoluokkaan.

Mistä tuollaisen kirjaston voisi löytää? Yritin etsiä, mutta en löytänyt mitään (mielestäni) ihmeellistä.

http://www.shoup.net/ntl/
http://www.shoup.net/ntl/doc/tour-ex1.html
http://www.swox.com/gmp/
http://www.kepreon.com/~matt/bigint/index.html
Siinä valmiiksi Googletettuna. NTL:ää joskus kokeilin itse, se ainakin oli helppo ja ilmeisen toimiva. Myös tuo viimeinen vaikutti parin sanan perusteella ihan kelvolliselta. GMP taitaa olla NTL:lle vaatimuksena, jos oikein ymmärsin (voin olla väärässäkin). NTL:stä on muistaakseni DevPak, jos Dev-C++:aa käytät, mutta devpaks.org oli näköjään nyt nurin.

Kiitos! Yritin tuota NTL:ää asentaa, mutta ei toimi... Ja miten ylipäätänsä tuota kirjastoa käytetään kun luvut ovat suuria? Kirjasto tietysti sisällytetään ohjelmaan ja sitten...? Käytänkö int-tyyppisiä muuttujia vai jotain ihme ZZ-muuttujaa, jota ohjelman manuaalissa mainostetaan.

Sitä ZZ:aa hyvinkin. Jos tuolta yritit ladata, niin saat vain lähdekoodit ja sinun täytyy kääntää kirjasto itse. DevPak näyttäisi olevan ainakin osoitteessa http://www.pr.infn.it/pub/materialedidattico/windid_cd1/win/devc /devpak/?C=S;O=A nyt, kun ei vieläkään devpaks.org toimi.

Muista siis include ja projektin asetuksista oikean kirjaston lisääminen (linkkeriparametri -lntl tai jokin vastaava, katso, mitä paketista asentuu).

Latasin ja asensin GMP-devpakin ja NTL-devpakin. Sitten lisäsin "projects"-välilehden kohdasta "project options" ja edelleen "parameters"-kohdasta "libntl.a"-tiedoston.
Kirjoitin myös ohjelman alkuun näin:

#include <iostream.h>
#include <cstdio>
#include <cstdlib>
#include <NTL/ZZ.h>
#include <NTL/config.h>

Ei tunnista vieläkään tuota ZZ-muuttujaa.

Unohdit ilmeisesti lisätä rivin

using namespace NTL;

Sama homma kuin C++:n standardikirjaston kanssa.

Hassua, ensimmäisen viestin koodissa ei lue missään "using namespace std;" mutta silti cout ilmeisesti toimii..? Noh, se taitaa olla tätä Windows-ohjelmien strategiaa ettei kerrota mikä pitää tehdä itse ja minkä ohjelma tekee automaattisesti. Itse olen tähän mennessä onneksi voinut luottaa siihen että jos en ole kirjoittanut using namespacea enkä komennon eteen std:: (tai jotain vastaava) niin se ei myöskään ole toiminut. Jee.

Lisäsin. Ei toimi. Kerrompa tässä nyt yksityiskohtaisesti, että mitä teen.

1. Latasin ja asensin GMP, - NTL-devpackin.

2. Avaan Dev-C++:ssa uuden projektin.

3. Kuva kertoo... Valitsen siis "projects"-kohdan.
http://i99.photobucket.com/albums/l312/tuomas_2006/kuva1.jpg
4. Valitsen "LIBNTL.a":n ja painan ok.
http://i99.photobucket.com/albums/l312/tuomas_2006/kuva2.jpg

5. Tässä itse koodi:

#include <iostream.h>
#include <cstdio>
#include <cstdlib>
#include <NTL/ZZ.h>
#include <NTL/config.h>



using namespace NTL;

int main()
{
    int ekaluku;
    for (ekaluku = 100000000; ekaluku < 999999999  ; ekaluku = ekaluku + 1)
    {
    int ykkoset = ekaluku%10;
    int kymmenet = ((ekaluku-ykkoset)/10)%10;
    int sadat = ((ekaluku-ykkoset-kymmenet*10)/100)%10;
    int tuhannet = ((ekaluku-ykkoset-kymmenet*10-sadat*100)/1000)%10;
    int kymmenettuhannet = ((ekaluku - ykkoset - kymmenet*10 - sadat*100 - tuhannet * 1000)/10000)%10;
    int sadattuhannet = ((ekaluku - ykkoset - kymmenet*10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet*10000)/100000)%10;
    unsigned long int miljoonat = ((ekaluku - ykkoset - kymmenet * 10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet * 10000 - sadattuhannet * 100000)/1000000)%10;
    unsigned long int kymmenetmiljoonat = ((ekaluku - ykkoset - kymmenet * 10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet* 10000 - sadattuhannet * 100000 - miljoonat * 1000000)/10000000)%10;
    unsigned long int sadatmiljoonat = (ekaluku - ykkoset - kymmenet * 10 - sadat * 100 - tuhannet * 1000 - kymmenettuhannet * 10000 - sadattuhannet * 100000 - miljoonat * 1000000 - kymmenetmiljoonat * 10000000)/100000000;
    int summa = ykkoset + kymmenet + sadat + tuhannet + kymmenettuhannet + sadattuhannet + miljoonat + kymmenetmiljoonat + sadatmiljoonat;
    unsigned long int potenssi = summa * summa * summa * summa * summa * summa * summa * summa * summa;

    if (ekaluku == potenssi){
    cout << ekaluku;
    cout << "\n";
}

}

    cout << "Laskettu\n";
    system("PAUSE");

    return 0;
}

Tuossa viimeisimmässä kuvassa näkyy Compiler kohta, laitapa sinne parametriksi -lntl, tai sitten sinne C++-Compiler kohtaan.

Tumpelo kirjoitti:

Hassua, ensimmäisen viestin koodissa ei lue missään "using namespace std;" mutta silti cout ilmeisesti toimii..? Noh, se taitaa olla tätä Windows-ohjelmien strategiaa ettei kerrota mikä pitää tehdä itse ja minkä ohjelma tekee automaattisesti. Itse olen tähän mennessä onneksi voinut luottaa siihen että jos en ole kirjoittanut using namespacea enkä komennon eteen std:: (tai jotain vastaava) niin se ei myöskään ole toiminut. Jee.

Tuossa käytetään vanhaa include.h:ta, jossa niitä ei ole määritelty nimiavaruuteen.
Nykyään pitää käyttää include-otsikkotiedostoa (ilman päätettä), jossa nämä tavarat ovat määriteltynä kyseiseen nimiavaruuteen.

Jaa-a, eiköhän tämä ollut sitten tässä. Saa tämä(kin) ohjelma jäädä. Sain käännettyä ohjelman ZZ-muutujilla, mutta ohjelma jäi laskemaan lukuja erittäin pitkäksi aikaa. (Jouduin keskeyttämään) Kiitokset kaikille avusta!

Nyt kun kyseinen kilpailu on onnellisesti loppunut niin voisiko joku tehtävän c++:lla ratkaissut laittaa koodin näkyviin, tai antaa muuta vinkkiä...

Eihän se ole minnekään loppunut. Se loppuu vasta, kun siltä sivulta lähtee vastauslinkki pois ja tulee mallivastauksia. Jos nyt tässä uskaltaa vinkkiä antaa, niin montakos noita mahdollisia numeroiden summia onkaan? Oho, 50 numeroa ja 9 suurin, eli 450... Ja kakkostakaan ei tarvitse korottaa kuin 167. potenssiin, jotta pääsee ulos sallitulta lukualueelta... ;)

Metabolix kirjoitti:

Eihän se ole minnekään loppunut.

Ai eikö se kisa loppunutkaan vielä?... :P

Jees, nyt sain ohjelman etsimään ko. lukuja omatoimisesti. Enää tarvitsee vain saada lisättyä tuo apukirjasto...