Rekursi

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 :

To be added : problems, solution, detailed explanation

Advertisements

4 Responses to Rekursi

  1. Derrick says:

    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?

    • Angelina Veni says:

      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.

  2. Febry says:

    Kak, soal OSN yang paduan suara itu gimana ya algo rekursinya? Thx before..

    • Angelina Veni says:

      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…

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: