Outlaws35

Soal Faktorial

Posted on: October 11, 2008

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…

About these ads

6 Responses to "Soal Faktorial"

halo adikku yang ganteng..
Keren deh…ilmu dishare di blog….

kpn kita nyanyi bareng lagi?

halo kakak ku yang cantik..

kalo kakak liburan ke medan, kita nyanyi bareng lagi..

gimana kerjanya??
gaji pertamanya, agak2 di share ya..
hehe..

klo aku jadi programmernya, aku konversi aja bilanganya ke string, trus aku sediakan fungsi untuk mencari angka 0 dari belakang sampai ketemu bukan angka 0. nah selama proses pencarian, maenkanlah counter++, jika ketemu bukan angka 0, langsung break aja loopnya. gampang kan??? hahahaha….

sekali lagi, programming adalah masalah seni, jadi jadikan seni itu indah, bukan yang ruwet-ruwet. wkwkwkwkwkwkw…. *nasehat ini jangan diterima dengan akal sehat, terimalah dengan akal bulus*

Gyahahahahahahahahahaha……….

pening poen aQ….

dimana2 bLajar…

:)

mantaph….mantaph..to ku…
tapi ajarin aq ya, maklumlah ito mu yang satu ini rada2 lemot, klo berhubungan dengan yang kayak gituan…ito awak yang master…;)

Wuah,, merasa terbantu sih,, tapi Q mash gak ngerti hehehe!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

my twitter

kalender

October 2008
M T W T F S S
« Sep   Nov »
 12345
6789101112
13141516171819
20212223242526
2728293031  

blog stats

  • 15,803 hits

counter

page rank


PageRank

me and sponsors


Visit ITapanuli
Visit Politeknik Informatika Del on OSUM
Jogi Silalahi
Jogi Silalahi
Create Your Badge

Sun Microsystems

Digital Open

OpenSolaris


Linux


Fedora Project


Open Solaris Org


OpenSolaris User Group


OSUM Member


OSOL Indonesia


Sun Student Developer Indonesia


ITapanuli, Learning Community


Open Solaris User Group Medan

referal link





Masukkan Code ini K1-5D2B4B-3
untuk berbelanja di KutuKutuBuku.com






top click

  • None

award dari mekkelbojak.blogdetik.com

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: