c语言 找零钱问题，谢谢

Question

我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。

注意：
要求带入250进去算时，系统不能超时。
我自己做的方法做到200时，系统就算不出来了。

PS：
如果大家知道的话，请问暴力穷举法是什么？
最好有 源程序。
这里的超时算是能算出来，只是带入200以上的数进去就很慢，像卡住一样，能不能有更快的方法。
example:
input
4
output
3

Answer 1

这很容易。
先输入n值，然后从最大面值的人民币开始减。例如：
我有238元
减最大面值的第一个。238－100＝138。结果为正数且不为零。然后记录100元张数的变量加1（这些变量都应初始化时为0）
继续，138－100＝38.结果正数且不为零，同上100面值变量加1，
38－100。结果小于零。不再用100面值的减。
38－50。结果同样小于零，不再用50面值的减。
38－20＝18.结果为正数且不为零，20元张数的变量加1，
18－20。结果小于零。不再用20面值的减。
18－10＝8。结果为正数且不为零，10元张数的变量加1，
8－10.结果小于零。不再用10面值的减。
8-5＝3。结果为正数且不为零，5元张数的变量加1，
3-5。结果小于零。不再用5面值的减。
3-2＝1.结果为正数且不为零，2元张数的变量加1，
1-1＝0.结果为零。1元张数变量加1.显示结果。

你有：
100元（2）张，50元（0）张，20元（1）张，10元（1）张，5元（1）张，2元（1）张，1元（1）张。

Answer 2

这个题目穷举是不行的， 用动态规划做吧

---------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main ()
{
long value,result[1000];
long i, j, v, n;
scanf ("%ld%ld",&v, &n);
result[0] = 1;
for (i = 1; i <= v; i ++) {
scanf ("%ld", &value);
for (j = value; j <= n; j ++) {
result[j] = result[j] + result[j - value];
}
printf ("\n");
}
printf ("result = %ld\n", result[j - 1]);
}

--------------------

代码算出有多少种组合， 没有计算面额总数不超过100张的.....QQ:421668239

Answer 3

跟据楼上(回答者：zhangyong073P)算得100张及以内共：140953种。 俺给代码完善了一下，俺是初学C++.

#include<iostream>
using namespace std;
int main()
{
int money;
unsigned long counter=0;
int i, j, k, l, s, h, v;
cout<< "please input money\n";
cin>>money;

for (i = 0; i <= money; ++i)
for (j = 0; j <= money/2; ++j)
for (k = 0; k <= money/5; ++k)
for (l = 0; l <= money/10; ++l)
for (s = 0; s <= money/20; ++s)
for (h = 0; h <= money/50; ++h)
for (v = 0; v <= money/100; ++v)

if(i+j+k+l+s+h+v<=100)
{

if (i + j * 2 + k * 5 + l * 10 + s * 20 + h * 50 + v * 100 == money)
{
counter=counter+1;
cout<<"counter"<<counter;
cout<<" 1yuan:"<<i<<" 2yuan:"<<j<<" 5yuan"<<k<<" 10yuan"<<l<<" 20yuan"<<s<<" 50yuan"<<h<<" 100yuan"<<v<<endl;

}

}

cin.get();
cin.get();
return 0;
}

Answer 4

这里面竟然没一个人看懂楼主的问题的，楼上那个看懂一半但是程序没有一般性 楼主说的是任意一个数 不只是250。。。 。。。 看到另一封帖子同样的问题看来也是楼主发的，相信已经得到答案了吧，那篇中的“龟十三 - 见习魔法师”的就是正解！只是需要把变量count改为长整形：
#include<stdio.h>
int main()
{int a,b,c,d,e,f,g,n;
long count=0；
printf(" please input n:\n");
scanf("%d",&n);
for(a=n/100;a>=0;a--)
for(b=(n-100*a)/50;b>=0;b--)
for(c=(n-100*a-50*b)/20;c>=0;c--)
for(d=(n-100*a-50*b-20*c)/10;d>=0;d--)
for(e=(n-100*a-50*b-20*c-10*d)/5;e>=0;e--)
for(f=(n-100*a-50*b-20*c-10*d-5*e)/2;f>=0;f--)
{g=n-100*a-50*b-20*c-10*d-5*e-2*f;
if(a+b+c+d+e+f+g<=100)
{count++;
printf(" 100:%d--50:%d--20:%d--10:%d--5:%d--2:%d--1:%d\n",a,b,c,d,e,f,g);
};
}
printf(" n=%d,count=%ld\n",n,count);
return 0;}

我试了下201答案是62705
250的话答案是140953

Answer 5

楼主，我干脆直说吧，我认为要想找出N=250时候的全部组合，不可能有太简单的算法！你想：组合数这么多，140953 种啊！无论多么好的算法，总是要进行判断吧？总是要得出这140953 个答案吧？别的不说，光是将这140953 个结果输出就注定了要不少时间！
再说了，区区几分钟运行时间，还算长吗？你大概还没有见过算好些天的程序吧？