Back to General discussions forum
Hi everyone,i think my algorithm is right and i can solve the example in the problem. However when i used it to slovethe problem, i got stuck.I think the reason is time complexity is too large. Any little hint to get me on right track would be appreciated :-).This is my python code.
def fib(num):
if num==0 or num==1:
return num
return int(fib(num-1))+int(fib(num-2))
result=[]
numInput=input()
for i in range(int(numInput)):
lineInput=input()
n=0
while int(lineInput)>int(fib(n)):
n=n+1
print(n,end=" ")
Your should optimize your fib() function. You can easy google how to calculate fibonacci fast.
To add another comment: While recursion seems like a natural way of solving the Fibonacci generation, it is actually horribly ineffective in your implementation:
Let's say we are some steps deep into your for loop and n=10. Then we call fib(10), which in turn calls fib(9) and fib(8), which in turn call fib(7), fib(6), fib(5) and fib(4) and so on, down to fib(1) and fib(0). Down there, we meet the dwarves who delved too greedily and too deep and return the 10th Fibonacci number.
That one is smaller than whatever our input is, so we increase n to 11 and then call fib(11). This in turn calls fib(10) and fib(9), which in turn calls... wait a second! We should have all those fib(10) and lower saved somewhere, but your program here calculates them all anew!
Thank you very much:-),i think i should not use recurision.It waste too much computation.
