Solved

a smart alogorithm needed

Posted on 1998-12-25
3
162 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
Comment Utility
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
Comment Utility
=====================================================================
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
Comment Utility
thank you very much.
i don't have enough words to tell you how much you helped me.
merry christmas
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
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 tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

762 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now