Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursive Mehtod problem

 
Lynn Finley
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • 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 ]
 
John Lee
Ranch Hand
Posts: 2545
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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
  • 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.
 
Dirk Schreckmann
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
  • 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?
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic