SOLVE EQUATION

[DaniDak]

Given an equation A + B + C = X, where X is a constant, and A,B,C are nonnegative integers, I need to list all the possible equation solutions and how many solutions there are.
//the user should be able to enter a number greater then 10 [e.g. A=11; B=15; C=2]

e.g.
user enters: A=1; B=1; C=1; X=3
solution1: 3:0:0
solution2: 2:1:0
solution3: 1:1:1
//and so on until you get all the possible combinations, then you print out the
total number of solutions: ***

I really appreciate any help.

 

[jinappa]

Well, what you have here is a basically a 3 variable integration with range from 0 to user entry for each variable where user entry is always positive. I would start out with something like this:

user enters 3
void someclass::getVariations(int x)
{
int a =0, b=0, c=0;

for(a =0; a <=x; a++)
{
for(b = 0; b <= x; b++)
{
for(c = 0; c <=x; c++)
{
if(a + b + c == x )
{
printf(&quot;a = %d, b = %b, c = %c&quot;,a,b,c);
break;
}
}
}
}

Actually, I think that will do it.
Good Luck and let me know how it turns out.

 

[jinappa]

OOPs, forgot a solution counter.

int someclass::getVariations(int x)
{
int a =0, b=0, c=0;
int count =0;

for(a =0; a <=x; a++)
{
for(b = 0; b <= x; b++)
{
for(c = 0; c <=x; c++)
{
if(a + b + c == x )
{
++count;
printf(&quot;solution %d %d:%d:%d&quot;,count,a,b,c);
break;
}
}
}
return count;
}

OK, that should do it now. Sorry about that. Good Luck.

 

[Zyrenthian]

I believe there is a combinatorics solution to this that will avoid doing all the overhead of the looping.

lets say x = 3 // simple example

there should exist

3 choose 1 + 3 choose 1 + 3 choose 1 +( 3%2 ? 1:-1)
MATHEMATICALLY
nC(1)+nC(1)+nC(1)+(n%2?1:-1)// +1 if odd -1 if even

combinations

or simply 3+3+3+ combinations and they would be

0 0 3
0 3 0
3 0 0
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
1 1 1

and four would look like

0 0 0 4
0 0 4 0
0 4 0 0
4 0 0 0
1 1 1 1
1 1 2 0
1 1 0 2
1 2 1 0
1 2 0 1
2 1 1 0
2 1 0 1
2 0 1 1
2 2 0 0
2 0 2 0
2 0 0 2

CHOOSE is defined as:

n CHOOSE m = n!/((n-m)!m!) : n>=m

zero factorial is defined as 1

See if that can save you some calculations and test it against the above to verify. It could help when you get a number like 100000

Matt

 

[Zyrenthian]

OH BTW... the above are PERMUTATIONS actually. if you want to exclude 0 0 n when you already have n 0 0 and 0 n 0 then n would be the answer (pretty sure of that)

Matt

 

[Zyrenthian]

ONE MORE BTW LOL

This was written for 3 variables and is not tested for other situations. If this is to be expanded please test it.
The number of CHOOSE's you do is based on the number of variables.

Matt

 

[Zyrenthian]

DOH... I hate taht... i forgot 3's in the 4 example

3 1 0 0
3 0 1 1
3 1 0 1

which kills my theory and brings the total of combinations for 4 to 18 and not 15... let me get back to you on this... it will take me a bit but the has to exist a mathematical equation to save you the time of looping

<number of variables> to the <number of variables power>

Matt

 

[Zyrenthian]

Ok... my original theory was bad... here is a function to determine it (written for 3 variables... untested for more or less)

int NumberOfCombinationsTotaling(int x)
{
   if(x == 0)
      return 1;
   
   return x+NumberOfCombinationsTotaling(x-1);
}
int GetCombinations(int x)
{
	return x+NumberOfCombinationsTotaling(x);
}


cout<<GetCombinations(x)<<&quot; Combinations\n&quot;;

That will do it for you. Not as elegant but it is defined as

# combinations of x = summation of i (i = 1 to x+1)

Good luck... thanx for the fun

Matt

 

[Zyrenthian]

LOL... guess i could have just done

int Summation(int x)
{
if(x== 0)
return 0;
return x+Summation(x-1);
}

Summation(x+1);

Oh well... i look at things the hard way

 

[Leibnitz]

These should be the complete solution to that problem !

#include <iostream>
#include <windows.h>
using namespace std;
int main(int argc, char* argv[])
{
int i, j, k, z = 0;
int A[100];
int B[100];
int C[100];
int X;
int second = 1000;
cout<<&quot;\t\t\tEquation solver&quot;<<endl<<endl;
cout<<&quot;Enter a number: &quot;;
cin>>X;
for( i = 0;i <= X; i++ )
{
for( j = 0; j <= X; j++ )
{
for( k = 0; k <= X; k++ )
{
if( i + j + k == X )
{
A[z] = i;
B[z] = j;
C[z] = k;
z++;
}
}
}
}
for( i = 0;i < z; i++ )
{
if( A < 10 && B < 10 )

cout<<&quot;A = &quot;<<A<<&quot; B = &quot;<<B<<&quot; C = &quot;<<C<<endl;
Sleep( 0*second );
}
if( A >= 10 )
{
cout<<&quot;A = &quot;<<A<<&quot; B = &quot;<<B<<&quot; C = &quot;<<C<<endl;
Sleep( 0*second );
}
if( B >= 10 )
{
cout<<&quot;A = &quot;<<A<<&quot; B = &quot;<<B<<&quot; C = &quot;<<C<<endl;
Sleep( 0*second );
}
}
cout<<&quot;There are &quot;<<z<<&quot; solutions to the equation A + B + C = &quot;<<X<<endl;
return 0;
}

notice that the number of solutions to that equation can be found by using this formula: Solution(X) = (X + 1)*(X + 2)/2
example: if X = 10,we have Solution(3) = 11*12/2=66;

 

[Leibnitz]

Oops ! There were a few errors while compiling the code but now it is working smuthly !

#include <iostream>
#include <windows.h>
using namespace std;
int main(int argc, char* argv[])
{
int i, j, k, z = 0;
int A[100];
int B[100];
int C[100];
int X;
int second = 1000;
cout<<&quot;\t\t\tEquation solver&quot;<<endl<<endl;
cout<<&quot;Enter a number: &quot;;
cin>>X;
for( i = 0;i <= X; i++ )
{
for( j = 0; j <= X; j++ )
{
for( k = 0; k <= X; k++ )
{
if( i + j + k == X )
{
A[z] = i;
B[z] = j;
C[z] = k;
z++;
}
}
}
}
for( i = 0;i < z; i++ )
{
if( A < 10 && B < 10 )
{
cout<<&quot;A = &quot;<<A<<&quot; B = &quot;<<B<<&quot; C = &quot;<<C<<endl;
Sleep( 0*second );
}
if( A >= 10 )
{
cout<<&quot;A = &quot;<<A<<&quot; B = &quot;<<B<<&quot; C = &quot;<<C<<endl;
Sleep( 0*second );
}
if( B >= 10 )
{
cout<<&quot;A = &quot;<<A<<&quot; B = &quot;<<B<<&quot; C = &quot;<<C<<endl;
Sleep( 0*second );
}
}
cout<<&quot;There are &quot;<<z<<&quot; solutions to the equation A + B + C = &quot;<<X<<endl;
return 0;
}

 

[jinappa]

Ok Guys, Here we come to the issue of practicality. Zyrenthian is coming up with mathematical formula to figure out what is going on in one line while Leibnitz is using the looping technique I used except of course he is adding in arrays to save the values and display them seperately.

The question here is readability and maintenance. I would say that the formala approach will probably be faster, but will anyone other than the author be able to understand it.
What happens if the requirements change...mmm... in that case a new formula will be required. The loops on the other hand are fairly easy to read and can be easily changed, even though somewhat less efficent, so I would say use the looping approach to keep in mind the poor sap who has to change the code 6 months from now after the original author has left the company. What say you?

 

[chiph]

Something else to think about is that the original question sounded like a school assignment.

Chip H.