C语言，找零钱的问题。 - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → C语言，找零钱的问题。

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 9356 人关注过本帖

标题：C语言，找零钱的问题。

只看楼主加入收藏

linqiang1225

等　级：新手上路
帖　子：15
专家分：0
注　册：2013-11-23
结帖率：50%

楼主

问题点数：0 回复次数：12

C语言，找零钱的问题。

题目是：描述
我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。
输入

输入有多组，每组一行，为一个整合n。
输入以0结束。

#include<stdio.h>
int main()
{
int n,a,b,c,d,e,f,g,s=0;
while(1)
{
scanf("%d",&n);
if(n==0)break;
for(a=0;a<=n/100;a++)
  for(b=0;b<=n/50;b++)
   for(c=0;c<=n/20;c++)
    for(d=0;d<=n/10;d++)
     for(e=0;e<=n/5;e++)
      for(f=0;f<=n/2;f++)
       for(g=0;g<=n;g++)
       {
        if(n==a*100+b*50+c*20+d*10+e*5+f*2+g)
        s++;
       }
printf("%d\n",s);
s=0;
}
return 0;
}
我这样叫上去显示超时的。谁有更好的方法吗？

搜索更多相关主题的帖子: include　人民币　 C语言　

2013-11-27 18:01

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 2 楼

得分:0

我有。代码也可以给你。麻烦你提交一下告诉我结果。

至于我的代码的解释，想听就请再开一贴。最好带点分以示诚意

程序代码：

#include<stdio.h>
#define min(a, b) ((a)<(b)?(a):(b))
int main()
{
    int f[251] = {0}, a[] = {1, 2, 5, 10, 20, 50, 100}, i, j, k;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    for(j = min(a[i] * 100, 250); j >= a[i]; j--)
    {
        if(j % a[i] == 0) f[j]++;
        for(k = j - a[i]; k > 0; k -= a[i])
            f[j] += f[k];
    }

    for(; scanf("%d", &i), i; printf("%d\n", f[i]));
    return 0;
}

重剑无锋，大巧不工

2013-11-27 21:46

经哥

来　自：代码空间
等　级：论坛游侠
威　望：1
帖　子：289
专家分：124
注　册：2012-9-8

第 3 楼

得分:0

回复 2楼 beyondyf

为什么我对版主的头像很喜欢，每次看到都有一种崇拜感，这不科学啊

我只是个演员，还是业余的！！

2013-11-27 23:58

a151141

等　级：黑侠
威　望：1
帖　子：197
专家分：680
注　册：2012-10-19

第 4 楼

得分:0

回复 2楼 beyondyf

呵呵，我愿意帮版主突破万分大关。
不过加一个小条件，希望不但可以统计个数，还可以列出其所包含的所有情况。（最好还有相应的解释啊，呵呵）
已开新帖https://bbs.bccn.net/viewthread.php?tid=424330&extra=page%3D1&frombbs=1

[ 本帖最后由 a151141 于 2013-11-28 00:25 编辑 ]

世界上幸福的事就是抓到一只羊，更幸福的事就是抓到两只羊……

2013-11-28 00:17

cosdos

来　自：ShangHai
等　级：蜘蛛侠
威　望：6
帖　子：2109
专家分：1385
注　册：2007-6-19

第 5 楼

得分:0

回复 2楼 beyondyf

250
176316

楼主的程序是199736

和穷举出来的有差异啊。

[ 本帖最后由 cosdos 于 2013-11-28 00:21 编辑 ]

—>〉Sun〈<—

2013-11-28 00:19

cosdos

来　自：ShangHai
等　级：蜘蛛侠
威　望：6
帖　子：2109
专家分：1385
注　册：2007-6-19

第 6 楼

得分:0

穿越

以下是引用chengwen1016在2010-3-8 19:21:07的发言：

程序能否执行和空格的多少没关系的。我用的也是 VC++6.0 可以的，看一下是不是别的问题。

想出了一个更好的办法，用dp做的。时间复杂度很低了，完全符合楼主要求。

代码如下:

#include <iostream>
using namespace std;

int money[8] = { 0, 1, 2, 5, 10, 20, 50, 100 };
long int dp[8][251];

int main()
{
    int i, j, n;
    for (i = 0; i < 8; i++)
    {
        dp[0] = 1;
        dp[1] = 1;
    }
    for (i = 0; i < 251; i++)
    {
        dp[0] = 1;
        dp[1] = 1;
    }
    for (i = 2; i < 8; i++)
    {
        for (j = 2; j < 251; j++)
        {
            if (j - money >= 0) dp[j] = dp[j-money] + dp[j];
            else                   dp[j] = dp[j];
        }
    }

    while (cin >> n && n != 0)
    {
        cout << "Total = " << dp[7][n] << endl;
    }
    return 0;
}

—>〉Sun〈<—

2013-11-28 00:25