忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 徽章 文库 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 2686 | 回复: 14

[C] 关于求5元硬币找零的问题 [复制链接]

论坛徽章:
0
发表于 2017-12-17 14:24 |显示全部楼层
题目是有一枚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多,请问关于这个递归是哪里出错了?

论坛徽章:
3
金牛座
日期:2013-10-12 15:42:452015年辞旧岁徽章
日期:2015-03-03 16:54:15IT运维版块每日发帖之星
日期:2016-06-01 06:20:00
发表于 2017-12-17 20:15 |显示全部楼层
这else写法看着真别扭

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2017-12-18 08:36 |显示全部楼层
1元 + 5角 + 1元

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

  1. #include <stdio.h>

  2. int main( void )
  3. {
  4.     unsigned count = 0;
  5.     for( unsigned a=0; 10*a<=50; ++a )
  6.         for( unsigned b=0; 10*a+5*b<=50; ++b )
  7.             ++count;
  8.     printf( "%u\n", count ); // 36
  9. }
复制代码

论坛徽章:
128
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2017-12-18 20:34 |显示全部楼层
本帖最后由 jason680 于 2017-12-18 20:39 编辑

回复 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;
}

论坛徽章:
0
发表于 2017-12-19 14:06 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-12-19 15:54 |显示全部楼层
打印输出count的值是32,
请问关于这个递归哪里出错了?
  1. #include <stdio.h>
  2. #define MAX 50
  3. int count = 0;
  4. int done[10 + 1][5 + 1][1 + 1];

  5. void partition(int x, int y, int z) {
  6.   int total = x * 10 + y * 5 + z * 1;

  7.   if (total > MAX)
  8.     return;
  9.   if (total == MAX) {
  10.     if (done[x][y][z])
  11.       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. int main() {
  22.   partition(0, 0, 0);
  23.   printf("%d\n", count);
  24.   return 0;
  25. }
复制代码

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-12-19 17:16 |显示全部楼层
本帖最后由 dorodaloo 于 2017-12-19 19:30 编辑

输出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. void partition(int x, int y, int z, int total) {
  6.     if (total > MAX) return;
  7.     if (total == MAX) {
  8.         if (done[x][y][z]) return;
  9.         printf("%d %d %d\n", x, y, z);
  10.         count++;
  11.         done[x][y][z] = 1;
  12.     } else {
  13.         partition(x + 1, y, z, total + 10);
  14.         partition(x, y + 1, z, total + 5);
  15.         partition(x, y, z + 1, total + 1);
  16.     }
  17. }

  18. int main() {
  19.     partition(0, 0, 0, 0);
  20.     printf("%d\n", count);
  21.     return 0;
  22. }
复制代码
  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. void partition(int x, int y, int z) {
  6.     int total = x * 10 + y * 5 + z * 1;
  7.    
  8.     if (total > MAX) return;
  9.     if (total == MAX) {
  10.         if (done[x][y][z]) return;
  11.         printf("%d %d %d\n", x, y, z);
  12.         count++;
  13.         done[x][y][z] = 1;
  14.     } else {
  15.         partition(x + 1, y, z);
  16.         partition(x, y + 1, z);
  17.         partition(x, y, z + 1);
  18.     }
  19. }

  20. int main() {
  21.     partition(0, 0, 0);
  22.     printf("%d\n", count);
  23.     return 0;
  24. }
复制代码

论坛徽章:
128
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2017-12-20 10:11 |显示全部楼层
回复 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;
}

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-12-20 14:58 |显示全部楼层
回复 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;
}

论坛徽章:
128
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2017-12-21 10:58 |显示全部楼层
本帖最后由 jason680 于 2017-12-21 11:01 编辑

回复 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;
}


您需要登录后才可以回帖 登录 | 注册

本版积分规则

DTCC2018购票6.8折优惠进行时

中国数据库技术大会是国内数据库及大数据领域规模最大、最受欢迎的技术交流盛会。 2018年5月10-12日,第九届中国数据库技术大会将如约而至。本届大会以“数领先机•智赢未来”为主题,设定2大主会场及20个技术专场,邀请来自国内外互联网、金融、教育等行业百余位技术专家,共同探讨Oracle、MySQL、NoSQL、大数据等领域的前瞻性热点话题与技术。
----------------------------------------
优惠时间:2018年2月13日前

报名链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP