• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursive Mehtod problem

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Need to write a recursive method that will count the number of ones in a binary representation of a number that is entered from the keyboard. I can't figure out how to return my ones to check if they are right. Here is the code I hava so far:

Can anyone help me with this problem?
[ edited to remove long blank line in code -ds ]
[ January 12, 2003: Message edited by: Dirk Schreckmann ]
 
Ranch Hand
Posts: 2545
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Lynn:
My thought is:
When you enter a number from keyborad, unless it is 0, then it got to have at least one '1' in binary representation. To find out where is the hightest position of 1,
2^(n+1) > number >= 2^n, n is the position (starting from right, starting from 0)
Then let:
m = n-1,
use same formula to see if postion m has 1
2^(m+1) > number - 2^n >= 2^m,
then, let
k = m-1;
to find out next 1 in binary, recursivly.
Set a counter to keep track all the 1's.
 
John Lee
Ranch Hand
Posts: 2545
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Lynn Finley:

Therefore, I think your code is wrong. For instance, 8 = ..0001000, but just has one '1', but in your program, it returns 5.
[ edited to remove long blank line in code -ds ]
[ January 12, 2003: Message edited by: Dirk Schreckmann ]
 
Lynn Finley
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The reason my method is written that way is my assignment said to write a recursive method that returns the number of ones in the binary representation of N. Use the fact that this number equals the number of ones in the representation of N/2, plus 1, if N is odd.
I just can't figure out how to pass my variable one to the main method in order to check my work. is passing a variable to the main method even possible with out creating a constructor?
Thanks for your input..
 
John Lee
Ranch Hand
Posts: 2545
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In fact, you have pretty much got it. All you need to do is call countOnes() repeatly inside countOnes(). I made some change for you. See below.
 
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not considering whether the algorithm is correct...
The identifier (aka variable) ones is local to the countOnes method and so is not in scope to be used in the main method. Your countOnes method returns a value. Capture that return value by assigning it to a local variable within the main method.Making sense?
 
Yeah. What he said. Totally. Wait. What? Sorry, I was looking at this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic