CODEWITHSUNDEEP
c++arraysrecursion
Zud
Zud

Reputation: 4477

Problem with C++ program output

Example: Let’s say your user input is 6.

Then the number of sequences that sum up to 6 is 11 (including 6 itself). This is shown clearly below:

6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
4+2
2+2+2
3+3

You SHOULD NOT have any sequences that repeat. You cannot have 2+2+1+1 and 1+1+2+2 as two different combinations!!

CODE:

#include <iostream>

using namespace std;

int sum(double number, int min, int & counter)
{
    int temp=0, n;
    n=number+temp;
    if ((number>=(n/2)) & (number!=0))
    {
        number --;
        temp ++;
        while (number>=(n/2))
        {
            cout << number << "+"<< temp << "\n";
            number --;
            temp ++;
            counter ++;
        }
    }
    else if (number==0)
    {
        return 0;
    }

    sum(n-min, 1,counter);

    return 0;
}

int main()
{
    int number, counter=1;


    cout << "Please enter the number: ";
    cin >> number ;
    cout << "\n";

    sum(number, 1, counter);
    cout << counter;

    return 0;
}

My output is

6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
3+1+2
2+3+1
4+2
2+2+2
3+3
0+1

Total out is 13.

Real output which is a shorter version for those of you who dont like whats posted above.

5+1
4+2
3+3
4+1
3+2
2+3
3+1
2+2
2+1
1+2
1+1
0+1

13

Where 1+2 and 2+3 are doubles as listed above.

Any ideas what is wrong here?

Upvotes: 0

Views: 668

Answers (4)

Drew D.
Drew D.

Reputation: 411

Well the logical AND operator in C++ is &&, not & as you have in this line:

if ((number>=(n/2)) & (number!=0))

Upvotes: 0

ruslik
ruslik

Reputation: 14880

I've already posted a solution to it in your previous question:

void sum_r(int n, int m, int cnt, int* nums){
    for (;n >= m; m++)
        sum_r(n-m, nums[cnt] = m, cnt+1, nums);
    if (!n) for (int i=0; i<cnt; i++) printf("%d%c",nums[i],(i==cnt-1)?'\n':'+');
};

void sum(int n){
    int nums[100];
    return sum_r(n, 1, 0, nums);
};

int main(){
    sum(6);
    return 0;
};

EDIT: I'll try to explain it better. The main idea is to impose an order on the generated sequence, it will help in avoiding repetition.
We will use the min parameter for that, it will be the smallest possible term we can use from now on in the sequence.
The function sum_r just prints the sequence of values of min at each recursion level.
The num term is used as a kind of accumulator, or the value left "to spare".

We can write a simplier function, that just counts the number of such sequences:

int sum_c(int n, int m){ 
    if (!n) return 1; // termination condition. end of sequence reached with "perfect match". this means we have found 1 additional sequence. Note that it's the only way of adding new values to result.
    int comb_cnt = 0;
    while (n >= m) { // we need a stop condition, and there is no point in having negative value of (n - m)
         comb_cnt +=   // here we accumulate all the solutions from next levels
            sum_c(n-m, m); // how many sequences are for current value of min?
         m++; // trying a larger `min`
    };
    return comb_cnt; // number of sequence fond at this level
};

Upvotes: 2

Daniel Trebbien
Daniel Trebbien

Reputation: 39208

Here's a hint: The problem is to compute the partitions of the input number. See also: partition function

Upvotes: 0

LavaScornedOven
LavaScornedOven

Reputation: 747

I guess it would be easier if you'd sum so that the first summand is always highest possible and you don't allow that of two adjacent summands the second one is greater than the first one.

Just a thought...

Upvotes: 4

Related Questions