谁能解决：找零钱的问题 - 编程论坛

#2

chengwen10162010-03-07 19:57

枚举的，不知道速度符不符合楼主要求。
#include <iostream>
using namespace std;

long int count(int n)
{
    long int sum = 0;
    int i, j, k, p, q, r, s;
    for (i = 0; i <= n/100; i++)
        for (j = 0; j <= n/50; j++)
            for (k = 0; k <= n/20; k++)
                for (p = 0; p <= n/10; p++)
                    for (q = 0; q <= n/5; q++)
                        for (r = 0; r <= n/2; r++)
                            for (s = 0; s <= n; s++)
                            {
                                if (100*i + 50*j + 20*k + 10*p + 5*q + 2*r + s == n)
                                    sum++;
                            }
    return sum;
}

int main()
{
    int n;
    cin >> n;
    while (n != 0)
    {
        cout << "Total = " << count(n) << endl;
        cin >> n;
    }
    return 0;
}

#3

寻找南方2010-03-08 02:05

看你的思路和程序都很好，但为什么你的程序我复制到VC++6.0中执行的没效果啊！！是不是你的空格太多了！

#4

cnfarer2010-03-08 08:16

应该还有更好的方法（上面的改了下）
#include <iostream>
using namespace std;

void count(int n)
{
    int sum=0;
    int i, j, k, p, q, r, s;
    for (i = 0; i <= n/100; i++)
        for (j = 0; j <= n/50; j++)
            for (k = 0; k <= n/20; k++)
                for (p = 0; p <= n/10; p++)
                    for (q = 0; q <= n/5; q++)
                        for (r = 0; r <= n/2; r++)
                        {
                            s=n-(100*i + 50*j + 20*k + 10*p + 5*q + 2*r);
                            if  (s>=0&&i+j+k+p+q+s<=100)
                            {
                                printf("100:%d  50:%d  20:%d  10:%d  5:%d  2:%d  1:%d\n",i,j,k,p,q,r,s);
                                sum++;
                            }
                        }
                        cout<<"共有"<<sum<<"种方法！"<<endl;
}

int main()
{
    int n;
    cin >> n;
    while (n != 0)
    {
        count(n);
        cin >> n;
    }
    return 0;
}

#5

chengwen10162010-03-08 19:21

回复 3楼寻找南方

程序能否执行和空格的多少没关系的。我用的也是 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[i][0] = 1;
        dp[i][1] = 1;
    }
    for (i = 0; i < 251; i++)
    {
        dp[0][i] = 1;
        dp[1][i] = 1;
    }
    for (i = 2; i < 8; i++)
    {
        for (j = 2; j < 251; j++)
        {
            if (j - money[i] >= 0) dp[i][j] = dp[i][j-money[i]] + dp[i-1][j];
            else                   dp[i][j] = dp[i-1][j];
        }
    }

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