 # 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)
30. print(x)
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