Solved

Posted on 1998-12-25

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 ()

{

cout<<"please enter 5 complete numbers"<<'\n';

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'<<co

}

merry christmess to you all.

3 Comments

Output of program:

please enter 5 complete numbers

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

}

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

cout<<"please enter 5 complete numbers"<<'\n';

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="<<soluti

// 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="<<soluti

// 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="<<soluti

}

Question has a verified solution.

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

Title | # Comments | Views | Activity |
---|---|---|---|

multi threaded debug dll option in visual studio | 2 | 95 | |

TCP/IP Socket - connection close results in data lost | 14 | 120 | |

FMX TCameraComponent Problem | 2 | 52 | |

Error creating a new C++ project in ,net | 20 | 21 |

The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**15** Experts available now in Live!