?
Solved

a smart alogorithm needed

Posted on 1998-12-25
3
Medium Priority
?
169 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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 200 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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

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…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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 be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

770 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