Ĺadny brzuch
Poszukuje algorytmu lub poprostu wytłumaczenia na następujące pytanie:
Podaj ile zer ma na końcu liczba n!. Liczba n może być nieskończenie duża :D
Jak narazie obiło mi się o uszy, że to jest związane ze symbolem Newtona:
n!/(k!(n-k)!
Ale nie wiem jak to mam wyliczyć.
PS. Proszę nie piszcie mi jak wygląda obliczenie n! bo to wiem :P
Słuchaj, ile zer ma na końcu, to można sprawdzić liczba mod 10 czy kończy się zerem a potem sprawdzamy dla 100, 1000 itd.
program liczzera;
var
Liczba, x, reszta : Longint;
ilezer : Byte;
begin
readln(Liczba);
ilezer := 0;
x := 10;
reszta := Liczba mod x;
while (reszta = 0) do
begin
ilezer := ilezer+1;
x := x * 10;
reszta := Liczba mod x;
end;
writeln(ilezer);
end.
Ten program liczy, ile ma zer na końcu podana przez Ciebie liczba. Możesz uzyć tego sposobu w swoim programie.
Użytkownik Balcerowicz edytował ten post 27 luty 2005, 14:42
no spoko tylko malutki problem pojawia sie gdy n = 1000000000 albo wiecej :) wtedy prawdopodobnie obliczenia na statystycznym pc potrwaja rok i bedzie potrzebne troche duzo ramu :]
napisz do czego Ci to jest potrzebne to będzie łatwiej :) z symbolem Newtona to raczej nie ma nic wspólnego :)
takie cus powinno dzialac :) teraz tylko przerobic na brzydkiego pascala :P
#include <iostream> using namespace std; int main() { size_t n; cout << "podaj n: "; cin >> n; cin.ignore(); size_t zeros = 0; for ( size_t i = n/5; i > 0; i /= 5 ) zeros += i; cout << "ilosc zer na koncu " << n <<"! wynosi " << zeros; cin.get(); return 0; }
n!= (n-1)!*n
i tak rekurencyjnie wywolujemy silnie. Tyle ze dla duzych n mozna wyczerpac pamiec.
Wartosci dla n=0, n=1, i powiedzmy n=2 warto byloby wpisac recznie.
no spoko tylko malutki problem pojawia sie gdy n = 1000000000 albo wiecej :) wtedy prawdopodobnie obliczenia na statystycznym pc potrwaja rok i bedzie potrzebne troche duzo ramu :]
Otóż, takie zadanie miałem na Mistrzostwach Polski w programowaniu, zrobiłem to metodą, że sprawdzałem którą wielkokrotnością 5 oraz 25 jest liczba n. Te zsumowane wielokrotności sumowałem i podawałem wynik. To dobrze działało tylko do bodajże kilku tysięcy (niepamiętam). Ostatnio takie zadanko widziałem w książce od matmy przy temacie o dwumianie Newtona. Więc to może trzeba zrobić tą metodą :unsure:
Proszę o zamknięcie tego tematu, ponieważ z pomocą już znalazłem odpowiedź na ten problem. Należy wypisać ilość liczb, w których jest 5 na końcu i pomnożyć to przez 2. W wyniku otrzymujemy m:=2n div 10, czy po skróceniu otrzymujemy m:=n div 5. Chyba taka postać jest poprawna :lol:
Proszę o zamknięcie tego tematu, ponieważ z pomocą już znalazłem odpowiedź na ten problem. Należy wypisać ilość liczb, w których jest 5 na końcu i pomnożyć to przez 2. W wyniku otrzymujemy m:=2n div 10, czy po skróceniu otrzymujemy m:=n div 5. Chyba taka postać jest poprawna :lol:
no cos niebardzo to dziala:
25! = 15511210043330985984000000
25 div 5 = 5.
no ale w sumie jedno extra zero to jeszcze nie tragedia :)
looknij na moj kod powinien byc dobry :)
maly hint :) trzeba liczyc 5 ale w liczbie 25 sa juz dwie 5, twoj alogrytm tego nie uwzglednia...
no cos niebardzo to dziala:
25! = 15511210043330985984000000
25 div 5 = 5.
no ale w sumie jedno extra zero to jeszcze nie tragedia :)
looknij na moj kod powinien byc dobry :)
maly hint :) trzeba liczyc 5 ale w liczbie 25 sa juz dwie 5, twoj alogrytm tego nie uwzglednia...
przy 100! masz blad :]
w 100! liczac kolejne 5, [5,10,15,20,...] jest ich 20
w 25, 50, 75 i 100 jest jeszcze jedna gratisowa 5 wiec razem 24 zera na koncu 100!
125! na koncu ma 31 zer :)
przeanalizuj sobie moj progs, na razie nie znalazlem bledu wiec mozna zalozyc ze liczy dobrze :P
program ile_zer; uses crt; var i:integer; {to nam policzy zera} n:integer; {to nasza dana liczba} j:integer; {a to będzie nasz licznik pętli :) } begin ClrScr; WriteLn('Program liczący ilość zer na końcu silni podanej liczby'); Write('Podaj liczbę w której chcesz określić ilość zer: '); ReadLn(n); i:=0; for j:= 1 to n do begin  if j mod 5 = 0 then {tutaj sprawdzamy ile jest liczb podzielnych przez 5 od 1 do n}  i:=i+1; {jeżeli tak to zwiększamy i o jeden}  if j mod 25 = 0 then {a tu sprawdzamy czy przypadkiem ta liczba nie jest podzielna przez 25}  i:=i+1; {jeżeli tak to zwiększamy i o jeden} end; WriteLn('W silni podanej liczby występuje ', i, ' zer na końcu'); ReadKey; end.
pepsi -->> nie mogę się z tobą zgodzić jak chodzi o liczbę 125 :) występuje 30 a nie 31 zer. obliczenie jest banalne :)
100 ma 24 zera no to liczymy dalej
105, 110, 115, 120, 125, i jeszcze raz 125 bo jest podzielne przez 25. razem mamy takich liczb od 100 do 125 6 :)
setka miała 24 a 24 + 6 = 30 :)
wyżej zamieściłem program w pascalu. sprawdziłem działa :) lubię takie problemy natury kombinatorycznej :)
//edit
ale się nakombinowaliśmy. waśnie to wszystko przejżałem. przecież na to jest wzór!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!
podziel daną liczbę przez pięc następnie podziel ją przez 25 wyniki zsumuj i masz ilość zer :). no to teraz kod z poprawioną wersją :)
program ile_zer; uses crt; var i:integer; {to nam przechowa ilość zer} n:integer; {to nasza dana liczba} begin ClrScr; WriteLn('Program liczący ilość zer na końcu silni podanej liczby'); Write('Podaj liczbę w której chcesz określić ilość zer: '); ReadLn(n); i:=n div 5; i:=i + n div 25; WriteLn('W silni podanej liczby występuje ', i, ' zer na końcu'); ReadKey; end.
koniec programu :lol: a takie banalne było to rozwiązanie :)
Użytkownik j-mail edytował ten post 01 marzec 2005, 11:26
pepsi -->> nie mogę się z tobą zgodzić jak chodzi o liczbę 125 :) występuje 30 a nie 31 zer. obliczenie jest banalne :)
100 ma 24 zera no to liczymy dalej
105, 110, 115, 120, 125, i jeszcze raz 125 bo jest podzielne przez 25. razem mamy takich liczb od 100 do 125 6 :)
setka miała 24 a 24 + 6 = 30 :) zmartwie cie ;) twoj program i rozumowanie jest zle :P
co do 100! to rzeczywiscie ma 24 zera
pozniej 5 wystepuje w 105 110 115 120 czyli kolejne 4 zera
ale w 125 wystepuja trzy piatki bo 5*5*5 = 125
wiec 125! ma 24+4+3 = 31 zer :P
przemysl, popraw progs, popatrz na moj kod, moze cie natchnie :)
zmartwie cie ;) twoj program i rozumowanie jest zle :P
co do 100! to rzeczywiscie ma 24 zera
pozniej 5 wystepuje w 105 110 115 120 czyli kolejne 4 zera
ale w 125 wystepuja trzy piatki bo 5*5*5 = 125
wiec 125! ma 24+4+3 = 31 zer :P
przemysl, popraw progs, popatrz na moj kod, moze cie natchnie :)
Pepsi, zwracam honor. Już zauważyłem swój błąd.
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Podaj ile zer ma na końcu liczba n!. Liczba n może być nieskończenie duża :D
Jak narazie obiło mi się o uszy, że to jest związane ze symbolem Newtona:
n!/(k!(n-k)!
Ale nie wiem jak to mam wyliczyć.
PS. Proszę nie piszcie mi jak wygląda obliczenie n! bo to wiem :P
Słuchaj, ile zer ma na końcu, to można sprawdzić liczba mod 10 czy kończy się zerem a potem sprawdzamy dla 100, 1000 itd.
program liczzera;
var
Liczba, x, reszta : Longint;
ilezer : Byte;
begin
readln(Liczba);
ilezer := 0;
x := 10;
reszta := Liczba mod x;
while (reszta = 0) do
begin
ilezer := ilezer+1;
x := x * 10;
reszta := Liczba mod x;
end;
writeln(ilezer);
end.
Ten program liczy, ile ma zer na końcu podana przez Ciebie liczba. Możesz uzyć tego sposobu w swoim programie.
Użytkownik Balcerowicz edytował ten post 27 luty 2005, 14:42
no spoko tylko malutki problem pojawia sie gdy n = 1000000000 albo wiecej :) wtedy prawdopodobnie obliczenia na statystycznym pc potrwaja rok i bedzie potrzebne troche duzo ramu :]
napisz do czego Ci to jest potrzebne to będzie łatwiej :) z symbolem Newtona to raczej nie ma nic wspólnego :)
takie cus powinno dzialac :) teraz tylko przerobic na brzydkiego pascala :P
#include <iostream> using namespace std; int main() { size_t n; cout << "podaj n: "; cin >> n; cin.ignore(); size_t zeros = 0; for ( size_t i = n/5; i > 0; i /= 5 ) zeros += i; cout << "ilosc zer na koncu " << n <<"! wynosi " << zeros; cin.get(); return 0; }
n!= (n-1)!*n
i tak rekurencyjnie wywolujemy silnie. Tyle ze dla duzych n mozna wyczerpac pamiec.
Wartosci dla n=0, n=1, i powiedzmy n=2 warto byloby wpisac recznie.
no spoko tylko malutki problem pojawia sie gdy n = 1000000000 albo wiecej :) wtedy prawdopodobnie obliczenia na statystycznym pc potrwaja rok i bedzie potrzebne troche duzo ramu :]
Otóż, takie zadanie miałem na Mistrzostwach Polski w programowaniu, zrobiłem to metodą, że sprawdzałem którą wielkokrotnością 5 oraz 25 jest liczba n. Te zsumowane wielokrotności sumowałem i podawałem wynik. To dobrze działało tylko do bodajże kilku tysięcy (niepamiętam). Ostatnio takie zadanko widziałem w książce od matmy przy temacie o dwumianie Newtona. Więc to może trzeba zrobić tą metodą :unsure:
Proszę o zamknięcie tego tematu, ponieważ z pomocą już znalazłem odpowiedź na ten problem. Należy wypisać ilość liczb, w których jest 5 na końcu i pomnożyć to przez 2. W wyniku otrzymujemy m:=2n div 10, czy po skróceniu otrzymujemy m:=n div 5. Chyba taka postać jest poprawna :lol:
Proszę o zamknięcie tego tematu, ponieważ z pomocą już znalazłem odpowiedź na ten problem. Należy wypisać ilość liczb, w których jest 5 na końcu i pomnożyć to przez 2. W wyniku otrzymujemy m:=2n div 10, czy po skróceniu otrzymujemy m:=n div 5. Chyba taka postać jest poprawna :lol:
no cos niebardzo to dziala:
25! = 15511210043330985984000000
25 div 5 = 5.
no ale w sumie jedno extra zero to jeszcze nie tragedia :)
looknij na moj kod powinien byc dobry :)
maly hint :) trzeba liczyc 5 ale w liczbie 25 sa juz dwie 5, twoj alogrytm tego nie uwzglednia...
no cos niebardzo to dziala:
25! = 15511210043330985984000000
25 div 5 = 5.
no ale w sumie jedno extra zero to jeszcze nie tragedia :)
looknij na moj kod powinien byc dobry :)
maly hint :) trzeba liczyc 5 ale w liczbie 25 sa juz dwie 5, twoj alogrytm tego nie uwzglednia...
przy 100! masz blad :]
w 100! liczac kolejne 5, [5,10,15,20,...] jest ich 20
w 25, 50, 75 i 100 jest jeszcze jedna gratisowa 5 wiec razem 24 zera na koncu 100!
125! na koncu ma 31 zer :)
przeanalizuj sobie moj progs, na razie nie znalazlem bledu wiec mozna zalozyc ze liczy dobrze :P
program ile_zer; uses crt; var i:integer; {to nam policzy zera} n:integer; {to nasza dana liczba} j:integer; {a to będzie nasz licznik pętli :) } begin ClrScr; WriteLn('Program liczący ilość zer na końcu silni podanej liczby'); Write('Podaj liczbę w której chcesz określić ilość zer: '); ReadLn(n); i:=0; for j:= 1 to n do begin  if j mod 5 = 0 then {tutaj sprawdzamy ile jest liczb podzielnych przez 5 od 1 do n}  i:=i+1; {jeżeli tak to zwiększamy i o jeden}  if j mod 25 = 0 then {a tu sprawdzamy czy przypadkiem ta liczba nie jest podzielna przez 25}  i:=i+1; {jeżeli tak to zwiększamy i o jeden} end; WriteLn('W silni podanej liczby występuje ', i, ' zer na końcu'); ReadKey; end.
pepsi -->> nie mogę się z tobą zgodzić jak chodzi o liczbę 125 :) występuje 30 a nie 31 zer. obliczenie jest banalne :)
100 ma 24 zera no to liczymy dalej
105, 110, 115, 120, 125, i jeszcze raz 125 bo jest podzielne przez 25. razem mamy takich liczb od 100 do 125 6 :)
setka miała 24 a 24 + 6 = 30 :)
wyżej zamieściłem program w pascalu. sprawdziłem działa :) lubię takie problemy natury kombinatorycznej :)
//edit
ale się nakombinowaliśmy. waśnie to wszystko przejżałem. przecież na to jest wzór!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!
podziel daną liczbę przez pięc następnie podziel ją przez 25 wyniki zsumuj i masz ilość zer :). no to teraz kod z poprawioną wersją :)
program ile_zer; uses crt; var i:integer; {to nam przechowa ilość zer} n:integer; {to nasza dana liczba} begin ClrScr; WriteLn('Program liczący ilość zer na końcu silni podanej liczby'); Write('Podaj liczbę w której chcesz określić ilość zer: '); ReadLn(n); i:=n div 5; i:=i + n div 25; WriteLn('W silni podanej liczby występuje ', i, ' zer na końcu'); ReadKey; end.
koniec programu :lol: a takie banalne było to rozwiązanie :)
Użytkownik j-mail edytował ten post 01 marzec 2005, 11:26
pepsi -->> nie mogę się z tobą zgodzić jak chodzi o liczbę 125 :) występuje 30 a nie 31 zer. obliczenie jest banalne :)
100 ma 24 zera no to liczymy dalej
105, 110, 115, 120, 125, i jeszcze raz 125 bo jest podzielne przez 25. razem mamy takich liczb od 100 do 125 6 :)
setka miała 24 a 24 + 6 = 30 :) zmartwie cie ;) twoj program i rozumowanie jest zle :P
co do 100! to rzeczywiscie ma 24 zera
pozniej 5 wystepuje w 105 110 115 120 czyli kolejne 4 zera
ale w 125 wystepuja trzy piatki bo 5*5*5 = 125
wiec 125! ma 24+4+3 = 31 zer :P
przemysl, popraw progs, popatrz na moj kod, moze cie natchnie :)
zmartwie cie ;) twoj program i rozumowanie jest zle :P
co do 100! to rzeczywiscie ma 24 zera
pozniej 5 wystepuje w 105 110 115 120 czyli kolejne 4 zera
ale w 125 wystepuja trzy piatki bo 5*5*5 = 125
wiec 125! ma 24+4+3 = 31 zer :P
przemysl, popraw progs, popatrz na moj kod, moze cie natchnie :)
Pepsi, zwracam honor. Już zauważyłem swój błąd.