Solved

a smart alogorithm needed

Posted on 1998-12-25
3
167 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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
SetCurrentDirectory path limit 7 144
typedef std::deque<BYTE> ByteVector is broken in vs2012 23 90
How can i compile this github project?? 2 99
boost::uuid crashes 17 40
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
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.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

733 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