Radeen10-_

Find the nearest Fibonacci Number Using Two Methods

Aug 1st, 2021 (edited)
331
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Given a positive integer (n) find the nearest fibonacci number to (n).
  2. # If there are more than one fibonacci with equal distance to the given number return the smallest one.
  3.  
  4.  
  5. # first procedure is an unoptimized and unique solution and the second one is an optimized and general solution,
  6.  
  7.  
  8. def nearest_fibonacci(number):
  9.     if number<=1:
  10.         return number
  11.     else:
  12.         return nearest_fibonacci(number-1)+nearest_fibonacci(number-2)
  13. #store residual of given number and fibonacci number
  14. residual=[]
  15. #store fibonacci number
  16. #we will iterate through the list of fibonacci number and return the residual of each element with given number.
  17. #the minimum residual number with fibonacci number will be the required nearest fibonacci term.
  18. #If the nearest fibonacci is equal to the given number, it will iterate and give the next nearest one
  19. fib_list=[]
  20. number=int(input(""))
  21. for i in range(number):
  22.     x=nearest_fibonacci(i+1)
  23.     fib_list.append(x)
  24.     residual.append(abs((x+1)-number))
  25.     ans=abs(x-number)
  26. tuples=tuple(zip(fib_list,residual))
  27. tuples=list(tuples)
  28. print(fib_list,residual)
  29. x=min(tuples,key=lambda t:t[1])
  30. print(x[0])
  31.  
  32.  
  33. #optimized solution
  34.  
  35. def nearest_fibonacci(number):
  36.     # Base Case
  37.     if (number <=1):
  38.         return number
  39.     # Initialize the first & second
  40.     n1= 0
  41.     n2 = 1
  42.  
  43.     # Store the third term
  44.     nth=n1+n2
  45.     # Iterate until the third term
  46.     while (nth <= number):
  47.         # Update the first
  48.         n1=n2
  49.  
  50.         # Update the second
  51.         n2 = nth
  52.  
  53.         # Update the third
  54.         nth = n1+n2
  55.  
  56.     # Store the Fibonacci number
  57.     # having smaller difference with N
  58.     if (number==n2)or(number==nth):
  59.         return None
  60.     elif (abs(nth - number) >=
  61.             abs(n2 - number)):
  62.         nearest_number = n2
  63.     else:
  64.         nearest_number = nth
  65.  
  66.     # Print the result
  67.     return nearest_number
RAW Paste Data