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