Faktorijel - broj nula?

[ BIHacker @ 29.07.2004. 13:55 ] @

Potrebno je izracunati sa koliko se nula zavrsava faktorijel datog broja u
datoj bazi. (1<Baza<=800)

Primjer:

Broj baza br. nula
2 10 0
5 16 0
5 10 1
30 000 10 7498

S bazom deset je jednostavo izracunati (to sam dosad uspio), al kako s ostalim bazama,npr 5!=120 (u decimalnom) al u heksadecimalnom 5!=78, pa se ne zavrsava ni jednom nulom.

[ Srđan Krstić @ 29.07.2004. 17:31 ] @

Pa opet nije tesko.
Neka je recimo baza b, a treba da nadjes za a!. Rastavis b na proste cinioce, uzmes najveci od njih (za 10 bi to bio 5), neka je on x. Sad delis a redom sa x, x^2, x^3, ... dokle god dobijas rezultat >0. Sve te medjurezultate sabiras i ono sto dobijes je ni manje ni vise nego trazeni broj nula. E da jedino treba da obratis paznju ako pri rastavljanju b na proste cinioce najveci cinioc nije jedinstven, npr 16=2*2*2*2. Neces da uzmes 2, tj uzeces 2, ali ce na kraju dobijeni rezultat za nule da podelis sa 4. Nadam se da je jasno. Poz

[ blaza @ 29.07.2004. 18:25 ] @

Bazu faktorizujes, i napises je u sledecem obliku:
baza = faktor1 ^ n1 * faktor2 ^ n2 * ... * faktork ^ nk.
Napravis petlju for i=2..broj. Svako i faktorizujes, i brojis ukupan broj ponavljanja svakog faktora. Na kraju ove operacije znaces odgovarajuce ax u formuli:
broj! = 2 ^ a2 * 3 ^ a3 * 5 ^a5 * 7 ^a7 * 11 ^ a11 * ...
Sada posmatras samo one faktore koje si dobio faktorizacijom baze (faktor1..faktork). Za ove faktore nadjes odgovarajuce vrednosti axi.
Za svaki od faktora faktor1..faktork, i=1..k izracunas axi/ni (celobrojno deljenje). Najmanja vrednost iz skupa dobijenih brojeva odgovarace broju nula izraza broj! zapisanom u brojnom sistemu sa osnovom baza.
IsrkiboyI-ovo resenje nije dobro.
Posmatraj npr. bazu b=3*3*3*3*5=405. Broj nula ne moze biti veci od broja petica, ali je pitanje ima li dovoljno trojki. Svaki od faktora se mora proveriti.

[ mmirilovic @ 29.07.2004. 22:19 ] @

Izračunaj faktorijel. Faktorijel i baza neka ti budu izraženi u decimalnom
brojnom sistemu. Faktorijel podeli sa bazom. Ako je deljenje bez ostatka
faktorijel se u datoj bazi završava sa nulom. Nastavi deljenje sa bazom
dokle god je deljenje bez ostatka. Onoliko puta koliko si podelio faktorijel
sa
bazom bez ostatka toliko ima nula na kraju faktorijela u datoj bazi/brojnom
sistemu...

[ Srđan Krstić @ 29.07.2004. 23:23 ] @

Moje resenje je vrlo dobro. Lepo sam naglasio za slucaj da se ponavlja faktor. Naravno da se nece posmatrati petice nego trojke. Nema potrebe posmatrati svaki faktor, vec samo najveci jer se on sigurno pojavljuje najmanji broj puta. Naravno ako u faktorizaciji imas p^q, treba posmatrati ceo stepen (p^q) kad se bira kojim ce se faktorom deliti, tj. u primeru ne 3 nego 81, ali se deli sa 3, pa se posle div-uje sa 4 (posto je 3^4). Mmirilovic je dao logicno straightforward resenje ali ne verujem da bi bilo od neke pomoci, jer verovatno ni vremenski ni memorijski ne bi blo zadovoljavajuce.

[ blaza @ 30.07.2004. 06:59 ] @

Inspirisan IsrkiboyI-ovim primerom nasao sam "poboljsanje":
0.Ulazni parametri su baza i broj;
1.Nadjes najveci delioc baza-e oblika faktor^stepen, gde je faktor prim broj.
2.Inijalizujes brojac rezultat=0
3.Za svaki broj, pocev od 2, pa do broj, delis sa faktor do god je deljiv sa istim, i za svako uspesno deljenje inkrementiras brojac rezultat.
4.broj nula bice jednak celobrojnom deljenju rezultat/stepen

Citat:

Sad delis a redom sa x, x^2, x^3, ... dokle god dobijas rezultat >0. Sve te medjurezultate sabiras i ono sto dobijes je ni manje ni vise nego trazeni broj nula.

Ovde se krije greska. Delenje broj-a sa stepenima faktor-a dace pogresne rezultate. Treba radti na nacin dat u tacki 3.

Evo (grubog) souce koda:

Code:

#include <iostream>
using namespace std;
int main(void){
    cout << "\nUnesi broj: ";
    int broj;
    cin >> broj;
    cout << "\nUnesi bazu: ";
    int baza;
    cin >> baza;
    int baza_ = baza;
    int najveci = 0;
    int faktor = 1;
    int stepen = 1;
    for(int i=2; (baza_>1)&&(i*i<=baza); i++){
        int k=0;
        int l=1;
        while(!(baza_%i)){
            baza_/=i;
            l*=i;
            k++;
        }
        if(l>najveci){
            najveci=l;
            faktor=i;
            stepen=k;
        }
    }
    if(baza_>najveci){
        najveci=faktor=baza_;
        stepen=1;
    }
    cout << "\nNajveci delioc baza-e oblika faktor^stepen je: " << najveci;
    cout << "\nfaktor = " << faktor << " stepen = " << stepen;
    int ukupno = 0;
    for(int i=2;i<=broj;i++){
        int k = i;
        while(!(k%faktor)){
            k/=faktor;
            ukupno++;
        }
    }
    int broj_nula=ukupno/stepen;
    cout << "\nBroj nula je: " << broj_nula;

}

[ Srđan Krstić @ 30.07.2004. 10:08 ] @

Blazo, slazem se da je tvoje resenje dobro, s tim sto si trebao da naglasis da rezultat sabiras samo ako je pri deljenju dobijen celobrojni rezultat. Ali moram ponovo da naglasim da je i moje resenje dobro, razmisli malo, u sustini radi istu stvar, samo dosta brze. Jer kad ti podelis broj sa faktor, ti ustvari dobijes koliko ima brojeva koji su <= broj a deljivi sa faktor, t. tj kod tebe kad delis sve one za koje si dobio rezultat >= 1. Sad kad delis sa faktor^2 dobijas sve one kod kojih si pri deljenju dobio >= 2, itd. i konacno tvoj abir bice jednak mom zbiru. Btw, umorih se vise od objasnjavanja, ako mi jos neko kaze da nesto nije dobro, dacu vam kod pa vi razmisljajte zasto radi :).

[ blaza @ 30.07.2004. 11:13 ] @

U pravu si. Tvoje resenje, je brze i bolje.