关于求5元硬币找零的问题

会飞的_海豚

题目是有一枚5元硬币，找零成1元，5角，1角的硬币。求有多少种方法？
我写的代码如下：
#include<stdio.h>
#define MAX 50
int count;
void partition(int x,int y,int z)
{
        if((x+y+z)==MAX)
       
                count++;
               
       
        else
        {
                if((x+y+z)<MAX)
                {
                        partition(x+10,y,z);
                        partition(x,y+5,z);
                        partition(x,y,z+1);
                }
        }
}
int main()
{
        partition(0,0,0);
        printf("%d\n",count);
        return 0;
}
打印输出count的值是1W9多，请问关于这个递归是哪里出错了？

flynetcn

这else写法看着真别扭

bruceteen

1元 + 5角 + 1元
和
2元 + 5角
在你的代码中算是两种方法

1. #include <stdio.h>
   
2. 
   
3. int main( void )
   
4. {
   
5.     unsigned count = 0;
   
6.     for( unsigned a=0; 10*a<=50; ++a )
   
7.         for( unsigned b=0; 10*a+5*b<=50; ++b )
   
8.             ++count;
   
9.     printf( "%u\n", count ); // 36
   
10. }

复制代码

jason680

回复 1# 会飞的_海豚

$ ./get_coin 50
(  0,  0, 50) (  0,  1, 45) (  0,  2, 40) (  0,  3, 35) (  0,  4, 30) count=5
(  0,  5, 25) (  0,  6, 20) (  0,  7, 15) (  0,  8, 10) (  0,  9,  5) count=10
(  0, 10,  0) (  1,  0, 40) (  1,  1, 35) (  1,  2, 30) (  1,  3, 25) count=15
(  1,  4, 20) (  1,  5, 15) (  1,  6, 10) (  1,  7,  5) (  1,  8,  0) count=20
(  2,  0, 30) (  2,  1, 25) (  2,  2, 20) (  2,  3, 15) (  2,  4, 10) count=25
(  2,  5,  5) (  2,  6,  0) (  3,  0, 20) (  3,  1, 15) (  3,  2, 10) count=30
(  3,  3,  5) (  3,  4,  0) (  4,  0, 10) (  4,  1,  5) (  4,  2,  0) count=35
(  5,  0,  0)
Total count=36

$ ./get_coin 33
(  0,  0, 33) (  0,  1, 28) (  0,  2, 23) (  0,  3, 18) (  0,  4, 13) count=5
(  0,  5,  8) (  0,  6,  3) (  1,  0, 23) (  1,  1, 18) (  1,  2, 13) count=10
(  1,  3,  8) (  1,  4,  3) (  2,  0, 13) (  2,  1,  8) (  2,  2,  3) count=15
(  3,  0,  3)
Total count=16


$ cat get_coin.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int total = 10;

int count = 0;
void partition(int v10,int v5,int v1) {

  int value  = v10*10+v5*5+v1;
  if(value == total){
    printf("(%3d,%3d,%3d) ",v10,v5,v1);
    ++count;
    if(count%5==0)
      printf("count=%d\n", count);
    return;
  }
  if(value < total) {
    if(value<= total)
      partition(v10,v5,v1+total-value);
    if(value+ 5 <= total && v1==0)
      partition(v10,v5+1,v1);
    if(value+10 <=total && v5==0 && v1==0)
      partition(v10+1,v5,v1);
  }
}
int main(int argc, char**argv) {
  if(argc == 2){
    if(atoi(argv[1])>0)
      total = atoi(argv[1]);
  }
  partition(0,0,0);
  printf("\nTotal count=%d\n",count);
  return 0;
}

ouyixq

Don't undermine your worth by comparing yourself and others.

dorodaloo

打印输出count的值是32，
请问关于这个递归哪里出错了？

1. #include <stdio.h>
   
2. #define MAX 50
   
3. int count = 0;
   
4. int done[10 + 1][5 + 1][1 + 1];
   
5. 
   
6. void partition(int x, int y, int z) {
   
7.   int total = x * 10 + y * 5 + z * 1;
   
8. 
   
9.   if (total > MAX)
   
10.     return;
    
11.   if (total == MAX) {
    
12.     if (done[x][y][z])
    
13.       return;
    
14.     printf("%d %d %d\n", x, y, z);
    
15.     count++;
    
16.     done[x][y][z] = 1;
    
17.   } else {
    
18.     partition(x + 1, y, z);
    
19.     partition(x, y + 1, z);
    
20.     partition(x, y, z + 1);
    
21.   }
    
22. }
    
23. 
    
24. int main() {
    
25.   partition(0, 0, 0);
    
26.   printf("%d\n", count);
    
27.   return 0;
    
28. }
    

复制代码

dorodaloo

输出36
乐不可支

1. #include <stdio.h>
   
2. #define MAX 50
   
3. int count = 0;
   
4. int done[MAX / 10 + 1][MAX / 5 + 1][MAX / 1 + 1];
   
5. 
   
6. void partition(int x, int y, int z, int total) {
   
7.     if (total > MAX) return;
   
8.     if (total == MAX) {
   
9.         if (done[x][y][z]) return;
   
10.         printf("%d %d %d\n", x, y, z);
    
11.         count++;
    
12.         done[x][y][z] = 1;
    
13.     } else {
    
14.         partition(x + 1, y, z, total + 10);
    
15.         partition(x, y + 1, z, total + 5);
    
16.         partition(x, y, z + 1, total + 1);
    
17.     }
    
18. }
    
19. 
    
20. int main() {
    
21.     partition(0, 0, 0, 0);
    
22.     printf("%d\n", count);
    
23.     return 0;
    
24. }
    

复制代码

1. #include <stdio.h>
   
2. #define MAX 50
   
3. int count = 0;
   
4. int done[MAX / 10 + 1][MAX / 5 + 1][MAX / 1 + 1];
   
5. 
   
6. void partition(int x, int y, int z) {
   
7.     int total = x * 10 + y * 5 + z * 1;
   
8.    
   
9.     if (total > MAX) return;
   
10.     if (total == MAX) {
    
11.         if (done[x][y][z]) return;
    
12.         printf("%d %d %d\n", x, y, z);
    
13.         count++;
    
14.         done[x][y][z] = 1;
    
15.     } else {
    
16.         partition(x + 1, y, z);
    
17.         partition(x, y + 1, z);
    
18.         partition(x, y, z + 1);
    
19.     }
    
20. }
    
21. 
    
22. int main() {
    
23.     partition(0, 0, 0);
    
24.     printf("%d\n", count);
    
25.     return 0;
    
26. }
    

复制代码

jason680

回复 7# dorodaloo

这算法....重复太多

$ time ./get_coin_long
5 0 0
4 2 0
...
0 1 45
0 0 50
count=36
partition=16094656

real    0m0.325s
user    0m0.184s
sys    0m0.000s


$ time ./get_coin 50
(  0,  0, 50) (  0,  1, 45) (  0,  2, 40) (  0,  3, 35) (  0,  4, 30) count=5
(  0,  5, 25) (  0,  6, 20) (  0,  7, 15) (  0,  8, 10) (  0,  9,  5) count=10
(  0, 10,  0) (  1,  0, 40) (  1,  1, 35) (  1,  2, 30) (  1,  3, 25) count=15
(  1,  4, 20) (  1,  5, 15) (  1,  6, 10) (  1,  7,  5) (  1,  8,  0) count=20
(  2,  0, 30) (  2,  1, 25) (  2,  2, 20) (  2,  3, 15) (  2,  4, 10) count=25
(  2,  5,  5) (  2,  6,  0) (  3,  0, 20) (  3,  1, 15) (  3,  2, 10) count=30
(  3,  3,  5) (  3,  4,  0) (  4,  0, 10) (  4,  1,  5) (  4,  2,  0) count=35
(  5,  0,  0)
Total count=36

partition count=66

real    0m0.003s
user    0m0.000s
sys    0m0.004s



$ cat get_coin_long.c
#include <stdio.h>
#define MAX 50
int count = 0;
int done[10 + 1][5 + 1][MAX + 1];

long part_count = 0;
void partition(int x, int y, int z) {
    int total = x * 10 + y * 5 + z * 1;
   
    ++part_count;
    if (total > MAX) return;
    if (total == MAX) {
        if (done[x][y][z]) return;
        printf("%d %d %d\n", x, y, z);
        count++;
        done[x][y][z] = 1;
    } else {
        partition(x + 1, y, z);
        partition(x, y + 1, z);
        partition(x, y, z + 1);
    }
}

int main() {
    partition(0, 0, 0);
    printf("count=%d\n", count);
    printf("partition=%ld\n", part_count);
    return 0;
}

dorodaloo

回复 8# jason680

大牛求解优化算法

int main(){
    给定C枚硬币，它们的面值分别为
    int coin[] = { 1, 2, 5, 10, 20, 25, 50 };
    求对于给定的金额N，可以从这C枚硬币中找出多少种组合，
    每种组合的金额总数刚好为N
    int money = 3000;
    int count = count(coin, 7, money);
    printf ("count = %d ", count);
    return 0;
}

jason680

回复 9# dorodaloo

非递归（for）与递归差异
注：非递归（for）由3楼改

$ m=100; time ./get_coin $m; time ./get_coin_cyc $m; time ./get_coin_cyc1 $m
   Total count=6730

real    0m0.001s
user    0m0.000s
sys    0m0.000s
   Total count=6730
function count=7426

real    0m0.001s
user    0m0.004s
sys    0m0.000s
   Total count=6730
function count=696

real    0m0.001s
user    0m0.000s
sys    0m0.000s

$ m=500; time ./get_coin $m; time ./get_coin_cyc $m; time ./get_coin_cyc1 $m
   Total count=16262126

real    0m0.165s
user    0m0.060s
sys    0m0.000s
   Total count=16262126
function count=16634622

real    0m0.453s
user    0m0.164s
sys    0m0.000s
   Total count=16262126
function count=372496

real    0m0.020s
user    0m0.004s
sys    0m0.004s

$ m=800; time ./get_coin $m; time ./get_coin_cyc $m; time ./get_coin_cyc1 $m
   Total count=217981557

real    0m2.016s
user    0m0.796s
sys    0m0.000s
   Total count=217981557
function count=221152875

real    0m5.518s
user    0m2.180s
sys    0m0.000s
   Total count=217981557
function count=3171318

real    0m0.096s
user    0m0.036s
sys    0m0.000s

$ m=1000; time ./get_coin $m; time ./get_coin_cyc $m; time ./get_coin_cyc1 $m
   Total count=769465576

real    0m7.100s
user    0m2.772s
sys    0m0.000s
   Total count=769465576
function count=778472662

real    0m19.374s
user    0m7.668s
sys    0m0.008s
   Total count=769465576
function count=9007086

real    0m0.257s
user    0m0.096s
sys    0m0.000s


$ time ./get_coin_cyc1 1500
   Total count=7885220976
function count=62023776

real    0m1.646s
user    0m0.652s
sys    0m0.004s

$ time ./get_coin_cyc1 2000
   Total count=41979451451
function count=248667566

real    0m6.638s
user    0m2.604s
sys    0m0.004s

$ time ./get_coin_cyc1 3000
   Total count=452756092626
function count=1795441446

real    0m47.511s
user    0m18.725s
sys    0m0.016s

$ cat get_coin.c
#include <stdio.h>
#include <stdlib.h>

int main( int argc, char **argv  )
{
  long long count = 0;
   
  int coin[7] = { 1, 2, 5, 10, 20, 25, 50 };
  int c[7],v[7];
  int money = 3000;
  if(argc == 2){
    if(atoi(argv[1])>0)
      money = atoi(argv[1]);
  }
  for( c[6]=0; c[6]*coin[6]<=money; ++c[6] ){
    v[6] = c[6] * coin[6];
    for( c[5]=0; v[6]+c[5]*coin[5]<=money; ++c[5] ){
      v[5] = v[6]+c[5]*coin[5];
      for( c[4]=0; v[5]+c[4]*coin[4]<=money; ++c[4] ){
        v[4] = v[5]+c[4]*coin[4];
        for( c[3]=0; v[4]+c[3]*coin[3]<=money; ++c[3] ){
          v[3] = v[4]+c[3]*coin[3];
          for( c[2]=0; v[3]+c[2]*coin[2]<=money; ++c[2] ){
            v[2] = v[3]+c[2]*coin[2];
            for( c[1]=0; v[2]+c[1]*coin[1]<=money; ++c[1] )
              ++count;
          }
        }
      }
    }
  }
  printf( "   Total count=%llu\n", count );
  return 0;
}



$ cat get_coin_cyc.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int total = 10;

int count = 0;
long long fun_count = 0;
long long get_count(int coin[],int num,int money) {

  long long count = 0;
  ++fun_count;

  if(--num == 0) return 1;
  
  int cyc = money/coin[num] + 1;
  for(int n=0; n < cyc; ++n){
    count += get_count(coin, num, money - n*coin[num]);
  }
  return count;
}
int main(int argc, char**argv) {
  int coin[7] = { 1, 2, 5, 10, 20, 25, 50 };
  int money = 3000;
  if(argc == 2){
    if(atoi(argv[1])>0)
      money = atoi(argv[1]);
  }
  long long count = get_count(coin, 7, money);

  printf("   Total count=%lld\n", count);
  printf("function count=%lld\n", fun_count);
  return 0;
}