0 
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?

Improve this question
10
  • That code does not look like it would produce that output. Commented Dec 10, 2010 at 1:09
  • It doesn't exactly but for the sake of helping whoever is looking at my code i put that in it really comes out in a shorter version. Commented Dec 10, 2010 at 1:10
  • When I run your code, the output I get is nothing like that. Can you please post your actual code, or the actual output you get? Commented Dec 10, 2010 at 1:15
  • @ Anon: Look at the post again. I did post it shortly before your last post. Commented Dec 10, 2010 at 1:20
  • Now that we have your actual output, the problem is much bigger than what you initially claimed. The fact that you're only getting sequences of two elements, and they're not always adding up to the target value, is a much bigger issue than elements being doubled. Commented Dec 10, 2010 at 1:23

4 Answers 4

Reset to default
4

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...

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Right, the idea is to produce a monotone sequence.
2

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
};
Improve this answer

4 Comments

This is not an acceptable answer you completely changed my code. This would not be work i've done but work someone else has done.
@Alec: That's very nice of you :) However, it works perfectly, so you can reverse engineer it, and then write your own version.
@ruslik: Sorry to be kinda harsh lol. That's what i would have done but i don't think I've learned some of the things in your code yet so I'm not 100% sure i could reverse engineer it.
@ruslik is there any way you can help me out on this a little more. Your the only one who seams to understand what im trying to work out... But i can seam to trace your code....
0

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

Improve this answer

Comments

0

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

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

5 Comments

Technically & is bitwise AND. && is logical AND
in this case & has the same effect (and is even faster!)
The only difference between && and & in C++ (and in most languages) is that && is short-circuited; that is, in evaluating a && b, the expression b is not evaluated if a is false.
@Daniel... for arguments of type bool. They are definitely NOT the same for other types. e.g. if (1 && 2) vs if (1 & 2) have totally different behavior.
@Ben: Yes, that is true. I should have said that the only difference between && and & as logical operators is... . &, of course, has the additional use of bitwise-ANDing the operands.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.