C Bank withdrawal algorithm using recursion
I am having doubts about a bank withdrawal algorithm in C. First of all it is better to pass the statement:
ATMs in banks are a great invention, but sometimes we need money exchanged and the machine delivers notes of R$100,00. Other times, we want to withdraw a slightly higher amount and for security reasons I would like to receive everything in notes of R 1 100,00, but the machine delivers a lot of notes of R 2 20,00. The Smart Bank it is trying to minimize this problem by giving customers the possibility to choose the value of the notes at the time of withdrawal. For this, they need your help to know, given the S value of the withdrawal and how many notes of each value the machine has, how many different ways there are to deliver the S value.the bank provides notes of 2, 5, 10, 20, 50 and 100. For example, if S = 22 and the number of notes of each value is N2=5, N5 = 4, N10=3, N20 = 10, N50 = 0 and N100=10, then there are 4 distinct forms of the machine deliver the withdrawal amount: 20+2, 10+10+2, 10+5+5+2 e 5+5+5+5+2.
Entry
The first line of the input contains an integer S, the value of the draw. The second row contains six integers N2, N5, N10, N20, N50 and N100, respectively, the number of notes of values 2,5,10,20,50 and 100, available on the machine.
Output
Your program must print an integer, the number of distinct ways the machine delivers the serve.
I just don't know how to count how many possibilities, even more so that there are many ways. So far this is what I've managed to implement in my code (the forms function is obviously not implemented at all):
#include <stdio.h>
typedef struct{
int q;
int v;
}din;
int start(din n[],int t,int i){
if(t>=n[i].v) return i;
else return start(n,t,i-1);
}
int forms(din n[6],int t,int i){
int x,k=t,c=0;
if(n[x].q==0) return forms(n,t,i-1);
else{
if(k==0){
c++;
}
else{
}
}
}
int main(void){
int t,x;
din n[6];
scanf("%d",&t);
for(x=0;x<6;x++) scanf("%d",&n[x].q);
for(x=0;x<6;x++){
if(x==0) n[x].v=2;
else if(x==1) n[x].v=5;
else if(x==2) n[x].v=10;
else if(x==3) n[x].v=20;
else if(x==4) n[x].v=50;
else if(x==5) n[x].v=100;
}
printf("%d\n",forms(n,t,start(n,t,5));
return 0;
}
1 answers
This problem is known, in English, as "coin change problem" and if there is interest just give a quick Google search that you can understand how all the possibilities are calculated.
But the problem you presented, in particular, has an interesting particularity: the amount of notes is limited. In most solutions you will find on the internet, one works with an infinite amount of banknotes (or coins)
Well, I did some changes your code and replaces the functions start(args) and forms(args) with a function only called count(args). Then I tested with the case you presented and a few more others and apparently it's working . The solution follows below:
#include <stdio.h>
typedef struct{
int q;
int v;
}din;
int count(din notas[], int indice, int saque){
if(saque == 0) {return 1;}
if(saque < 0){return 0;}
if(indice < 0){return 0;}
int esq, dir;
if (notas[indice].q <= 0){
esq = 0;
} else {
/*Para se controlar o número de notas, subtrai-se antes de chamar a função e,
com o retorno da função, restitui-se o valor ao estado anterior*/
notas[indice].q--;
esq = count(notas, indice, saque - notas[indice].v);
notas[indice].q++;
}
dir = count(notas, indice - 1, saque);
return esq + dir;
}
int main(void){
int t,x;
din n[6];
scanf("%d",&t);
for(x=0;x<6;x++) scanf("%d",&n[x].q);
for(x=0;x<6;x++){
if(x==0) n[x].v=2;
else if(x==1) n[x].v=5;
else if(x==2) n[x].v=10;
else if(x==3) n[x].v=20;
else if(x==4) n[x].v=50;
else if(x==5) n[x].v=100;
}
printf("%d\n",count(n, 5, t));
return 0;
}