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

Faktorijel - broj nula?

[es] :: Art of Programming :: Faktorijel - broj nula?

[ Pregleda: 6140 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.



Profil

icon Faktorijel - broj nula?29.07.2004. u 13:55 - pre 223 meseci
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.
nix
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Faktorijel - broj nula?29.07.2004. u 17:31 - pre 223 meseci
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
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Faktorijel - broj nula?29.07.2004. u 18:25 - pre 223 meseci
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.
O_o
 
Odgovor na temu

mmirilovic
Mladen Mirilović
Čačak

Član broj: 10462
Poruke: 721
*.net
Via: [es] mailing liste



+1 Profil

icon Re: Faktorijel - broj nula?29.07.2004. u 22:19 - pre 223 meseci
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...
Pozdrav.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Faktorijel - broj nula?29.07.2004. u 23:23 - pre 223 meseci
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.
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Faktorijel - broj nula?30.07.2004. u 06:59 - pre 223 meseci
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;
    
}

O_o
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Faktorijel - broj nula?30.07.2004. u 10:08 - pre 223 meseci
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 :).
I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Faktorijel - broj nula?30.07.2004. u 11:13 - pre 223 meseci
U pravu si. Tvoje resenje, je brze i bolje.
O_o
 
Odgovor na temu

[es] :: Art of Programming :: Faktorijel - broj nula?

[ Pregleda: 6140 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

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