Solved

# a smart alogorithm needed

Posted on 1998-12-25
Medium Priority
171 Views

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
Question by:levkovitz

LVL 85

Expert Comment

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

LVL 6

Accepted Solution

ID: 1181042
=====================================================================
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 Comment

ID: 1181043
thank you very much.
i don't have enough words to tell you how much you helped me.
merry christmas
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
###### Suggested Courses
Course of the Month13 days, 12 hours left to enroll