Problem with a recursive partition (number theory) function
Example: Let’s say your user input is 6. Then the number of sequences that sum up to 6 is 11 (including 6 itself). The problem I am having is that it works when the user enters 1 or 6, but if not it is way off and I can't figure out why.
I can give more info on the subject if needed.
#include <iostream>
using namespace std;
int sum(double number, int min, int & counter)
{
int temp=0, n;
n=number+temp;
if (number>=(n/2.0)+.5 && (number!=1))
{
number --;
temp ++;
while (number>=(n/2.0))
{
number --;
开发者_开发技巧 temp ++;
counter ++;
}
}
else if (number==1)
{
counter ++;
return 0;
}
sum(n-1, 1,counter);
return 0;
}
int main()
{
int counter=1;
double number;
cout << "-------------------------------------------------------\n"
<< "Please enter the number: ";
cin >> number ;
cout << "\n";
if (number!=1)
{
sum(number, 1, counter);
}
cout << "The total number of combinations that result in a sum of "
<< number << " is: " << counter
<< "\n-------------------------------------------------------\n";
return 0;
}
I read wiki article you pointed out, they give some instructions how to build recursive defined function. It looks different then your code. The code below works for me
#include <iostream>
using namespace std;
int sum(int k, int n)
{
if(k == 1 || n == 1)
return 1;
if(k < n)
return sum (k, k);
else if (k == n)
return 1 + sum (k, k-1);
else
return sum (k,n-1) + sum (k-n, n);
}
int main (void)
{
int counter=1;
double number;
cout << "-------------------------------------------------------\n"
<< "Please enter the number: ";
cin >> number ;
cout << "\n";
counter = sum(number, number);
cout << "The total number of combinations that result in a sum of "
<< number << " is: " << counter
<< "\n-------------------------------------------------------\n";
return 0;
}
You can test this code here
精彩评论