본문 바로가기
IT 이론/자료구조&알고리즘

Chainging Coin System 관련

by id 2013. 4. 15.
반응형

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])

}

반응형

댓글0