Chainging Coin System 관련

Suppose you are in the wonder land in which the coin changing system is not governed by the greedy strategy. There are only 4 coins cl = 1, c2 = 3, c3 = 7, and c4 = 11 in the country.

 

(a) Construct N[0..21] and P[0..21] for changing 21 wons.

 

(b) Write a recursive program "void print_coins (int x)" to print optimal coins for x wons. You must assume that array P[0..21] is global to this program.

 

(a)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
N	0	1	2	1	2	3	2	1	2	3	2	1	2	3	2	3	4	3	2	3	4	3
P	0	1	1	3	1	1	3	7	1	1	3	1	1	1	3	1	1	3	7	1	1	3

 

N은 필요한 동전의 갯수, P는 사용되는 동전의 최소 단위이다.

 

(b)

void print_coins(int x) {

  if(x<=0) return;

  printf("%d", P[x]);

  print_coin (x - p[x])

}