• Status: Solved
• Priority: Medium
• Security: Public
• Views: 176

a smart alogorithm needed

i'm a student and my current project is to write an efficient program that reads 5 complete numbers
a,b,c,d,e,n
for that type of equation:
aX + bY +cZ = d
input - 5 complete numbers
output - the number of solutions to the equation  between
n and -n
according to my program i have n^3 possibilities and i'm looking for a more efficient alogorithm.
here is what i did:

#include <iostream.h>

void main ()
{
int a,b,c;
int d;
int n;
int solution = 0;
int na;
int nb;
int nc;
int num_of_solutions = 0;
int counter = 0;

cin>>a>>b>>c>>d>>n;

na = (-1)*n;
nb = (-1)*n;
nc = (-1)*n;

while (nc <= n){
solution = a*na + b*nb + c*nc;
if (solution == d)
num_of_sol ++;
na ++;
if (na == n+1){
nb ++;
na = -n;
}
if (nb == n+1){
nc ++;
nb = -n;
}
counter ++;

}
cout<<num_of_sol<<'\n'<<counter<<'\n';
}

merry christmess to you all.

0
levkovitz
1 Solution

Commented:
assuming a!=0, you could cut it to O(n^2) by solving for na given nb and nc.
0

Commented:
=====================================================================
Output of program:

2
4
6
12
100
Solutions=13464 Counter=8120601 Time(ms)=2564
Solutions=13464 Counter=8120601 Time(ms)=751
Solutions=13464 Counter=40401 Time(ms)=20

=====================================================================
Source code:

#include <stdlib.h>
#include <iostream.h>
#include <sys/timeb.h>

long
elapsed(struct _timeb f,struct _timeb t)
{
return (((t.time-f.time)*1000)+(t.millitm-f.millitm));
}

void
main(int argc, char *argv[])
{
int a,b,c,d,n;    // Inputs
int x,y,z;        // Loop counters
int rhs;          // Right hand side of equation
int na,nb,nc;     // Multipliers
int solutions=0;  // Number of solutions
int count=0;      // Number of iterations

struct _timeb start; // CPU start time
struct _timeb stop;  // CPU end time

cin>>a>>b>>c>>d>>n;

// This is your original version
// It executes (2n+1)^3 iterations
_ftime(&start);

na = (-1)*n;
nb = (-1)*n;
nc = (-1)*n;

while (nc <= n){
rhs = a*na + b*nb + c*nc;
if (rhs == d)
solutions ++;
na ++;
if (na == n+1){
nb ++;
na = -n;
}
if (nb == n+1){
nc ++;
nb = -n;
}
count ++;
}
_ftime(&stop);
cout<<"Solutions="<<solutions<<" Counter="<<count<<" Time(ms)="<<elapsed(start,stop)<<endl;

// This version makes efficient use of multiplications.
// It still executes (2n+1)^3 iterations
_ftime(&start);

solutions=0;
count=0;
na = n*a;
nb = n*b;
nc = n*c;
for ( x=-na ; x<=na ; x+=a ) {
for ( y=-nb ; y<=nb ; y+=b ) {
rhs = x+y;
for ( z=-nc ; z<=nc ; z+=c ) {
if ( rhs+z==d )
solutions++;
count++;
}
}
}
_ftime(&stop);
cout<<"Solutions="<<solutions<<" Counter="<<count<<" Time(ms)="<<elapsed(start,stop)<<endl;

// This version also makes efficient use of multiplications.
// but introduces modulo and division into the inner loop.
// However it only executes (2n+1)^2 iterations.
//
// aX+bY+cZ=d can be re-written like this: Z=((d-(xA+bY))/c
//
// Since Z must be a whole number between -n and n the
// solution to the equation is:
//
// rhs = d-(aX+bY))/c;
// if ( (rhs%c)==0 && abs(rhs)<=n ) then
//   a solution exists for a, b, c and d.
_ftime(&start);

solutions=0;
count=0;
na = n*a;
nb = n*b;
for ( x=-na ; x<=na ; x+=a ) {
for ( y=-nb ; y<=nb ; y+=b ) {
rhs = d-(x+y);
if ( rhs%c==0 && abs(rhs/c)<=n )
solutions++;
count++;
}
}
_ftime(&stop);
cout<<"Solutions="<<solutions<<" Counter="<<count<<" Time(ms)="<<elapsed(start,stop)<<endl;
}

0

Author Commented:
thank you very much.
i don't have enough words to tell you how much you helped me.
merry christmas
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.