Factorial:
Recursion Properties z
z
base case, problem paling sederhana yang memproses input tanpa perlu recursive lagi. recursive case: 1. membagi problem menjadi bagian yang lebih kecil. 2. memanggil fungsi secara recursive untuk setiap bagian 3. menggabungkan solusi tiap bagian ke menjadi solusi dari problem utama.
04-Mar-04
IKI10100 - PM
MaxSubseqSum
1
Recursive version
Case 1: Max sum dihasilkan oleh elemen di paruh pertama Case 2: Max sum dihasilkan oleh elemen di paruh kedua Case 3: Max sum dihasilkan oleh elemen awal di paruh pertama dan berakhir di paruh kedua Case 1
IKI10100 - PM
2
MaxSubseqSum
Recursive version public int maxSubSum (int[ ] a) { return maxSumRec(a, 0, a.length-1); } private int maxSumRec(int[ ] a, int left, int right) { int center = (left+right)/2;
3
cari index tengah
base case
int maxLeftSum = maxSumRec(a, left, center);
Pilih dari ketiganya yang menghasilkan nilai terbesar. IKI10100 - PM
04-Mar-04
if(left == right) return a[left] > 0 ? a[left] : 0;
Case 2
Case 3
04-Mar-04
static public int factorial( int n) { // return n! if( n <= 1) // base case return 1; else return n * factorial(n-1); }
cari max di paruh kiri
int maxRightSum = maxSumRec(a, center+1, right); …. cari max 04-Mar-04
IKI10100 - PM
di paruh kanan 4
1
MaxSubseqSum
Recursive Version for(int i=center; i>=left; i--) { leftBorderSum += a[i]; if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } for(int j=center+1; j<=right; j++) { rightBorderSum += a[j]; if(rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; }
}
Recursive Version
cari max jumlah dari tengah ke kiri cari max jumlah dari tengah ke kanan
First Half
Second Half
4
-3
5
-2
-1
2
6
-2
4
0
3
-2
-1
1
7
5
maxSeqSum
pilih max dari ketiga kemungkinan
return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBoderSum); 04-Mar-04
IKI10100 - PM
5
04-Mar-04
IKI10100 - PM
6
Recursive Call
Running Time
Binary Search N N
low
mid
high
int binsearch(data[ ], n, low, high) {
N
mid = data.length() / 2; if( data[mid] == n ) return mid;
N 04-Mar-04
O (N log N)
IKI10100 - PM
else if ( n < data[mid] ) return binsearch(data[ ], n, low, mid ); else return binsearch( data[ ], n, mid+1, high); } 7
04-Mar-04
IKI10100 - PM
8
2
Running Time of BinarySearch
Tower of Hanoi (Lucas, 1883) Pindahkan tumpukan disc dari source ke dest dengan bantuan auxiliary z Tumpukan disc harus mengecil ke atas. z
04-Mar-04
source
O (log N)
IKI10100 - PM
9
auxiliary
04-Mar-04
destination IKI10100 - PM
10
Tower of Hanoi
Recursive Solution (N discs)
Change-making Problem:
1. Move the top N-1 disks from Src to Aux (using Dst as an intermediary peg)
z Dengan
2. Move the bottom disks from Src to Dst 3. Move N-1 disks from Aux to Dst (using Src as an intermediary peg) Solve(N, Src, Aux, Dst) if N is 0 exit Solve(N-1, Src, Dst, Aux) Move from Src to Dst Solve(N-1, Aux, Src, Dst) 04-Mar-04
IKI10100 - PM
11
coin yang tersedia C1, C2, .., CN (cents) tentukan jumlah minimum coin yang diperlukan untuk “kembalian” sejumlah K cents.
04-Mar-04
IKI10100 - PM
12
3
Inefficient makeChange
Greedy Algorithm z Dengan
divide-and-conquer, hasilkan penyelesaian terbaik untuk setiap sub-problem tanpa memperhitungkan hasil akhir.
int makeChange (int[] coins, int change, int differentCoins) { int minCoins = change; max # of coins for (int i=0; i
ada coin yg = change
for (int j=1; j<=change/2; j++) { int thisCoins = makeChange(coins, j, differentCoins) + makeChange(coins, change-j, differentCoins); if(thisCoins < minCoins) minCoins = thisCoins } return minCoins;
z Dengan
coin: 1, 5, 10, 21 dan 25 cent, kembalian 63 cent: 25, 25, 10, 1, 1, 1. }
04-Mar-04
IKI10100 - PM
13
Brute-Force Recursive Version Coin = 1, 5, 7 1+minCoin(9)
5+minCoin(5)
14
Dynamic Programming perhitungan disimpan dalam cache untuk kemudian dipakai lagi untuk permasalah yang sama.
5+minCoin(4) 7+minCoin(2) 1+minCoin(4)
minCoin(10)
IKI10100 - PM
z Hasil
1+minCoin(8)
Change = 10
04-Mar-04
5+minCoin(0) X 1+minCoin(2)
7+minCoin(3)
X X
04-Mar-04
IKI10100 - PM
15
04-Mar-04
IKI10100 - PM
16
4
Dynamic Programming
Pelajari algoritma ini dan ubah ke bentuk recursive!
Result Caching coinUsed[0]=0; lastCoin[0]=1;
z Menyimpan
hasil penyelesaian optimal setiap tahap ke dalam bentuk array/tabel. Kembalian 1 2 . 5 6 . 10 11 23 63
04-Mar-04
Jml Coin 1 2 . 1 2 . 1 2 3 3 IKI10100 - PM
for loop Version
17
for(int cents = 1; cents <= change; cents++) { int minCoins = cents; int newCoin = 1; j = index coin for(int j = 0; j < diffCoins; j++) { if(coins[ j ] > cents) continue; // can’t use coin j if(coinUsed[ cents - coins[ j ] ] + 1 < minCoins) { minCoins = coinUsed[ cents-coins[ j ] ] + 1; newCoin = coins[ j ]; } } coinUsed[ cents ]=minCoins; lastCoin[ cents ]=newCoin; } 04-Mar-04
IKI10100 - PM
Result Caching
Reporting Coin List z
for (int i = change; i > 0; ) { System.out.print( lastCoin[ i ] + “ “); i -= lastCoin[ i ]; } System.out.println( );
Menyimpan hasil penyelesaian optimal setiap tahap ke dalam bentuk array/tabel. Kembalian 0 1 . 5 … 12 25 … 37 38
Jml Coin 0 1 . 1 . 1 1 . 2 3
Kembalian 0 1 … 5 … 12 25 … 37 38
coinUsed[ ] 04-Mar-04
IKI10100 - PM
19
18
04-Mar-04
Last Coin 0 1 . 5 . 12 25 . 12 1
lastCoin[ ] IKI10100 - PM
Change(38) 20
5
