Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   need help in backtrack algorithm (http://www.go4expert.com/forums/help-backtrack-algorithm-t15008/)

AmaScatman 6Nov2008 19:42

need help in backtrack algorithm
 
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

xpi0t0s 6Nov2008 22:43

Re: need help in backtrack algorithm
 
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?

AmaScatman 8Nov2008 16:23

Re: need help in backtrack algorithm
 
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??

back from retirement 22Nov2008 21:19

Re: need help in backtrack algorithm
 
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....

back from retirement 22Nov2008 21:28

Re: need help in backtrack algorithm
 
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....

back from retirement 22Nov2008 21:30

Re: need help in backtrack algorithm
 
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....

xpi0t0s 23Nov2008 00:53

Re: need help in backtrack algorithm
 
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.

back from retirement 23Nov2008 11:10

Re: need help in backtrack algorithm
 
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...

xpi0t0s 23Nov2008 20:11

Re: need help in backtrack algorithm
 
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

back from retirement 23Nov2008 20:16

Re: need help in backtrack algorithm
 
Exactly....I am trying....and trying....and trying....
Just because my sem is near, I am not being able to concentrate fully...


All times are GMT +5.5. The time now is 09:15.