The Artima Developer Community
Sponsored Link

Java Answers Forum
Pseudocode help

5 replies on 1 page. Most recent reply: Nov 26, 2003 11:22 AM by Matt Gerrans

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 5 replies on 1 page
Kieran

Posts: 3
Nickname: gould
Registered: Nov, 2003

Pseudocode help Posted: Nov 25, 2003 5:33 AM
Reply to this message Reply
Advertisement
Hi, i have just started a degree in computing and am struggling on a particular section, that being pseudocode -

On my revision sheet i have the following code -

function binarySearch(a[], lo, hi, x)
found = false
while (lo <= hi)
mid = (lo + hi ) / 2 // find midpoint
if (a[mid] < x) // too low
lo = mid + 1
else if (a[mid] > x) // too high
hi = mid - 1
else
return mid
end if
end while
return -1
end function binarySearch

It asks me too modify the function so it implements a binary search recursively rather than iteratively.

Does anyone have any ideas on how to do this? or could anyone recommend a site or alternative forum that may help?

Thanks in advance


Ernie Douglas

Posts: 18
Nickname: y2j
Registered: Nov, 2002

Re: Pseudocode help Posted: Nov 25, 2003 7:11 AM
Reply to this message Reply
this might help you

import java.awt.*;
import javax.swing.*;
 
 
public class BinaryA
{
    
    public static void main( String args[] )
    {
        String    message;   //stores the binary number
        String    output;    //stores message to print out
        int       num;       //stores decimal number to convert
        int       numvalue;  //stores BACKUP copy of num
        boolean   valid;     //boolean FLAG to check if number is 0 - 255.
        
        //initialise String values
        message = "";
        output = "";
        
        //initialise FLAG
        valid = true;
        
        //DECIMAL number to convert to BINARY
        num = 65;
        numvalue = num;
        
        //check if num is in the range 0 - 255 inclusive.
        if ((num > 255) || (num < 0)) 
        {
          message = message + "Invalid value for num";
          valid = false;
        }
        
        
        //check if the bit for 128 needs to be set
         if ((num >= 128) && (valid = true))
             {
               message = message + "1";
               num = num - 128;
             }
         else
             {
               message = message + "0";
             }
         
         //check if the bit for 64 needs to be set
         if ((num >= 64) && (valid = true))
             {
               message = message + "1";
               num = num - 64;
             }
         else
             {
               message = message + "0";
             }
 
         //check if the bit for 32 needs to be set
         if ((num >= 32) && (valid = true))
             {
               message = message + "1";
               num = num - 32;
             }
         else
             {
               message = message + "0";
             }
 
         //check if the bit for 16 needs to be set
         if ((num >= 16) && (valid = true))
             {
               message = message + "1";
               num = num - 16;
             }
         else
             {
               message = message + "0";
             }
 
         //check if the bit for 8 needs to be set
         if ((num >= 8) && (valid = true))
             {
               message = message + "1";
               num = num - 8;
             }
         else
             {
               message = message + "0";
             }
 
         //check if the bit for 4 needs to be set
         if ((num >= 4) && (valid = true))
             {
               message = message + "1";
               num = num - 4;
             }
         else
             {
               message = message + "0";
             }
 
         //check if the bit for 2 needs to be set
         if ((num >= 2) && (valid = true))
             {
               message = message + "1";
               num = num - 2;
             }
         else
             {
               message = message + "0";
             }
 
         //check if the bit for 1 needs to be set
         if ((num >= 1) && (valid = true))
             {
               message = message + "1";
               num = num - 1;
             }
         else
             {
               message = message + "0";
             }
 
    //Build the output message to be printed
    output = "Binary value of " + numvalue + " is: " + message;
    
    //print out the message to screen
    JOptionPane.showMessageDialog(null, output, "Binary Value", JOptionPane.INFORMATION_MESSAGE);
    
    //terminate program
    System.exit(0); 
    } //end of main
 
 
}//end of class

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Pseudocode help Posted: Nov 25, 2003 12:24 PM
Reply to this message Reply
> Does anyone have any ideas on how to do this?

Please read this handy primer:
http://www.catb.org/~esr/faqs/smart-questions.html

What is the purpose of the "found" variable in your original post?
It doesn't seem to be used anywhere, so this pseudocode would appear
to be equivalent:
function binarySearch(a[], lo, hi, x)
   while (lo <= hi) 
      mid = (lo + hi ) / 2
      if (a[mid] < x)
         lo = mid + 1
      else if (a[mid] > x)
         hi = mid - 1
      else
         return mid
      end if
   end while
   return -1
end function binarySearch

Making it recursive would just be a matter of eliminating the while-loop
and instead passing a new search range back into the same function, like so:
function recursiveBinarySearch(a[], lo, hi, x)
   if (lo <= hi) 
      mid = (lo + hi ) / 2
      if (a[mid] < x)
         return recursiveBinarySearch(a, mid+1, hi, x)
      else if (a[mid] > x)
         return recursiveBinarySearch(a, lo, mid-1, x)
      else
         return mid
      end if
   end if
   return -1
end function recursiveBinarySearch

Kieran

Posts: 3
Nickname: gould
Registered: Nov, 2003

Re: Pseudocode help Posted: Nov 26, 2003 1:37 AM
Reply to this message Reply
Hi, thanks for the 2 replies they were both a big help. On the subject of the found variable im not sure myself of its function...on the sheet it says "If the data value is found, the function returns its position. If the the data value is not found, -1 is returned."

Im not sure if that has any relavance to your query or if im being blindingly stupid...probably the latter but i do find this kind of work very hard as i have just started and have had no previous experience in programing of any kind.

thanks again for your help.

Kieran

Posts: 3
Nickname: gould
Registered: Nov, 2003

Re: Pseudocode help Posted: Nov 26, 2003 2:09 AM
Reply to this message Reply
Just read the prima guide you recommended and I can see that this forum was probably not the best place to post my question, I am sorry if i have caused any annoyance with my query and I am sincerly grateful for the help you have already given me.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Pseudocode help Posted: Nov 26, 2003 11:22 AM
Reply to this message Reply
With regard to your "Does anyone have any ideas on how to do this?" question, I was referring to the Prune pointless Queries (http://www.catb.org/~esr/faqs/smart-questions.html#prune) topic. Of course, the Don't post homework questions topic probably also applies, but that is not peculiar to this forum.

Flat View: This topic has 5 replies on 1 page
Topic: ABOUT J2EE Previous Topic   Next Topic Topic: Java & RegEx

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use