here's an O(lgn) soln :
matrix form of fib :
http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
and then use the divide and conquer for calculating (A)^n in O(lgn).
Thanks
On Sun, Oct 21, 2012 at 7:10 PM, rahul sharma <rahul23111...@gmail.com>wrote:
> I have implemented this code below:-
> #include<stdio.h>
> int fibs(int);
> int fibb[9]={0};
> int fib(int n)
> {
> if ( n <= 1 )
> {
> fibb[1]=n;
> return n;
> }
>
> return fibs(n-1)+fibs(n-2);
>
>
> }
>
> int fibs(int n)
> {
>
> if( fibb[n]!=0)
> return fibb[n];
> int temp=fib(n);
> fibb[n]=temp;
> return temp;
>
>
> }
>
>
>
> int main ()
> {
> int n = 9;
>
> printf("%d", fib(n));
> for(int i=0;i<9;i++)
> printf("\n%d",fibb[i]);
> getchar();
> return 0;
> }
>
>
> but if i call for 9..then the lookup/fibb should contain upto 9 so that
> when i call for 11 it would take only two computaion..but my code storing
> in fibb upto 8 i.e the element for which we called its result is not
> getting stored in fibbonicci...so if i call for 9 it would store till
> fibb[8].....but it should store for 9 also.i am not able to get that
> statemnt...plz correct my code..
>
> On Sun, Oct 21, 2012 at 6:39 PM, rahul sharma <rahul23111...@gmail.com>wrote:
>
>> on wiki they are saying(in case of factorial) that once function called
>> with 5!..then if we call with 6! then only one iteration needed....i just
>> wana confirm that both these calls occur simultaneously..i mean like
>>
>> fact(5);
>> ...
>> ...
>> ...
>> fact(6)
>>
>>
>> or
>> fact (5).....stop execution.....add statemet
>> fact(6)
>>
>> if we do like this this will delete old fact(5) as emmory has been
>> deleted after execution..am i ryt??or there is something in memorization
>> that preserve the memory
>>
>>
>> On Sun, Oct 21, 2012 at 6:32 PM, rahul sharma <rahul23111...@gmail.com>wrote:
>>
>>> sachin
>>> i have no idea about floowong
>>>
>>> Iterator<int, int> it = optimizationMap.find(n);
>>>
>>> can you provide me a clear definition
>>>
>>> On Sun, Oct 21, 2012 at 6:30 PM, rahul sharma
>>> <rahul23111...@gmail.com>wrote:
>>>
>>>> yes,,,,i have read somehwr that we can save the already calculated
>>>> values..thtas wat i did.....now after ur sol i came to know abput
>>>> memorization..thnx
>>>>
>>>>
>>>> On Sun, Oct 21, 2012 at 5:58 PM, Sachin Maheshwari <
>>>> sachin.maheshw...@gmail.com> wrote:
>>>>
>>>>> Rahul,
>>>>> Your solution in principle is doing a similar work. If you look
>>>>> closely you are using fibb array to do memoization of already calculated
>>>>> values.
>>>>>
>>>>> Regards,
>>>>> Sachin
>>>>>
>>>>> On Sun, Oct 21, 2012 at 5:47 PM, rahul sharma <rahul23111...@gmail.com
>>>>> > wrote:
>>>>>
>>>>>> I came up with follwoing solution...plz comment.....
>>>>>> #include<stdio.h>
>>>>>> int fib(int n,int fibb[])
>>>>>> {
>>>>>> if ( n <= 1 )
>>>>>> {
>>>>>> fibb[1]=n;
>>>>>> return n;
>>>>>> }
>>>>>> fib(n-1,fibb);
>>>>>> fibb[n]=fibb[n-1]+fibb[n-2];
>>>>>> return fibb[n];
>>>>>> }
>>>>>>
>>>>>> int main ()
>>>>>> {
>>>>>> int n = 9;int fibb[9];
>>>>>> fibb[0]=0;
>>>>>> printf("%d", fib(n,fibb));
>>>>>> getchar();
>>>>>> return 0;
>>>>>> }
>>>>>>
>>>>>> plz comment
>>>>>> On Sun, Oct 21, 2012 at 5:16 PM, rahul sharma <
>>>>>> rahul23111...@gmail.com> wrote:
>>>>>>
>>>>>>> #include<stdio.h>
>>>>>>> int fib(int n)
>>>>>>> {
>>>>>>> if ( n <= 1 )
>>>>>>> return n;
>>>>>>> return fib(n-1) + fib(n-2);
>>>>>>> }
>>>>>>>
>>>>>>> How can we reduce no of computations with the above
>>>>>>> code....(iterative solution not allowed).
>>>>>>>
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Regards,
>>>>> Sachin Maheshwari
>>>>> Cell phone: +91.7259917298
>>>>>
>>>>> "If we admit that human life can be ruled by reason; the possibility
>>>>> of life is destroyed." - Alexander Supertramp
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
