fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. #define MAX_AMOUNT_LIST 8192
  6. #define KIND_OF_COIN    6
  7.  
  8. typedef struct Coin {
  9.     int  amount;
  10.     int  coinNum[KIND_OF_COIN];
  11. } Coin;
  12.  
  13. typedef struct CoinStats {
  14.     int    coinWorth[KIND_OF_COIN];
  15.     int    coinWeight[KIND_OF_COIN];
  16.     int    coinNum[KIND_OF_COIN];
  17.     int    coinTypeNum;
  18. } CoinStats;
  19.  
  20. // initialize coin stats (global)
  21. static CoinStats cs = {{   1,   5,  10,  50, 100, 500},
  22.                        {  10,  37,  45,  40,  48,  70},
  23.                        {   0,   0,   0,   0,   0,   0},
  24.                         KIND_OF_COIN};
  25.  
  26. void Sort(Coin *amountList, int amountNum)
  27. {
  28.     int  i, j;
  29.     Coin tmp;
  30.  
  31.     // sort by amount (bubble sort)
  32.     for (i = 0; i < amountNum - 1; i++) {
  33.         for (j = 0; j < amountNum - 1 - i; j++) {
  34.             if (amountList[j].amount > amountList[j+1].amount) {
  35.                 tmp = amountList[j];
  36.                 amountList[j] = amountList[j+1];
  37.                 amountList[j+1] = tmp;
  38.             }
  39.         }
  40.     }
  41. }
  42.  
  43. void CheckWeight(int depth, int remain, Coin *amountList, int *amountNum)
  44. {
  45.     int    i;
  46.     int    nextRemain;
  47.  
  48.     while (remain >= cs.coinWeight[depth] * cs.coinNum[depth]) {
  49.         nextRemain = remain - cs.coinNum[depth] * cs.coinWeight[depth];
  50.         if (depth == KIND_OF_COIN - 1) {
  51.             // if exact weight then add current stats to amountList
  52.             if (remain == (cs.coinNum[depth] * cs.coinWeight[depth])) {
  53.                 if (*amountNum < MAX_AMOUNT_LIST) {
  54.                     amountList[*amountNum].amount = 0;
  55.                     for (i = 0; i < cs.coinTypeNum; i++) {
  56.                         amountList[*amountNum].amount += cs.coinWorth[i] * cs.coinNum[i];
  57.                         amountList[*amountNum].coinNum[i] = cs.coinNum[i];
  58.                     }
  59.                     (*amountNum)++;
  60.                 } else {
  61.                      printf("List Buffer Overflow !\n");
  62.                 }
  63.             }
  64.             cs.coinNum[depth]++;
  65.         } else {
  66.             cs.coinNum[depth + 1] = 0;
  67.             CheckWeight(depth + 1, nextRemain, amountList, amountNum);
  68.             cs.coinNum[depth]++;
  69.         }
  70.     }
  71. }
  72.  
  73. int main(void)
  74. {
  75.     char   strbuf[256];
  76.     int    i;
  77.     int    weight;
  78.  
  79.     Coin   amountList[MAX_AMOUNT_LIST];  // result buffer
  80.     int    amountNum = 0;                // number of result
  81.  
  82.     printf("Weight of Coins (gram) : ");
  83.     fgets(strbuf, sizeof(strbuf), stdin);
  84.     weight = round(atof(strbuf) * 10);
  85.  
  86.     cs.coinNum[0] = 0;
  87.     CheckWeight(0, weight, amountList, &amountNum);
  88.     Sort(amountList, amountNum);
  89.  
  90.     printf("\nCoin Weight    : %.1f g\n", (double)weight / 10);
  91.     if (amountNum == 0) {
  92.         printf("No combination found. (may be FAKE !)\n");
  93.     } else {
  94.         printf("Number of List : %d\n", amountNum);
  95.         printf("amount(yen) :   1yen   5yen  10yen  50yen 100yen 500yen\n");
  96.         printf("---------------------------------------------------------\n");
  97.         for (i = 0; i < amountNum; i++) {
  98.             printf(" %10d : %6d %6d %6d %6d %6d %6d\n", amountList[i].amount, 
  99.                         amountList[i].coinNum[0], amountList[i].coinNum[1],
  100.                         amountList[i].coinNum[2], amountList[i].coinNum[3],
  101.                         amountList[i].coinNum[4], amountList[i].coinNum[5]);
  102.         }
  103.     }
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0s 2156KB
comments (?)
stdin
copy 
23.7
stdout
copy 
Weight of Coins (gram) : 
Coin Weight    : 23.7 g
Number of List : 23
amount(yen) :   1yen   5yen  10yen  50yen 100yen 500yen
---------------------------------------------------------
         25 :     20      1      0      0      0      0
         36 :     11      1      2      0      0      0
         47 :      2      1      4      0      0      0
         71 :     16      1      0      1      0      0
         82 :      7      1      2      1      0      0
        117 :     12      1      0      2      0      0
        127 :      7      2      1      0      1      0
        128 :      3      1      2      2      0      0
        163 :      8      1      0      3      0      0
        173 :      3      2      1      1      1      0
        209 :      4      1      0      4      0      0
        218 :      3      3      0      0      2      0
        255 :      0      1      0      5      0      0
        410 :      0      0      1      0      4      0
        518 :     13      1      0      0      0      1
        529 :      4      1      2      0      0      1
        564 :      9      1      0      1      0      1
        575 :      0      1      2      1      0      1
        610 :      5      1      0      2      0      1
        620 :      0      2      1      0      1      1
        656 :      1      1      0      3      0      1
       1011 :      6      1      0      0      0      2
       1057 :      2      1      0      1      0      2
https://ideone.com/vE7UPP
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!