For each of the problems below you are to consider making a function to solve th

Question

For each of the problems below you are to consider making a function to solve the problem. As before, state the purpose of the function in your own words. Next specify input that is needed for the function to complete the task, and state what input should be passed to the function as parameters and what would be acquired inside the function using the input function. Specify the expected output and state if the output will be returned to the function call or be sent to the monitor. Finally give the step by step process that will obtain the output from the input (the algorithm). In addition to these 4 items also specify test data that can be used for each function. Remember to describe your steps in enough detail so someone other than you could follow your algorithm and solve the problem. Also do not write any actual code.

Explanation / Answer

Purpose: Minimize the total
number of coins(each of the four categories(nickels,dimes,quarters,pennies)) needed as a change for some value in the form of nickles dime pennies and quarters

Input: an integer ranging from 0 to 99

Expected output: four values that are to be returend to the function calling,
1. number of pennies needed
2. number of nickels needed
3. number of dimes needed
4. number of quarters needed

Algorithm: The problem can be solved by using Dynamic Programming Approach. In this at each step we try to calculate the minimum number of coins needed for a given change using a particular denomination(1,5,10,25). If a particular coin is used, we check for the minimum coins needed for the remaining amount of money. If we have already calculated the remaining amount, it is possible for us to use that value and add this to the total amount till now making it easy for us to calculate optimally what is the minimum amount of coins needed.

The algorithm goes like this:
if N is the total amount to be calculated :
we can check in the following way:

Number of coins needed for N = 1 + minimum{
   coins needed for(N-1),
   coins needed for(N-5),
   coins needed for(N-10),
   coins needed for(N-25)
}

Algo pseudo code:
Input: integer N(for which change is required)
Output: Array containing amount of penny,nickels,dimes and quarters needed.

Integer Array a:={1,5,10,25}
integer array answer[N+1][4]:={infinity} //all zeros containing number of coins required for a given value.
integer x:

integer totalcoins[N+1] //

for i 1 to N //calculating for all the subproblems upto N in bottomup manner
   for k from 1 to 4 // since we have 4 denominations : 1 5 10 25
       if(totalcoins[i]>totalcoins[N-a[i] and i-a[k]>=0) //checking for the conditions
           for l from 1 to 4 //calculating for each denominations
               answer[i][l]=answer[N-i][l] //copying the amount needed for N-i
           answer[i][k]=answer[i][k]+1 // adding 1 to amount needed for N-i

return answer[N]//returning a 4 value tuple

for example:

Suppose we want a sum 11:

Table: 1 5 10 25 Sum

i=0: 0 0 0 0    0        // for zero, 0 coins needed
i=1: 1 0 0 0    1       // for 1 , 1 coin of 1
i=2: 2 0 0 0    2       // 2 coins of 1
i=3: 3 0 0 0    3       // 3 coins of 1
i=4: 4 0 0 0    4       // 4 coins of 1
i=5: 0 1 0 0    1       // I=5, sum (N-5) = 0 < sum(N-1) = 4, hence choose coin 5 rather than 1, thus Table[5]=Table[0],Table[5][2]+=1. Here table[5][1] means , Number of 1s needed, table[5][2] number of 5s needed   
i=6: 1 1 0 0   2        //1 coin of 5 and 1 coin of 1 as 6-1=5, sum[5]=1; 6-5=1, sum[1]=1
i=7: 2 1 0 0   3       //1 coin of 5 and 2 coin of 1 as 7-1=6, sum[6]=2; 7-5=2, sum[2]=2
i=8: 3 1 0 0   4       //4 coins
i=9: 4 1 0 0   5 //5 coins
i=10: 0 0 1 0   1        //1 coins as Sum[n-5] < Sum[n-1], hence take N-5, but N-10 < N-5, so finally take N-10
i=11: 1 0 1 0   2        //2 coins needed

Sum[11] are the number of coins needed and Table[11] is the 4 value tuple representing number of pennies, nickles, dimes and quartes needed

Table 1 5 10 25 Total Coins 0 0 0 0 0 0 1 1 0 0 0 1 2 2 0 0 0 2 3 3 0 0 0 3 4 4 0 0 0 4 5 0 1 0 0 1 6 1 1 0 0 2 7 2 1 0 0 3 8 3 1 0 0 4 9 4 1 0 0 5 10 0 0 1 0 1 11 1 0 1 0 2

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.