免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12
最近访问板块 发新帖

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

论坛徽章:
6
数据库技术版块每日发帖之星
日期: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:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2017-12-28 13:17 |显示全部楼层
回复 10# jason680
大牛求
get_coin_cyc1的代码

论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期: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未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
发表于 2017-12-31 17:51 |显示全部楼层
回复 11# dorodaloo

$ time ./get_coin_cyc2 3000; time ./get_coin_cyc1 3000
   Total count=452756092626
function count=14708260

real    0m1.067s
user    0m0.468s
sys    0m0.004s
   Total count=452756092626
function count=1795441446

real    0m47.081s
user    0m22.777s
sys    0m0.072s

get_coin_cyc.c
  if(--num == 0) return 1;

get_coin_cyc1.c
  if(--num == 1) return( ... );

get_coin_cyc2.c
  --num
  if(num == 2&& money%5==0) return( ... );
  if(num == 1) return( ... );

论坛徽章:
0
发表于 2018-01-05 16:05 |显示全部楼层
#include <stdio.h>
#define MAX 50
int main(int argc,char* argv[])
{
        int count=0;
        for(int i=0;i<=5;i++)
        {
                for(int j=0;j<=10;j++)
                {
                        for(int k=0;k<=50;k++)
                        {
                                if(i*10+j*5+k==50)
                                        {
                                                count++;
                                                printf("1元硬币:%d;5角硬币:%d;1角硬币:%d\n",i,j,k);
                                                }
                                }
                        }
                }
                printf("总方法:%d\n",count);
        return 0;
        }

论坛徽章:
6
数据库技术版块每日发帖之星
日期: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:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-01-06 21:15 |显示全部楼层
回复 12# jason680

大牛求get_coin_cyc2代码

论坛徽章:
6
数据库技术版块每日发帖之星
日期: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:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-01-06 21:51 |显示全部楼层
回复 12# jason680

越来越牛逼,结果还是令人震惊的,竟然只有1s

论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期: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未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
发表于 2018-01-28 07:45 |显示全部楼层
本帖最后由 jason680 于 2018-01-29 13:46 编辑
dorodaloo 发表于 2017-12-28 13:17
回复 10# jason680
大牛求
get_coin_cyc1的代码


找出"更快"的算法/方法...

money=0
5 2 1
------
x 0 0
count = 1

money=1
5 2 1
------
x 0 1
count = 1

money=2
5 2 1
------
x 0 2
x 1 0
count = 2

money=3
5 2 1
------
x 0 3
x 1 1
count = 2

money=4
5 2 1
------
x 0 4
x 1 2
x 2 0
count = 3

money=5
5 2 1
------
x 0 5
x 1 3
x 2 1
count = 3

...

money 0,1,2,3,4,5,...
count  1,1,2,2,3,3,....

// get_coin_cyc1.c
if(--num == 1) return(money/2+1);

// get_coin_cyc.c
if(--num == 0) return 1;


Note: in coin array
... [3] [2] [1] [0]  <== num
...  10  5    2    1  <== value


论坛徽章:
6
数据库技术版块每日发帖之星
日期: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:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-01-29 21:31 |显示全部楼层
回复 16# jason680

非常感谢
太强了,绝对要顶啊.

这一般不单纯啊

论坛徽章:
11
2015年迎新春徽章
日期:2015-03-04 09:55:282017金鸡报晓
日期:2017-02-08 10:39:4215-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:1715-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:2015-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:1215-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:182016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52每日论坛发贴之星
日期:2016-02-07 06:20:00程序设计版块每日发帖之星
日期:2016-02-07 06:20:0015-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37
发表于 2018-02-22 16:42 |显示全部楼层
用python (C++++)

count = []
for c10 in range(6):
    s0 = c10*10
    if s0 > 50:
        break
    for c5 in range(11):
        s1 = s0+c5*5
        if s1 > 50:
            break
        for c1 in range(51):
            s2 = s1+c1
            if s2 == 50:
                count.append((c10,c5,c1))
            if s2 > 50:
                break
print len(count)
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP