// PP1.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#define LEN 5

void fun(int &sum, int factors[], int solv[], int n)

{

if (sum == 0)

{

for (int j = 0; j < LEN; ++j)

{

std::cout << solv[j] << " ";

}

std::cout << std::endl;

return;

}

if (n < 0)

{

return;

}

if (sum < factors[n])

{

fun(sum, factors, solv, –n);

}

else

{

int k = sum / factors[n];

for (int i = k; i >= 0; –i)

{

solv[n] = i;

int temp = (sum – (solv[n] * factors[n]));

fun(temp, factors, solv, n – 1);

sum = temp + solv[n] * factors[n];

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int f[LEN] = {5, 6, 7, 8, 9};

int s[LEN] = {0};

int sum = 8;

fun(sum, f, s, 4);

return 0;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

下面是改进版,尾递归

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


#include <iostream>
using namespace std;

#define LEN 5

int index[LEN] = {0};

void GetChange(int sum, int cents[], int index[], int current)
{
    if (sum == 0)
    {
        for (int i = 0; i < LEN; ++i)
        {
            cout << index[i] << " ";
        }
        cout << endl;
        return;
    }
    if (current < 0)
    {
        return;
    }
    if (sum < cents[current])
    {
        GetChange(sum, cents, index, current – 1);
    }
    else
    {
        int k = sum / cents[current];
        for (int i = k; i >= 0; –i)
        {
            index[current] = i;
            int temp = sum – cents[current] * i;
            GetChange(temp, cents, index, current – 1);
        }
    }
}

int main()
{
    int cents[LEN] = {1, 2, 5, 10, 20};
    int sum = 15;
    GetChange(sum, cents, index, LEN – 1);
    return 0;
}

Advertisements