[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Help With Recursion

Posted on 2003-11-12
9
Medium Priority
?
406 Views
Last Modified: 2010-04-02
I'm trying to recursivly search a vector of objects for the smallest value of a field.
It should work something like this.... Say you have 8 elements

          12345678      // not 2 or 1 split vector
         1234  8765     // not 2 or 1 split vector 1234 and 5678
       12  43  87  56   // min of 1&2 , min of 3&4, min of 5&6, min of 7&8
         1 3      7  5     .....
           1         5
                1

I have these functions
FindMid(string a, string b) // checks for the smallest value (I checked this function it works)
vector<Associate> split(vector<Associate> &a) (Will split a vector that looks like 012345678 into 01234 and 8765
string MinimumObject(vector<Associate> &Members, string key)

Code I'm Trying
****************************************************************************
string MinimumObject(vector<Associate> &Members, string key, int mode)
{
      vector<Associate> Members2;
      
      if (Members.size() == 0)
            return "NULL";

      if (Members.size() == 1)
      {
           return Members[0].getKey(key);
      }

      if (Members.size() == 2)
      {
           return FindMin(Members[0].getKey(key), Members[1].getKey(key));
      }

      else
      {
           Members2 = split(Members); // Split Members vector
           return FindMin(MinimumObject(Members, key, mode), MinimumObject(Members2, key, mode));      
      }
}

string FindMin(string a, string b)
{
     bool first = (a<=b);
    if (first)
    {
      cout<<a<<" is less than "<<b<<endl;
      return a;
   }
   else
   {
                cout<<b<<" is less than "<<a<<endl;
      return b;
   }
}

vector<Associate> split(vector<Associate> &a)
{
       //define local variables
       vector<Associate> b;
       int size, count;

       Associate temp;

       size=a.size();
       size = size -1;
       count=size;
       
      size=size/2;

       while (count!=size){
         temp=a[count];
         a.pop_back();
         b.push_back(temp);
         count = count - 1;
       }
       return b;
}//end split

****************************************************************************

Something is wrong though becuase when I output what the recursive function MinimumObject returns by typing
string hold;
hold = Senate_Class.MinimumObject(Senate_Class.Members, "phone", 0);
cout<<hold<<endl;

I get a value that is not the smallest

however

the function calls FindMin several times and the last comparison that function makes is always the minimum.

So bottom line for some reason the FindMin function can locate the minimum value in the vector but the recusive function does not return it..




0
Comment
Question by:RiMZ
[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
  • 3
  • 2
  • +1
9 Comments
 
LVL 6

Expert Comment

by:GloomyFriar
ID: 9730916
Could you show all FindMin output?
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9730929
You say "the last comparison that function makes is always the minimum". There should be a sequence of comparisons with the minimum, right? 3 comparisons with 1 if there were 8 entries initially (the log base 2 of the size of the original array, give or take).

Are you sure the returned value is not the smallest? That is you are comparing strings so if a string contains non-digits (or if the lengths of the keys are not identical) the comparison may appear to sort in an odd way. You may want to print hold inside of quotes as in cout << "\"" << hold << "\"" << endl so you can see if there are any spaces at the front of the string.

All of this indicates that I don't see anything immeadiately and cannot run your code so there is noting I can do but suggest tests to you.

Good luck,
-bcl
PS: Mode is never used in MinimumObject (or at least the version we were shown). IThere are several studies that corelate unused variables/parameters with errors in code (it is not an error in and of itself).
0
 

Author Comment

by:RiMZ
ID: 9730956
the output created by FindMin is....


(202) 224-2441 is less than (202) 224-3441
(202) 224-2441 is less than (202) 224-5852
(202) 224-2644 is less than (202) 224-4343
(202) 224-2644 is less than (202) 224-3954
(202) 224-2441 is less than (202) 224-2644
(202) 224-2921 is less than (202) 224-3521
(202) 224-2921 is less than (202) 224-4451
(202) 224-2531 is less than (202) 224-5641
(202) 224-2531 is less than (202) 224-5054
(202) 224-2531 is less than (202) 224-2921
(202) 224-2441 is less than (202) 224-2523
(202) 224-5047 is less than (202) 224-5521
(202) 224-5042 is less than (202) 224-5721
(202) 224-4623 is less than (202) 224-6521
(202) 224-3553 is less than (202) 224-4623
(202) 224-3553 is less than (202) 224-5042
(202) 224-5444 is less than (202) 224-5623
(202) 224-2651 is less than (202) 224-5444
(202) 224-4024 is less than (202) 224-5941
(202) 224-4944 is less than (202) 224-6361
(202) 224-4024 is less than (202) 224-4944
(202) 224-2651 is less than (202) 224-4024
(202) 224-2651 is less than (202) 224-3553
(202) 224-2441 is less than (202) 224-2651
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:RiMZ
ID: 9730976
In main I code this...

      string hold;
      hold = Senate_Class.MinimumObject(Senate_Class.Members, "phone", 0);
      cout<<":"<<hold<<":"<<endl;

This couts this

(202) 224-4944 is less than (202) 224-6361
:(202) 224-4944:


why is (202) 224-4944 coming up instead of (202) 224-2441
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9731033
You are testing your find min routine BEFORE your assignment to hold?

You only show one line of comparison (an odd line of comparison) before you show the return value. Your MinimumObject is DESTRUCTIVE and if you don't make a COPY of the input data that data will be destroyed (or rather reduced to a two element array: bet those two phone numbers are the first numbers in your original list).

-bcl
0
 
LVL 9

Accepted Solution

by:
_ys_ earned 2000 total points
ID: 9731050
> string MinimumObject(vector<Associate> &Members, string key)
Try removing the pass-by-reference functionality.

The left and right code paths are likely _confused_:
> return FindMin(MinimumObject(Members, key, mode), MinimumObject(Members2, key, mode));
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9731064
Looking at the output, that seems to be the case. My suggestion: Change split so it takes three vectors, the original and references to the first and second half. Then take the original apart into the other two vecotrs.
Then in MinimumObject you have two vectors declared locally and make the call to split as:

split(Members, frontOfMembers, backOfMembers);

and then pass front and back into the recursive call.

If I haven't explained myself clearly, please feel free to follow up here.

-bcl
0
 

Author Comment

by:RiMZ
ID: 9731218
THANK F***IN U!!!!!!!!!!!!!!!!!!  LOL THANK YOU THANK YOU THANK YOU.

I JUST SPENT 7 HOURS STRIGHT TRYING TO FIGURE OUT WHAT WAS WRONG IT WAS THE "&"
0
 
LVL 9

Expert Comment

by:_ys_
ID: 9731269
7 hours ... world time zones are great.
0

Featured Post

[Webinar] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

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

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. …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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.

649 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