Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Šta nije u redu sa ovim programom?

[es] :: Art of Programming :: Šta nije u redu sa ovim programom?

[ Pregleda: 2567 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Exit
Djordje Vukovic
Berane

Član broj: 45956
Poruke: 92
*.crnagora.net.



Profil

icon Šta nije u redu sa ovim programom?01.08.2007. u 16:29 - pre 203 meseci
Vidio sam ovaj zadatak na z-treningu

Citat:

Oznacimo sa p proizvod svih brojeva od 1 do n (1 <= n <= 10000). Napisati program koji izracunava poslednju cifru broja p (zapisanog u dekadnom sistemu) razlicitu od 0.

Sa standardnog ulaza se ucitava broj n, a program treba da na standardni izlaz ispiše poslednju nenultu cifru broja p.

Primer:

Ulaz:
10

Izlaz:
8

Komentar: 1*2*3*4*5*6*7*8*9*10 = 3628800 pa je poslednja nenulta cifra 8.


i evo mog koda. Radi dobro sa malim brojevima ali kad se ukuca neki veći broj kao ulazni (n) program blokira.

Code:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    
    
    int n, p = 1, res;
    
    cout<<"Unesi broj n:"<<endl;
    cin>>n;
    if (n< 1 || n>10000) {
    cout<<"Invalidna vrijednost\n";
    return 0;
    }
   
    for (int i =1; i<=n;i++){
        p=p*i;
        }
  
   res = p % 10;
   if (res != 0){ cout<<res<<endl;}
   else {
        while (res == 0) {
              p = p / 10;
              res = p % 10;
              }
              cout<<res<<endl;
              }
         
    
    system("PAUSE");
    return EXIT_SUCCESS;
}


Može li mi neko reći gdje je greška?
Underground
 
Odgovor na temu

DjoleReject
Djordje Knezevic
Zvezdara

Član broj: 85258
Poruke: 309
*.dynamic.sbb.co.yu.



+1 Profil

icon Re: Šta nije u redu sa ovim programom?01.08.2007. u 17:11 - pre 203 meseci
ti mnozis broj p sa samim sobom uvecanim za jedan, sto je slicno kvadriranju. Posto si ogranicio n na 10000 u kasnijim iteracijama dobijas sumanuto velike brojeve koji ne staju u int promenljivu. Resenje je u tome da p bude tipa long ili da smanjis mogucu velicinu n, s tim da i long ima svoja ogranicenja.
De si Deda...
 
Odgovor na temu

Exit
Djordje Vukovic
Berane

Član broj: 45956
Poruke: 92
*.crnagora.net.



Profil

icon Re: Šta nije u redu sa ovim programom?01.08.2007. u 17:54 - pre 203 meseci
Ne mogu n da smanjim jer je u zadatku zadato da mora da bude između 1 i 10000 (čudi me da nisu stavili neku manju vrijednost). A ni long mi ne pomaže.
U svakom slučaju hvala na pomoći.
Underground
 
Odgovor na temu

NastyBoy
Bojan Nastic
UK

Član broj: 12041
Poruke: 895
*.plus.com.



+4 Profil

icon Re: Šta nije u redu sa ovim programom?01.08.2007. u 18:21 - pre 203 meseci
Heh, srecno sa tim faktorijelom od 10000.

Da bi video zbog chega tvoj algoritam mora potpuno drugachije da radi, pogledaj koliki je taj faktorijel:
Citat:
10000 factorial is 35,659 digits long

http://gimbo.org.uk/texts/ten_thousand_factorial.txt
 
Odgovor na temu

Exit
Djordje Vukovic
Berane

Član broj: 45956
Poruke: 92
85.94.123.*



Profil

icon Re: Šta nije u redu sa ovim programom?01.08.2007. u 23:42 - pre 203 meseci
A kako da drugacije organizujem program a da zadovolji sve uslove iz zadatka?
Underground
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4902
*.tekostolac.co.yu.

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: Šta nije u redu sa ovim programom?02.08.2007. u 09:47 - pre 203 meseci
Ovu temu ću prebaciti u Art Of Programming jer se po pretpostavci ovde pre radi o izboru (pronalaženju) optimalnog algoritma nego o samoj implementaciji koja bi trebala biti samo formalnost.

Siguran sam da nije predviđeno da se rešenje pronalazi tako što se prvo izračuna ceo faktorijel i spakuje u neki niz (od 35,659 elemenata, kako precizno reče NastyBoy), već je pretpostavljam fora u tome da se čuva samo neki ključni deo privremenog proizvoda, odnosno da se čuva određeni broj cifara nižeg nivoa, tj onih sa desne strane (do prve nenulte vrednosti ujključujući i nju).

E sad, koliko treba - ne znam, verovatno je to neki broj koji varira (pogledaj u rešenju koje je dao NastyBoy koliko ima tih nula sa desne strane za 10,000!). Možda možeš pokušati da simuliraš ručno množenje i uočiš neku zakonistost.

Celu priču komplikuje reč NENULTU:
Citat:

[...] poslednju nenultu cifru broja p [...]

... jer da nije toga, bilo bi lako ;)


Ok, da ne dužim, evo prebacujem u Art Of Programming... pa ako neko ima slobodnog vremena neka pokuša...
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+711 Profil

icon Re: Šta nije u redu sa ovim programom?02.08.2007. u 09:57 - pre 203 meseci
Umesto da pamtite ceo proizvod, pamtite samo poslednju nenultu cifru.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
195.252.119.*



+2789 Profil

icon Re: Šta nije u redu sa ovim programom?02.08.2007. u 10:03 - pre 203 meseci
Problem je što standardni celobrojni tipovi imaju ograničenje, tako da se zadatak može rešiti u principu na dva načina:

1) Definišeš nov tip - BigInteger, gde se celi nenegativni brojevi pamte kao nizovi cifara, kao i odgovarajuće operacije nad njim.
2) Rešiš problem matematički tako da ne zahteva rad sa velikim brojevima.

U matematici se taj broj p označava sa n!, a znak "!" se čita "faktorijel". Tebi treba poslednja nenulta cifra broja n!. Kada bi n! rastavio na proste činioce, u tom rastavljanju bi broj 2 dobio u puta i broj 5 v puta (u>v), tako da bi za neki prirodan broj q (koji nije deljiv ni sa 2 ni sa 5) važilo n!=2u5vq, odnosno n!=10vr, gde je r=2u-vq. Pošto broj r nije deljiv sa 5, on ne može biti deljiv ni sa 10. Kada iz zapisa broju n! obrisao sve nule ne kraju, dobio bi zapis broja r. Dakle, tebi treba poslednja cifra broja r.

Broj q možeš računati kao f(1)*...*f(n), gde je f(k) broj koji se dobija delenjem broja k sa 2, odnosno 5, dokle god se takva delenja vrše bez ostatka. Ostaje ti samo da odrediš brojeve u i v. To je upravo broj svih delenja sa 2, odnosno sa 5 (koristi brojače). Ostaje da se q pomnoži u-v puta sa 2. Pošto ti treba samo poslednja cifra broja r, sva računanja možeš da vršiš po modulu 10, tako da se ne radi sa velikim brojevima. Evo rešenja:
Code:

#include <iostream>

using namespace std;


int main()
{
    int razlika = 0, r = 1, i, n;

    cout << "Unesi n: " << endl;
    cin >> n;

    for (i=1; i<=n; i++)
    {
        int c = i;

        while (c%2==0)
        {
            razlika++;
            c /= 2;
        }

        while (c%5==0)
        {
            razlika--;
            c /= 5;
        }

        c %= 10;
        r *= c;
        r %= 10;
    }

    for (i=0; i<razlika; i++)
    {
        r *= 2;
        r %= 10;
    }

    cout << "Rezultat je " << r << endl;

    return 0;
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Exit
Djordje Vukovic
Berane

Član broj: 45956
Poruke: 92
85.94.116.*



Profil

icon Re: Šta nije u redu sa ovim programom?02.08.2007. u 10:31 - pre 203 meseci
Odličan algoritam, i odlično implementiran.
Mada ga ono na www.z-trening.com što bi trebalo da izigrava kompajler ne prihvata kao tačno rešenje (iako sam dodao funkciju validacije unosa). Ali meni je bitno da sam shvatio kako treba da ide ovaj algoritam.
Puno hvala na pomoći.
Underground
 
Odgovor na temu

[es] :: Art of Programming :: Šta nije u redu sa ovim programom?

[ Pregleda: 2567 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.