int fibArray[INTEGER_MAX_VALUE] = {0};
int fibonacci (int n) {
if (n <= 0) {
return 0;
} else if ( n > 0 && fibArray[n] != 0) {
return fibArray[n];
} else {
if (n == 1) return (fibArray[n] = 1);
return (fibArray[n] = fibonacci(n - 1) + fibonacci(n-2));
}
}
int findNearestFibLessthanK(int k) {
int upper = INTEGER_MAX_VALUE;
int lower = 0;
int incr = 1;
int fibLower = 0;
while (lower < upper) {
fibLower = fibonacci(lower + incr);
if (fibLower < k) {
incr <<= 1;
} else if (fibLower == k) {
return fibLower;
} else {
upper = incr;
lower += incr >> 1;
incr = 1;
}
}
return fibLower;
}
Thanks,
Immanuel
On Tue, May 24, 2011 at 8:09 PM, Aakash Johari <[email protected]>wrote:
> search OEIS.. and tell if you find something interesting :)
>
>
> On Tue, May 24, 2011 at 7:37 AM, Piyush Sinha <[email protected]>wrote:
>
>> U r using he same approach which I mentioned it before...I knew about
>> this approach but it sounded to me too naive solution...so I was
>> thinking whether there exists any shortcurt method/mathematical
>> formulae for it or not..
>>
>> On 5/24/11, bittu <[email protected]> wrote:
>> > @all geeks
>> >
>> > I have already posted it 2-3 forums..here let me post it again its
>> > O(n) but the basic idea is clear if got the problem stmt correct then
>> > we have to find out the largest Fibonacci number that is small then
>> > given number n so say if n=10 then should be 8
>> > for n=13 i=8
>> > n=14 i=13 similarly for all n>13 & n <21 i will 13 & so on i don't why
>> > so confusion ?? It Will Cover All Test Cases
>> >
>> > #include<stdio.h>
>> >
>> > int fib(int n)
>> > {
>> >
>> > int final=0,i,c,a=0,b=1;
>> >
>> > for(i=2;i<n;i++)
>> > {
>> > c=a+b;
>> > a=b;
>> > b=c;
>> > if(c<n)
>> > final=c;
>> > }
>> >
>> > return final;
>> >
>> > }
>> >
>> > int main()
>> > {
>> > int n=14;
>> > printf( " %d ", fib(n));
>> >
>> > }
>> >
>> > TC O(n)
>> > SC O(1)
>> > Run Here https://ideone.com/aCli7
>> >
>> >
>> >
>> > Optimization: To get the answer in O(logn) we can use matrix
>> > representation of Fibonacci number check wiki..& if you wants O(logn)
>> > then i can also post that..I hope m clear ..There are already 6 Way
>> > Known to me to find nth Fibonacci Number
>> >
>> > only thing necessary is that optmization .. Correct me if anything
>> > wrong ???
>> >
>> > Thanks
>> > Shashank>>" the Best Way To Escape From The problem is To Solve It"
>> > CSE,BIT Mesra
>> > Reach Me +91-9739002481
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to [email protected].
>> > To unsubscribe from this group, send email to
>> > [email protected].
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/profile.php?id=100000655377926 *
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> -Aakash Johari
> (IIIT Allahabad)
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
