need help in backtrack algorithm

AmaScatman's Avatar, Join Date: Nov 2008
Newbie Member
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
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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?
0
AmaScatman's Avatar, Join Date: Nov 2008
Newbie Member
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??
0
back from retirement's Avatar, Join Date: Nov 2008
Contributor
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....
0
back from retirement's Avatar, Join Date: Nov 2008
Contributor
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....
0
back from retirement's Avatar, Join Date: Nov 2008
Contributor
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....
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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.
0
back from retirement's Avatar, Join Date: Nov 2008
Contributor
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...
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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
0
back from retirement's Avatar, Join Date: Nov 2008
Contributor
Exactly....I am trying....and trying....and trying....
Just because my sem is near, I am not being able to concentrate fully...