| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4492 人关注过本帖, 1 人收藏
标题:对C语言---换零钱问题的进一步请教
只看楼主 加入收藏
a151141
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:1
帖 子:197
专家分:680
注 册:2012-10-19
结帖率:78.57%
收藏(1)
已结贴  问题点数:50 回复次数:10 
对C语言---换零钱问题的进一步请教
原帖
https://bbs.bccn.net/viewthread.php?tid=424300&page=1&extra=#pid2369874
希望可以不仅统计个数,还可以列出其所包含的各种情况(尽量有算法+程序+解释哦)
搜索更多相关主题的帖子: C语言 统计 
2013-11-28 00:24
pink_duo
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:209
专家分:1054
注 册:2013-11-5
收藏
得分:10 
mark

埋头做牛,抬头做人,低头做狗
2013-11-28 11:06
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:10 
这个要求有点过分了!250的结果是十万的数量级,仅输出十万种结果程序就得跑很久,而且意义不大。

程序代码:
#include <stdio.h>

#define  SIZE  7    //sizeof(data) / sizeof(int)
#define  N   250

int data[] = {1, 2, 5, 10, 20, 50, 100};
int result[N] = {};

void fun(int ip, int flag, int sum)
{
    if (100 < ip)    return;
    if (0 > sum)    return;
    if (0 == sum)
    {
        for (int i = 0; i < ip; i++)
        {
            printf_s("%d ", result[i]);
        }
        puts("\n");

        return;
    }

    for (int i = flag; i < SIZE; i++)
    {
        result[ip] = data[i];
        fun(ip+1, i, sum-result[ip]);
    }
}

int main()
{
    FILE *fp;
    freopen_s(&fp, "out.txt", "w", stdout);

    fun(0, 0, 50);

    fclose(stdout);
    return 0;
}


[ 本帖最后由 azzbcc 于 2013-11-28 13:49 编辑 ]


[fly]存在即是合理[/fly]
2013-11-28 13:43
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
250 的 out.txt 18.8M  共 140953 种


[fly]存在即是合理[/fly]
2013-11-28 13:53
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:10 
我在原贴中的代码是错误的。当时考虑的不够严谨,没有经过仔细的论证就以为已经满足了100张纸币的限制,结果只是对面值为1的及金额在100以下的满足。

至于原贴中的其它代码(楼主的和你找的)都没有考虑纸币数量的限制,而这恰恰是这道题的重点。

下面是更正后的算法代码,时间原因暂不解释。而穷举输出每一种结果,确实没什么意义。会输出全排列或组合吗?会那个,就会这个。

程序代码:
#include<stdio.h>
#define M    250
#define N    100
int main()
{
    int f[M + 1][N + 1] = {0};
    int a[] = {1, 2, 5, 10, 20, 50, 100};
    int i, j, k, t, p;
    
    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    for(j = M; j >= a[i]; j--)
    for(k = 1; k <= N; k++)
    {
        if(k * a[i] == j) f[j][k]++;
        for(t = j, p = k; (t -= a[i]) > 0 && --p > 0; f[j][k] += f[t][p]);
    }

    for(i = 1; i <= M; i++)
    for(j = 1; j <= N; j++)
        f[i][0] += f[i][j];
    
    while(scanf("%d", &i), i) printf("%d\n", f[i][0]);
    
    return 0;
}

重剑无锋,大巧不工
2013-11-29 23:53
韶志
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:斗气大陆
等 级:贵宾
威 望:44
帖 子:2223
专家分:13592
注 册:2013-3-22
收藏
得分:10 
回复 5楼 beyondyf
最佩服   B版简洁的代码了!

三十年河东,三十年河西,莫欺少年穷!
2013-11-30 00:43
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 6楼 韶志
过奖了。上一段代码还不够简洁,这和思维方式有关。下面这段代码我更改了计算方向,代码更简洁一些,效率提高了一个数量级(上一段代码在我的电脑上初始化部分耗时43毫秒,下面这段3毫秒)。呵呵,玩算法就是这样,不断的改进过程正是它的乐趣所在。

程序代码:
#include<stdio.h>
#define M    250
#define N    100
int main()
{
    int f[M + 1][N + 1] = {0};
    int a[] = {1, 2, 5, 10, 20, 50, 100};
    int i, j, k;
    
    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    for(f[j = a[i]][1] = 1; j <= M; j++)
    for(k = 2; k <= N; k++)
        f[j][k] += f[j - a[i]][k - 1];

    for(i = 1; i <= M; i++)
    for(j = 1; j <= N; j++)
        f[i][0] += f[i][j];
    
    while(scanf("%d", &i), i) printf("%d\n", f[i][0]);
    
    return 0;
}

重剑无锋,大巧不工
2013-11-30 20:49
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呃,话说有谁看懂我这两段代码了没?

呵呵,算是促进一下大家读代码的能力,谁能解释一下这两段代码中任意一段的算法原理,我奖励100专家分。

重剑无锋,大巧不工
2013-12-01 23:02
韶志
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:斗气大陆
等 级:贵宾
威 望:44
帖 子:2223
专家分:13592
注 册:2013-3-22
收藏
得分:0 
回复 8楼 beyondyf
代码好深啊...   看不懂
这样会不会影响代码的可读性啊?
B 版你以后还是加上注释吧,不然理解真的困难

三十年河东,三十年河西,莫欺少年穷!
2013-12-01 23:48
pangshch
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:2
帖 子:443
专家分:1966
注 册:2013-4-9
收藏
得分:10 
回复 8楼 beyondyf
好像是悬赏贴. 版主应该设置限时高亮.
2013-12-03 14:36
快速回复:对C语言---换零钱问题的进一步请教
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016882 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved