大神的世界

跟a229的想法很像

迴圈

輸入N

輸入幣值

輸入金額

由大到小分配

迴圈

輸出

考慮可分之最大面額

(若可分之最大面額為輸入幣值之最小值

則跳出迴圈)

分一個出去

將其餘的重新分配

#include <iostream>

using namespace std;

void print(int number[], int N)
{
    cout << "(";
    for(int i = 0; i<N-1; i++)
        cout << number[i] << ",";
    cout << number[N-1] << ")\n";
}

int main()
{
    int N;
    int value[5];
    int number[5];
    int dollar;
    int lastValPos, lastVal, recycle;

    while(cin >> N)
    {
        for(int i = 0; i<N; i++)
            cin >> value[i];

        cin >> dollar;

        //分配
        for(int i = N-1; i>=0 && dollar > 0; i--)
        {
            number[i] = dollar/value[i];
            dollar -= value[i]*number[i];
        }

        while(true)
        {
            print(number, N);

            //找尋分配者
            for(lastValPos = N-1; number[lastValPos]==0; lastValPos--);

            if(lastValPos == 0)
                break;

            lastVal = value[lastValPos];
            number[lastValPos]--;

            //分配該數字
            for(int i = lastValPos-1; i>=0 && lastVal > 0; i--)
            {
                number[i] += lastVal/value[i];
                lastVal -= value[i]*number[i];
            }

            //重新分配
            recycle = value[lastValPos]*number[lastValPos];
            number[lastValPos] = 0;

            for(int i = N-1; i>=0 && recycle > 0; i--)
            {
                number[i] = recycle/value[i];
                recycle -= value[i]*number[i];
            }
        }
    }

    return 0;
}