Python Forum
fibonacci ***Time limit exceeded***
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
fibonacci ***Time limit exceeded***
#11
Here's how I would have done it:

f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
while True:
    user_input = input()
    if user_input == 'END':
        break
    user_input = int(user_input)
    while len(f) < user_input:
        f.append(sum(f[-2:])
    print (f[user_input - 1])
That only calculates what you need when you need it.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#12
Your code has an error at the last print,i will check it further as soon as i go home

optimized the code a bit for my standards
f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
user_input = input()
while user_input !='END':
    user_input = int(user_input)
    while type(user_input)==int:
        while len(f) < user_input:
          f.append(sum(f[-2:]))
        print (f[user_input - 1])
        user_input=input()
Reply
#13
Your code will throw an exception on line 4 when they enter 'END'.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#14
So normally, for generating infinite sequences, you'd use a generator:
>>> def find_fibs():
...   last_two = (1, 1)
...   yield 1
...   yield 1
...   while True:
...     new_num = sum(last_two)
...     yield new_num
...     last_two = (last_two[1], new_num)
...
>>> fibs = find_fibs()
>>> for _ in range(10):
...   print(next(fibs))
...
1
1
2
3
5
8
13
21
34
55
But, as ichabod801 mentioned, if the point is that you'll be finding similar numbers repeatedly, you want to keep track of what the old numbers were, and only calculate new numbers if needed. Similar to this:
>>> def fibs(num, results=[1, 1]):
...   while num > len(results):
...     print("**generating new fib**")
...     results.append(results[-1] + results[-2])
...   return results[:num]
...
>>> fibs(2)
[1, 1]
>>> fibs(5)
**generating new fib**
**generating new fib**
**generating new fib**
[1, 1, 2, 3, 5]
>>> fibs(3)
[1, 1, 2]
>>> fibs(10)
**generating new fib**
**generating new fib**
**generating new fib**
**generating new fib**
**generating new fib**
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> fibs(6)
[1, 1, 2, 3, 5, 8]
The difference being a memory issue. If you want to generate the 500 millionth fibonacci number, the generator will give you what that number is, while keeping track of what every previous number is might use up all your memory before giving an answer, which would throw an error instead of getting a result.
Reply
#15
(Nov-24-2018, 02:49 AM)frequency Wrote:
def fib(number): 
  if number==0: 
      return 0
  elif number==1: 
      return 1
  else: 
    return fib(number-1)+fib(number-2)
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?

It seems to me that you can't have Fibonacci without recursive solution (at least in school / university) :-). This is somehow considered 'appropriate' way of learning recursion. Recursion can be helpful but it's memory hungry and it's not very well suited for Python. However, if you absolutely must use recursion and the number is not very large (so that Python recursion depth is not reached) you can take advantage of memoization and fit nicely into time limit.

import time
start_time = time.time()

def fibonacci(n, d):
    """
    Calculate n-th Fibonacci number using recursion with memoization.
    """
    
    if n in d:
        return d[n]
    
    else:
        stacked = fibonacci(n - 1, d) + fibonacci(n-2, d)
        d[n] = stacked
        return stacked
    
d = {1: 1, 2: 1}
print(fibonacci(2967, d))   # max value

print(f'time: {time.time() - start_time} seconds')

5210070734289118676556659504172397216509110684811035423298698167608113070
8128298569412879157715400318322090085906471884461561425531080766704209506
4311080110751154013406591832134966583308143574796700315698273930037147293
5213339912864755255418769562822777951268745753053628637531122736216232998
2608605087960788184953369249606869764593142447603256366652678730040462508
2678511875453604344284964368071643450341691576353630336917618689891862786
8101774706249610049853926508865933137189372424857166415874230698017498326
2019706158006070552174196824071976060605681771809636978040161730581446676
084619548504486422369069065085516578

time: 0.005608797073364258 seconds
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#16
You don't need recursion for Fibonacci numbers
>>> def fib(n):
...     if n == 0:
...         return 0
...     a, b = 0, 1
...     for i in range(n-1):
...         a, b = b, a + b
...     return b
... 
>>> fib(2967)
5210070734289118...
I think Fibonacci numbers is a terrible example because one finds it in many many language tutorials and it is useless and it doesn't teach you anything. Good examples are
  • The towers of Hanoi for recursion.
  • The edit distance for dynamic programming.
Reply
#17
(Nov-28-2018, 09:43 AM)Gribouillis Wrote: You don't need recursion for Fibonacci numbers. I think Fibonacci numbers is a terrible example /../

I agree with you totally.

Still it's reality of life that lot (majority?) of students have submit calculation of fibonacci numbers using recursion in order to pass the term.
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#18
Quote:Still it's reality of life that lot (majority?) of students have submit calculation of fibonacci numbers using recursion
The actual lesson of the Fibonacci example is that recursion can be the worst idea on a problem. That's what need to be taught.
Reply
#19
Thank you for your time.i really apreciate your efford! I tweaked it a bit to make it fully functional
def fib(n):
  if n == 0:
    return 0
  a, b = 0, 1
  for i in range(n-1):
    a, b = b, a + b
  return b

user_input=input()
while user_input!="END":
  user_input=int(user_input)
  print (fib(user_input))
  user_input=input()
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Fibonacci Yasunaga 7 2,863 May-16-2021, 02:36 PM
Last Post: csr
  Assign a value if datetime is in between a particular time limit klllmmm 2 2,699 Jan-02-2021, 07:00 AM
Last Post: klllmmm
  Time Limit Exceeded error loves 5 3,077 Dec-03-2020, 07:15 AM
Last Post: Sofia_Grace
Bug maximum recursion depth exceeded while calling a Python object error in python3 Prezess 4 3,689 Aug-02-2020, 02:21 PM
Last Post: deanhystad
  RecursionError: maximum recursion depth exceeded in comparison ? leoahum 11 12,874 Mar-18-2019, 01:53 PM
Last Post: leoahum
  'Time Limit Exceeded' Problem bkpee3 2 5,377 Nov-14-2018, 03:51 AM
Last Post: bkpee3
  If conditions with time limit unknowntothem 4 3,010 Nov-09-2018, 08:59 PM
Last Post: nilamo
  Fibonacci sequence Darbandiman123 2 2,667 Sep-26-2018, 02:32 PM
Last Post: Darbandiman123
  Help debug my fibonacci implementation dineshpabbi10 6 3,921 May-16-2018, 12:12 PM
Last Post: dineshpabbi10
  maximum recursion depth exceeded saba_keon 3 7,323 Apr-08-2018, 07:30 AM
Last Post: Gribouillis

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020