ada soal OSN yang terus2an aku pikirkan(begh…)…
uda lama juga aku mikir, gimana solusi untuk memecahkan masalah itu…(maklum lah, pengetahuan tentang yang gituan agak kurang…)

ini dia soalnya, dari OSN601

Diberikan sebuah bilangan N, N! disebut N faktorial dan nilainya dihitung dengan rumus :
N x (N – 1) x (N – 2) … x 1.
Tugas Anda adalah menghitung berapa jumlah angka nol berturutan yang mengakhiri N!.
Sebagai contoh:
N=10: 10! = 3 628 800, maka jumlah angka nol adalah 2.
N=8: 8! = 40 320, jumlah angka nol adalah 1 (nol di tengah tidak dihitung).

FORMAT MASUKAN
Masukan hanya terdiri dari satu baris berisi bilangan bulat N (1 ≤ N ≤ 10 000).
FORMAT KELUARAN
Tuliskan satu bilangan bulat yang menyatakan jumlah angka nol yang mengakhiri N!.

CONTOH MASUKAN 1
10
CONTOH KELUARAN 1
2

CONTOH MASUKAN 2
8
CONTOH KELUARAN 2
1

pada suatu hari, gak sengaja aku lihat sepertinya ada sebuah pattern pada faktorial,,
waktu itu aku lagi baca2 ebook tentang java(lagi belajar java neehhh..)..

judulnya “Beginning Java 2.JDK5.Edition-2004″ oleh ivor horton…
pada halaman 122, ada di tuliskan tentang keluaran dari prosedur faktorial yang dibuat..

1! is 1
2! is 2
3! is 6
4! is 24
5! is 120
6! is 720
7! is 5040
8! is 40320
9! is 362880
10! is 3628800
11! is 39916800
12! is 479001600
13! is 6227020800
14! is 87178291200
15! is 1307674368000
16! is 20922789888000
17! is 355687428096000
18! is 6402373705728000
19! is 121645100408832000
20! is 2432902008176640000

aku lihat, adanya penambahan angka 0 setiap kelipatan 5..
aku da mulai ngerasa, apakah ini triknya???

akhirnya penasaran aku hilang juga (walaupun bukan hasil kerja sendiri)….
ada sebuah penyelesaian dari toki tentang masalah itu (aku lupa judul file nya..), dan di pembahasan itu, menggunakan angka 5 sebagai penyelesaiannya…(ternyata dugaan ku tentang kelipatan 5 itu bener..hehe)…

ini di code dari toki.

i := 5;
count := 0;
while i <= N do
begin
// menghitung berapa banyak kemunculan faktor 5 dalam
i
j := i;
while (j mod 5) = 0 do begin
j := j div 5;
count := count + 1;
end;
i := i + 5;
end;

namun kode itu kurang memuaskan…
lho…
kenapa??
aku juga sempat berkata2 demikian, kepikiran solusi itu adalah paling bagus…
namun,,
ada sebuah permasalahan lagi dengan code di atas,,,

Perhatikan bahwa:
• bilangan­bilangan berfaktor 5 adalah semua bilangan kelipatan 5. Jika J1 adalah
jumlah bilangan kelipatan 5 yang = N tersebut maka J1 = N div 5.
• di antara bilangan­bilangan itu terdapat bilangan­bilangan kelipatan 25, yaitu
yang menyumbang faktor 5 sebanyak dua kali. Jika J2 adalah banyaknya
kemunculan bilangan kelipatan 25 yang = N, maka J2 = N div 25.
• di antara bilangan­bilangan itu terdapat bilangan­bilangan kelipatan 125, yaitu
yang menyumbang faktor 5 tiga kali. Jika J3 adalah banyaknya kemunculan
bilangan kelipatan 125 yang = N maka J3 = N div 125.
• … dst.

Maka, jumlah faktor 5 pada N! = J1 + J2 + J3 + … = (N div 5) + (N div 25) + (N div 125)
+ … berdasarkan analisis ini anda cukup membuat iterasi untuk menghitung dan
mentotalkan (N div i) dengan i deret 5, 25, 125, … selama i = N. Algoritma yang
diperoleh hanya berisi 8 baris saja sebagai berikut. Untuk N = 1012
, iterasi hanya
dilakukan kurang dari 18 kali (log5(1012
) < 18). Jadi program yang efisien untuk
menjawab masalah di atas adalah program yang sangat pendek sebagai berikut.

readln(N);
i := 5;
count := 0;
while i <= N do begin
count := count + (N div i);
i := i * 5;
end;
writeln(count);

gitu rupanya….

ku jadi semangat2 nya nih belajar algoritma…
hehe…