Angelina Veni
prosedur/function yang memanggil dirinya sendiri – paling jelas terlihat bila dibuat dalam notasi matematika. Contohnya, faktorial :
if n = 1, faktorial(n) = 1
if n > 1, faktorial(n) = n*faktorial(n-1)
sehingga programnya akan menjadi seperti ini [*.pas].
note:ini materi yang sangat penting (dan untuk mengerti benar agak lama), jadi make sure kalian benar-benar mengerti alur rekursinya..
Harus dikuasai:
- Permutasi – given n, generate semua permutasi angka2 dari 1 – n. Solusi[.pas]
- Kombinasi - given n dan k, generate semua kombinasi k angka dari 1-n. Solusi[.pas]
- perhatikan penggunaan variabel khusus dalam procedure/function dalam contoh2 di atas. bila var i : integer; ditaruh di global, program akan menjadi salah.
Latihan :
- UVA 10696 : F91
- UVA 291 : House of Santa Claus
- SPOJ : ONP
- OSN 2008 Sesi 3 : Memasang Lantai
- OSN 2009 Sesi 3 : Paduan Suara
- OSN 2007 Sesi 3 : Permutasi Ekspresi
To be added : problems, solution, detailed explanation
Tweet12 Responses to Rekursi
Leave a Reply to eko bp Cancel reply
On the Web
Recent Comments
- Peter on US College Application Essay
- Peter on US College Application Essay
- angelinavj on US College Application Essay
- Peter on US College Application Essay
- didut on Bahasa Indonesia dan Lokalisasi
- widya on Programming
- Vederis Leunardus on Array
- nissa on US College Application Essay
- Rhemed on Rekursi
- Anonymous on Programming
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License (you're required to link to this blog whenever you republish my content).
Kak,kalau ada soal seperti A^B yang besar sekali dan jika hasilnya lebih besar dari 999999 maka hanya memasukkan 6 angka terakhir itu divide and conquernya itu gimana ya kak?
divide and conquer itu sendiri seperti apa kak?
Divide and Conquer intinya:
1) membagi masalah yang besar menjadi masalah yang kecil
2) selesaikan / buat solusi masalah yang kecil
3) gabungkan solusi2 kecil menjadi solusi global
untuk A^B mod 1000000, kira2 rumus rekursif / divide and conquernya :
f(pangkat) ->
- bila pangkat adalah 1, A. => base case
- bila pangkat adalah genap, f(pangkat/2) * f(pangkat/2)
- bila pangkat adalah ganjil, f(pangkat/2) * f(pangkat/2) * f(1)
mod sejutanya tinggal diselip2in aja.
Kak, soal OSN yang paduan suara itu gimana ya algo rekursinya? Thx before..
itu kalo ga salah kan nentuin ‘kelompok’ mana yang dapet x, yang mana yang dapet x+1. di mana x = total div jumlah kelompok. nah pembagiannya ini ditentuin pake permutasi…
Mbak, fungsinya “fillchar(used,sizeof(used),false)” itu apa ya??
Mohon bantuannya….
used itu array yang tipenya boolean mungkin ya ?
fillchar(used,sizeof(used),false), kalo bahasa indonesianya mungkin gini kali ya : mengisi seluruh array used, dengan “false”.
kenapa seluruh array used? karena sizeof(used)
*cmiiw
soalnya masih belajar juga
kak tolong bantuannya ya
tolong dong soal-soal olimpiade TIK OSK dan OSP dan Pembahasannya, terima kasih terlebih dulu atas kemurahan hatinya mengirimkan saol dan pembahasan
kak tlng bantuannya unt soal:
function a(n:integer):integer;
begin
if(n=0)then
a:=0:
else
a:=1-n*a(n-1);
end;
berapa hasil dari a(5)
input(n);
j:=n-1;
for i:=j downto 2 do
begin
n:=i mod n;
end;
writeln(n);
berapa outputnya jika di inputkan n=97
mksh atas bantuannya
begin
if(n=0)then
a:=0:
else
a:=1-n*a(n-1);
end;
berapa hasil dari a(5)
hasilnya:a=500
dan untuk soal kedua
input(n);
j:=n-1;
for i:=j downto 2 do
begin
n:=i mod n;
end;
writeln(n);
berapa outputnya jika di inputkan n=97
hasilnya:n=2
kalo gk salah hehe sama masih pemula
sob, bleh minta tolong,
masalahnya bilangan pangkat besar kenapa overflow ya?
gimana source kodingnya.
misal 77 pangkat 53 mod 239 =….?
minta tolong source koding.a ya sob…