On Wed, 2009-02-11 at 09:15 +0900, Li Chen wrote:
Hi all,
In order to study recursion, I want to change a decimal number into a
binary number based on the algorithm on website
http://www.trunix.org/programlama/cpp/fred/notes/cpp/misc/decimal2binary.html
But my codes don’t work. Any idea or optimization?
The main idea behind recursion is that we break a problem into a
representation of the same problem. In this case, we are taking a
number, n. We want the value of that n, modulo 2, + the binary value of
(n / 2).
Using that approach, for 4, we’d get:
(n%2) + ((n/2)%2) + ((n/2)/2)%2
which is “001” – the reverse of what we were wanting. However, if we
turn it around, we can say that the binary representation of n is
equivalent to:
the binary representation of (n/2) + (n modulo 2)
Or, if you will:
def decimal_to_binary(num = 0)
((num > 1) ? decimal_to_binary(num / 2) : “”) + (num % 2).to_s
end
No arrays needed, nor any reversing.
We could also have written it as:
def decimal_to_binary(num = 0)
if (num > 1) then
results = decimal_to_binary(num/2)
else
results = “”
end
results + (num % 2).to_s
end
So, were we to call it with 4, the following calls to decimal_to_binary
would happen:
decimal_to_binary(4) (which returns the next line + “0”)
decimal_to_binary(2) (which returns the next line + “0”)
decimal_to_binary(1) (which returns “1”)
or, if you will, “100”
I’m sure there’s probably ways to optimize my code even more, but it
works…
Matt