Witam. Mam za zadanie napisać program, wyliczający ostatnią niezerową cyfrę n!. Chciałbym aby mi ktoś wytłumaczył na czym polega ten sposób, w którym dzielimy, stosujemy modulo, ucinamy pewne liczby itp. bo kompletnie nie wiem o co chodzi i jak dojść do tego żeby obliczyć ostatnią niezerową cyfrę np. 10000! Mam nadzieję, że ktoś to rozumie i mi pomoże ;)
0
1
Oj nie wróżę ci przyszłości na WDI :P
Na ostatnią niezerową cyfrę silni z n ma wpływ tylko ostatnia niezerowa cyfra liczby n-1, mam nadzieję ze rozumiesz czemu? Ergo nie potrzebujesz liczyć 10000! żeby znać ostatnią niezerową cyfrę bo wystarczy że będziesz za każdym kolejnym mnożeniem brał pod uwagę tylko ostatnią niezerową cyfrę.
Zera z końca możesz ucinać bo 0*x zawsze da nam 0. A cyfry z początku liczby możesz odrzucić bo nie będą miały wpływu na ostatnią.
0
Ok, chyba rozumiem, zobaczymy co z tego wyjdzie ;) No WDI to bajka :D
3
@Shalom - nieprawda, nieprawda! Na swoim WDI zrobiłem dokładnie ten sam błąd, więc wiem :P
Owszem, dla
6! = 720
7! = 5040
2 * 7 = 14
Ale już dla
14! = 87178291200
15! = 1307674368000
2 * 15 = 30
Nie ma tak łatwo...
Na pocieszenie dodam że problem występuje tylko kiedy mnożymy 2 z 5 (z czego w n! na końcu może być tylko 2, więc 5 musi być w n) - da się to efektywnie rozwiązywać, ale nie mam pod ręką kodu a niezbyt mogę teraz więcej pisać.
PS. mniej ambitne ale szybkie rozwiązanie to po prostu trzymanie więcej znaczących cyfr (np. 4 ostatnich zamiast ostatniej) żeby zwiększyć liczbę dla której pierwszy raz występuje błąd.
1
Wg algorytmu od @msm bez własnej arytmetyki się nie obejdzie:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned N;
while(cin>>N)
{
unsigned L2=0,L5=0;
for(unsigned n=2;n<=N;++n)
{
unsigned v=n;
for(;!(v&1);++L2) v>>=1;
for(;!(v%5);++L5) v/=5;
}
cout<<N<<"! ma "<<min(L2,L5)<<" zer na koncu."<<endl;
}
return 0;
}
http://ideone.com/mpdvi7
Na wbudowanych typach danych nie obliczysz ostatnią niezerową cyfrę nawet dla n<=100 (tym algorytmem mam na myśli).
Może coś takiego:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned long long N;
while(cin>>N)
{
unsigned long long x=1;
for(unsigned long long n=2;n<=N;++n)
{
x*=n;
while(!(x%10)) x/=10;
x%=10;
}
cout<<N<<" ostatnia cyfra "<<x<<endl;
}
return 0;
}
Ale coś mi się nie zgadza np dla 15: http://ideone.com/H6ZaHX
Problem z 15-ką rozwiązuje taki kod:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned long long N;
while(cin>>N)
{
unsigned long long x=1;
for(unsigned long long n=2;n<=N;++n)
{
x*=n;
while(!(x%10)) x/=10;
x%=100;
}
cout<<N<<" ostatnia cyfra "<<x%10<<endl;
}
return 0;
}
Ale nie wiadomo czy nie wystąpi jakiś podobny bug na większych liczbach.
Zastosowanie zamiast 100 liczby 1000000000000000000 też nie wchodzi w rachubę bo będą przepełnienia.
Przy ograniczeniu n do 9000000000 można zapodać:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned long long N;
while(cin>>N)
{
unsigned long long x=1;
for(unsigned long long n=2;n<=N;++n)
{
x*=n;
while(!(x%10)) x/=10;
x%=1000000000LL;
}
cout<<N<<" ostatnia cyfra "<<x%10<<endl;
}
return 0;
}
Ciekawostką jest fakt że oprócz 1! ostatnia niezerowa cyfra to jedna z:
2 4 6 8
Tak sobie zastanawiam czy nie ma w ich kolejności jakieś reguły:
2 ostatnia cyfra 2
3 ostatnia cyfra 6
4 ostatnia cyfra 4
5 ostatnia cyfra 2
6 ostatnia cyfra 2
7 ostatnia cyfra 4
8 ostatnia cyfra 2
9 ostatnia cyfra 8
10 ostatnia cyfra 8
11 ostatnia cyfra 8
12 ostatnia cyfra 6
13 ostatnia cyfra 8
14 ostatnia cyfra 2
15 ostatnia cyfra 8
16 ostatnia cyfra 8
17 ostatnia cyfra 6
18 ostatnia cyfra 8
19 ostatnia cyfra 2
20 ostatnia cyfra 4
21 ostatnia cyfra 4
22 ostatnia cyfra 8
23 ostatnia cyfra 4
24 ostatnia cyfra 6
25 ostatnia cyfra 4
26 ostatnia cyfra 4
27 ostatnia cyfra 8
28 ostatnia cyfra 4
29 ostatnia cyfra 6
30 ostatnia cyfra 8
31 ostatnia cyfra 8
32 ostatnia cyfra 6
33 ostatnia cyfra 8
34 ostatnia cyfra 2
35 ostatnia cyfra 2
36 ostatnia cyfra 2
37 ostatnia cyfra 4
38 ostatnia cyfra 2
39 ostatnia cyfra 8
40 ostatnia cyfra 2
41 ostatnia cyfra 2
42 ostatnia cyfra 4
43 ostatnia cyfra 2
44 ostatnia cyfra 8
45 ostatnia cyfra 6
46 ostatnia cyfra 6
47 ostatnia cyfra 2
48 ostatnia cyfra 6
49 ostatnia cyfra 4
50 ostatnia cyfra 2
51 ostatnia cyfra 2
52 ostatnia cyfra 4
53 ostatnia cyfra 2
54 ostatnia cyfra 8
55 ostatnia cyfra 4
56 ostatnia cyfra 4
57 ostatnia cyfra 8
58 ostatnia cyfra 4
59 ostatnia cyfra 6
60 ostatnia cyfra 6
61 ostatnia cyfra 6
62 ostatnia cyfra 2
63 ostatnia cyfra 6
64 ostatnia cyfra 4
65 ostatnia cyfra 6
66 ostatnia cyfra 6
67 ostatnia cyfra 2
68 ostatnia cyfra 6
69 ostatnia cyfra 4
70 ostatnia cyfra 8
71 ostatnia cyfra 8
72 ostatnia cyfra 6
73 ostatnia cyfra 8
74 ostatnia cyfra 2
75 ostatnia cyfra 4
76 ostatnia cyfra 4
77 ostatnia cyfra 8
78 ostatnia cyfra 4
79 ostatnia cyfra 6
80 ostatnia cyfra 8
81 ostatnia cyfra 8
82 ostatnia cyfra 6
83 ostatnia cyfra 8
84 ostatnia cyfra 2
85 ostatnia cyfra 2
86 ostatnia cyfra 2
87 ostatnia cyfra 4
88 ostatnia cyfra 2
89 ostatnia cyfra 8
90 ostatnia cyfra 2
91 ostatnia cyfra 2
92 ostatnia cyfra 4
93 ostatnia cyfra 2
94 ostatnia cyfra 8
95 ostatnia cyfra 6
96 ostatnia cyfra 6
97 ostatnia cyfra 2
98 ostatnia cyfra 6
99 ostatnia cyfra 4
1
Da się bez własnej arytmetyki:
http://cat.wordpandit.com/finding-last-non-zero-digit-of-any-factorial/