Solved

a smart alogorithm needed

Posted on 1998-12-25
3
166 Views
Last Modified: 2010-04-16

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'<<counter<<'\n';
}
 

merry christmess to you all.
 
0
Comment
Question by:levkovitz
3 Comments
 
LVL 84

Expert Comment

by:ozo
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

by:
zebada earned 50 total points
ID: 1181042
=====================================================================
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.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

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

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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

789 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question