原帖
https://bbs.bccn.net/viewthread.php?tid=424300&page=1&extra=#pid2369874
希望可以不仅统计个数，还可以列出其所包含的各种情况（尽量有算法+程序+解释哦）

mark

这个要求有点过分了！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 编辑 ]

250 的 out.txt 18.8M  共 140953 种

我在原贴中的代码是错误的。当时考虑的不够严谨，没有经过仔细的论证就以为已经满足了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;
}

最佩服   B版简洁的代码了！

过奖了。上一段代码还不够简洁，这和思维方式有关。下面这段代码我更改了计算方向，代码更简洁一些，效率提高了一个数量级（上一段代码在我的电脑上初始化部分耗时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;
}

呃，话说有谁看懂我这两段代码了没？

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

代码好深啊...   看不懂
这样会不会影响代码的可读性啊？
B 版你以后还是加上注释吧，不然理解真的困难

好像是悬赏贴. 版主应该设置限时高亮.