+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: fibonacci ***Time limit exceeded*** (/thread-14312.html)
Pages:
1
2
fibonacci ***Time limit exceeded*** - frequency - Nov-24-2018
def fib(number):
if number==0:
return 0
elif number==1:
return 1
else:
return fib(number-1)+fib(number-2)
n=int(input())
while n!="END" and n>0:
print (fib(n))
n=int(input())With this code i can show the N fibonacci number given. But my code is not accepted because of this***Time limit exceeded***. Any ideas?
RE: fibonacci ***Time limit exceeded*** - ichabod801 - Nov-24-2018
You are making the same calculations over and over again. Say you try fib(5). That's fib(4) + fib(3). But those are fib(3) + fib(2) + fib(2) + fib(1). So far you've called fib(3) and fib(2) twice each. It would be faster to just generate the numbers until you have n of them. Now, if you have to pass multiple tests, I would save the numbers you calculate for the first test, so you don't have to calculate them again.
RE: fibonacci ***Time limit exceeded*** - frequency - Nov-24-2018
This is the list that they told me,to suppose that i have
F=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...]
RE: fibonacci ***Time limit exceeded*** - Gribouillis - Nov-24-2018
Ichabod801's suggestion is an example of dynamic programming. It is probably what you're supposed to do. Accessing
F[k] is much faster than calling fib(k). See this image extracted from wikipedia.
RE: fibonacci ***Time limit exceeded*** - ichabod801 - Nov-24-2018
(Nov-24-2018, 05:24 AM)frequency Wrote: This is the list that they told me,to suppose that i have
F=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...]
Right. So start with [1, 1], and keep adding the last two numbers together until you have n of them. Then return the last one.
RE: fibonacci ***Time limit exceeded*** - frequency - Nov-24-2018
So should i make a look to append the 1 last and 2 last number calculation on the last position,so i can call the item after?
RE: fibonacci ***Time limit exceeded*** - ichabod801 - Nov-24-2018
I'm not sure I understood your question, but you would start with [1, 1]. Add the last two and append it, to get [1, 1, 2]. Add the last two and append it, to get [1, 1, 2, 3]. Keep going until you have n numbers, and return the last one.
RE: fibonacci ***Time limit exceeded*** - frequency - Nov-24-2018
So i made this
f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
for i in range (99999):
f.append(f[-1]+f[-2])
user_input=input()
while user_input!="END":
user_input=int(user_input)
print (f[user_input-1])
user_input=input()9999 in range because it will test maximum 9999 digit number.On idle it works but on my submittion page,it will cause a MemoryError.
RE: fibonacci ***Time limit exceeded*** - ichabod801 - Nov-24-2018
First of all, you are still doing too much calculation. You only need to calculate until you have as many numbers as requested.
Second of all, you have 5 nines in your range, not 4. If that doesn't fix the problem, just keep track of the last two numbers, and the count of which number you're on.
RE: fibonacci ***Time limit exceeded*** - frequency - Nov-24-2018
f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
for i in range (9999):
f.append(f[-1]+f[-2])
user_input=input()
while user_input!="END":
user_input=int(user_input)
print (f[user_input-1])
user_input=input()I actually removed the wrongfuly placed 9 there. Got it working