Solved

a smart alogorithm needed

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

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…
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 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…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

920 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

15 Experts available now in Live!

Get 1:1 Help Now