need help in backtrack algorithm

Discussion in 'C++' started by AmaScatman, Nov 6, 2008.

  1. AmaScatman

    AmaScatman New Member

    Joined:
    Nov 6, 2008
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    hi all..
    i need help in solving a backtrack algorithm using c++ .

    the program asks the user for a number , and the output will be all the sums of the number entered.. for example:

    if the user entered 10.. the output should be:
    1+2+3+4
    1+2+7
    1+3+6
    1+4+5
    1+9
    2+3+5
    2+8
    3+7
    4+6
    10

    example 2.. if the user entered 6.. the output should be:
    1+2+3
    1+5
    2+4
    6
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Can you post the code you've got so far (use code blocks to make it easier to read, just wrap the code with [ code ] and [ /code ] (without spaces)) and let us know where you're stuck - what line of code is it where you have the problem, and what is it doing that you didn't expect, or not doing that you did?
     
  3. AmaScatman

    AmaScatman New Member

    Joined:
    Nov 6, 2008
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Code:
     
    #include <iostream.h>
    #include <conio.h>
    
    int val=0,start=0;
    
    void sumAlgo(int n){
    
    if(start==n){ cout<<n; return ;}
    
    val=0;
    start++;
    
    for(int i=0 ; i<n ; i++){
     val=start+i;
     if(n == val && i>start) cout<<start<<"+"<<i<<endl;
    }
    
    sumAlgo(n);
    }
    
    
    main(){
     int numb;
     cout<<"enter a number :";
     cin>>numb;
    
    sumAlgo(numb);
    getch();
    }
    
    well thats my code so far..... it only displays 2 sums--- for example:
    if the user eneter 10 the output will be:
    1+9
    2+8
    3+7
    4+6
    10

    so i need help in the "sumAlgo" function.. i think i should use a backtrack algorithm.... but i don't know how!!
    any suggestions??
     
  4. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    For expressing it as the sum of two numbers, I found it easey...but for greater than 2, I think I need to work out further....

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<malloc.h>
    
    void main()
    {
    int *a, *b;
    int i,m;
    printf("\nEnter your number=");
    scanf("%d",&m);
    a=(int *)malloc((m-1)*sizeof(int));
    b=(int *)malloc((m-1)*sizeof(int));
    for(i=0;i<m-1;i++)
    {
    a[i]=i+1;
    b[i]=m-i-1;
    }
    for(i=0;a[i]<=b[i];i++)
    {
    printf("\n%d+%d=%d\n", a[i],b[i],m);
    }
    getch();
    }
    
    Cheers....
     
  5. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Right now I worked it out for three nos. as well....but for n nos. the printing statement is troubling me....I think it'll need more time....

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<malloc.h>
    
    void main()
    {
    int *a, *b, *c;
    int i,j,k,m,sum;
    printf("\nEnter your number=");
    scanf("%d",&m);
    a=(int *)malloc((m-1)*sizeof(int));
    b=(int *)malloc((m-1)*sizeof(int));
    c=(int *)malloc((m-1)*sizeof(int));
    for(i=0;i<m-1;i++)
    {
    a[i]=i+1;
    b[i]=i+1;
    c[i]=i+1;
    }
    for(i=0;i<m-1;i++)
    {
    for(j=0;j<m-1;j++)
    {
    for(k=0;k<m-1;k++)
    {
    sum=a[i]+b[j]+c[k];
    if(sum==m)
    printf("\n%d+%d+%d=%d\n", a[i],b[j],c[k],m);
    else
    sum=0;
    }
    }
    }
    getch();
    }
    
    BTW.....the program can be done in form of writing functions as well....

    Cheers....
     
  6. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    One more thing.....the last program is not void of showing repeated results, e.g. it is showing 1+1+8=10 and 1+8+1=10 and 8+1+1=10 all three....I need to work out there as well....

    Cheers....
     
  7. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Seems like a good use of recursion; top level looks at 1..n/2 (for n=10, it looks at 1-5), then deduct that from n and call itself. Subsequent levels look at 1..(n-(sum of all previous levels))/2.
     
  8. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Yes....that's right....

    But for higher sum representation, what will be the expression??
    I mean say we want to print this sum

    "1+1+1+1+....n times=n" by means of printf....how are we gonna do that????
    Coz, we dunno what no. of "%d"s we are gonna use....
    This was the major problem I was facing...

    Cheers anyway...
     
  9. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Just printf one %d each time round a loop:
    Code:
    	printf("Enter a number: ");
    	char buf[32];
    	fgets(buf,30,stdin);
    	int max=atoi(buf);
    	for (int i=1; i<=max; i++)
    	{
    		printf("%d ",i);
    	}
    
    Output:
    Enter a number: 7
    1 2 3 4 5 6 7

    Or, to use your example:
    Code:
    	int max=atoi(buf);
    	for (int i=1; i<max; i++)
    	{
    		printf("1+");
    	}
    	printf("1=%d\n",max);
    
    Output:
    Enter a number: 5
    1+1+1+1+1=5

    So you'd need to store the numbers to print in an array, then determine when in the function you need to print something (say if you're not going to recurse again for the current number, e.g. for 10 you would want to iterate further for 1+2 but not for 1+9, so if you've got {1,2} so far, you print nothing and recurse, but if you've got {1,9} then you know that adds up to 10 so you print "1+9" and don't recurse).

    Ultimately what you probably want is a program that recurses only as deep as necessary, eliminates (or avoids, which is better) duplicates, and gives output something like:
    Enter a number: 15
    1+2+3+4+5
    1+2+4+8
    1+2+5+7
    1+3+4+7
    1+3+5+6
    1+6+8
    2+3+4+6
    2+5+8
    2+6+7
    3+4+8
    3+5+7
    4+5+6
    7+8
     
  10. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Exactly....I am trying....and trying....and trying....
    Just because my sem is near, I am not being able to concentrate fully...
     
  11. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Well, as I often say, how would you do it on paper?

    Let's say we're finding sums of 15, and we're part way through, and we have 2 at the start of the array.
    In the recursive function we want to loop, but from what to what? 1..15? Would there be any point starting at 1 if we just want increasing sums? Would there be any point starting at 2 if we want to avoid duplicates? Once we've decided where we want to start counting from, how would we work that out?

    What would be the upper limit? Remember from the output above, the sums starting with 2 are 2+3+4+6, 2+5+8 and 2+6+7.

    Having decided on the loop, what now goes in the loop? We want to put the current number in the loop. How do we know what entry in the array to use? The first level would use [0], the second [1], the third [2], is there a pattern here that we could work out from something?

    After assigning something to somewhere in the array, what next? Let's say we've got 2+3. Does this add up to 15? Do we want to print anything? Do we want to recurse deeper? What about when we get to 2+13 (just realised that's missing from my output above - bug fixed). Same three questions. Would it be appropriate to use an if/else here? What would the test be? What would we do (a) if that test is true; (b) if that test is false?

    Corrected output for 15:

    Enter a number: 15
    1+2+3+4+5
    1+2+3+9
    1+2+4+8
    1+2+5+7
    1+2+12
    1+3+4+7
    1+3+5+6
    1+3+11
    1+4+10
    1+5+9
    1+6+8
    1+14
    2+3+4+6
    2+3+10
    2+4+9
    2+5+8
    2+6+7
    2+13
    3+4+8
    3+5+7
    3+12
    4+5+6
    4+11
    5+10
    6+9
    7+8
     
  12. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Correction: the sums starting with 2 are:
    2+3+4+6
    2+3+10
    2+4+9
    2+5+8
    2+6+7
    2+13
     
  13. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    But xpi0t0s, the sum beginning with 1 can also be with repeatations, I mean;
    1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=15
    isn't it??
     
  14. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    There aren't any repeats in the opening post. Two examples were given, neither show any repeats. The second was:

    > example 2.. if the user entered 6.. the output should be:
    > 1+2+3
    > 1+5
    > 2+4
    > 6

    As you see, 1+1+1+1+1+1 wasn't listed, nor were 1+1+4, 2+2+2, 3+3 and so on.

    This is why you shouldn't hijack other people's threads. If you've got *EXACTLY* the same issue then maybe it's OK but it's still better to open your own thread so that any help is specific to your situation. There's no shortage of numbers and it doesn't cost anything to create a new thread. And if you've got a different issue then it'll only create confusion, as you can see.
     
  15. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Sorry....the moment I saw the thread, I went for trying it, without reading it completely....I have no intention to hijack someone's thread, not even of opening a new thread...I am extremely sorry....
     
  16. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Of course, if duplicates are allowed, then the sums of 15 starting with 2 are too many to list here; I count 4096. The first few:
    2+1+1+1+1+1+1+1+1+1+1+1+1+1
    2+1+1+1+1+1+1+1+1+1+1+1+2
    2+1+1+1+1+1+1+1+1+1+1+2+1
    2+1+1+1+1+1+1+1+1+1+1+3
    2+1+1+1+1+1+1+1+1+1+2+1+1
    2+1+1+1+1+1+1+1+1+1+2+2
    2+1+1+1+1+1+1+1+1+1+3+1
    2+1+1+1+1+1+1+1+1+1+4

    some more:
    2+1+3+2+4+1+1+1
    2+1+3+2+4+1+2
    2+1+3+2+4+2+1
    2+1+3+2+4+3
    2+1+3+2+5+1+1
    2+1+3+2+5+2
    2+1+3+2+6+1
    2+1+3+2+7
    2+1+3+3+1+1+1+1+1+1

    and the last few:
    2+9+4
    2+10+1+1+1
    2+10+1+2
    2+10+2+1
    2+10+3
    2+11+1+1
    2+11+2
    2+12+1
    2+13
     
  17. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    In total I got 16384 sums adding up to 15, just using positive non-zero integers.
     
  18. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    I have counted them as well...that's what was confusing me...
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice