Pseudo Code Coin Changing

Pseudocode Coin Changing Problem

Mata Kuliah : [ CF-1333 Alpro 2 ]

Disusun oleh : Khairu Rahman

5207 100 030

Jurusan Sistem Informasi Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya

Greedy Algorithm

Greedy Algorithm is the most popular method to solve optimation

problem.

Greedy principle is : “take what you can get now!”. The example of this problem in our life are : 

Choose some of investment type



Finding the shortest way from Bandung to Surabaya



Choose a direction in University



Playing card

Greedy algorithm form a solution step by step. to explain the way of greedy algorithm, next i will explain one of the problem that can be solved by greedy algorithm, there is Coin Changing Problem .

Example : I have money 500. I want to exchange with available coin. There are 50 as much as 5, 25 as much as 10, and 10 as much as 15. How much coin is needed to this exchange? The answer of this problem have two combination. There are

maximal

combination and minimum combination.

Solution : To understand the problem, make a table which contain some available coin with their amount. For the minimum combination the kind of available coin must be sort (descending). Here is the table :

Index

Coin

Denom

amount

0

50

5

Looked for

1

25

10

Looked for

2

10

15

Looked for

For the maximum combination the kind of available coin must be sort (ascending). Here is the table :

Index

Coin

Denom

amount

0

10

15

Looked for

1

25

10

Looked for

2

50

5

Looked for

This time I will explain the solution to find minimum combination. The way to find maximal combination is same. The different is in the procces of sorting coin. To find minimum combination, the first step , we take the first kind of coin (50). If after this taking the value still less than or not equals with the value of money then we must take again the coin. If the first kind of coin (50) was taken all and the sum still less than or not equals with the value of money then we take again the coin in the next kind (25). This process will looping until the sum of coin combination is equals with the money that we want to exchange. In this process we must pay attention for some case. When we taking the first kind of coin and weren’t taking all, so we have to take again the kind of this coin. If after this taking the sum is more than the value of our money, then this taking must be canceled and we take the next kind of coin. The next process is same with the previous explanation. The process is looping until the sum of coin combination equals with the money that we want to exchange.

Pseudocode Coin Changing Problem From the previous explanation of the solution coin changing problem, I can make the pseudocode. The input is the value of money that we want to exchange (n), amount kind of available coin (counter) and amount of each kind of available coin. Data about the amount of each kind of available coin must be placed into array. And must be sorting by ascending or descending, according to our needed (want to find maximal combianation or minimum combination). In my pseudocode, I prepare 3 arrays, there are coin array is used for saving the kind of available coin, denom array is used for save amount of each kind of coin, and the last array is amount array is used for saving amount of each coin that used for maximal combination or minimum combination. In this pseudocode I make 3 method . There are 2 variable as global variable. There are n variable , sum variable (used for saving the sum of coin combination that be arrangged).

Global variable n, sum

COUNT-COIN (counter, coin[] , denom[]) 1. i  0 2. sum  0 3. while i
amount[i] = PROSES(coin[i] , denom [i])

5.

i++

6.

if sum = n

7.

i = ∞

8. PRINT-COIN (counter, coin [], amount[])

PROCCESS (coin , denom) 1. counter  1 2. amount  0 3. while counter <= denom and (sum+coin) <= n 4.

sum = sum + coin

5.

amount = counter

6.

counter++

7. return amount

PRINT-COIN (counter, coin [], amount[]) 1. for i  0 to counter 2.

print coin[i] “=” amount[i]

Method COUNT-COIN. This method have 3 parameters. It is counter variable that used for saving amount kind of available coin, it was getting from user. Then coin array contain the kinds of available coin, it was getting from user. The last parameter is denom array that used for saving amount of each kind of available coin, it was getting from user. Variable i is used for saving index value. Starting from 0. variable sum is used for saving sum from coin combination that be arranged. Variable sum starting from 0. next in line 2 to 7 progrma will enter looping process. This looping process is used to fill amount array. The filling process in each amount array element were did in PROCESS METHOD, so that in line-4 I call PROCESS METHOD and sending argument coin[i] and denom[i]. Finally this method will call PRINT-COIN METHOD for print the result. In line 7 i value is unlimited if the value of sum equals n. If the value of sum equals n it means the purpose of this process completed and looping process must be stopped. I change the value of i become unlimited so that unfulfill looping condition in line-3. and looping was over.

PROCESS METHOD. This method have 2 parameters, there are coin and denom variable. This two variable is different with coin and denom variable in COUNT-COIN method. In that method coin and denom variable is array. In this method I make variable counter, with starting value 1. counter variable is different with counter variable in COUNT-COIN method. When counter = 1 it means we take one from this kind of coin checking, when counter=2 it means we take 2 coin, and further. Amount variable is used for saving amount of coin that starting value 0, amount variable in this method is different with the variable in COUNT-COIN Method. In line 3-6 program wil enter looping process. This looping process is used to find the amount that use and count some of coin combination that be arranged. The condition of this looping process is during counter value <= denom its means during the kind of coin was cheked is still available and the value from sum+coin still<=n, it means if the sum from combination that be arranged is not over n. If looping process is finished so this method will return the value from amount to COUNT-COIN Method. Method PRINT-COIN. This method is used to print the result of all process (output) . That is print amount from each of coin that will used.