@Hemesh : dats would be an over kill , you are converting O(n) solution to
a subset sum problem which NP
On Tue, Mar 20, 2012 at 7:35 PM, Hemesh Singh hemesh.mn...@gmail.comwrote:
Isn't it a standard subset sum problem? You can generate the Fibonacci
numbers and put them in an array. Now just
Isn't it a standard subset sum problem? You can generate the Fibonacci
numbers and put them in an array. Now just apply the standard algorithm to
find that which Fibonacci numbers add up to make the given sum. Please
correct me if I am wrong.
On Mon, Mar 19, 2012 at 8:58 PM, atul anand
Thanks.
I noticed this too. If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then my original code would have been
right. But the example isn't done this way.
I fixed the code to match the example the evening of the 18th
(Eastern time), but I guess the change is
@gene it does show your updated code.
@atul from the given input it seems different from Fibonacci encoding.
On Mon, Mar 19, 2012 at 5:32 PM, Gene gene.ress...@gmail.com wrote:
Thanks.
I noticed this too. If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then
@Gene : yeah i skipped ur updated code...its dere
@shady : it is similar to fib encoding...you just need to reverse the
output from gene code and append '1' at the end...
while decoding it ...this extra '1' is not considered..
i am nt sure but maybe the reason for adding '1' at the end is to
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
