Find the nearest Fibonacci Number Using Two Methods

# Given a positive integer (n) find the nearest fibonacci number to (n).
# If there are more than one fibonacci with equal distance to the given number return the smallest one.


# first procedure is an unoptimized and unique solution and the second one is an optimized and general solution,


def nearest_fibonacci(number):
    if number<=1:
        return number
    else:
        return nearest_fibonacci(number-1)+nearest_fibonacci(number-2)
#store residual of given number and fibonacci number
residual=[]
#store fibonacci number
#we will iterate through the list of fibonacci number and return the residual of each element with given number.
#the minimum residual number with fibonacci number will be the required nearest fibonacci term.
#If the nearest fibonacci is equal to the given number, it will iterate and give the next nearest one
fib_list=[]
number=int(input(""))
for i in range(number):
    x=nearest_fibonacci(i+1)
    fib_list.append(x)
    residual.append(abs((x+1)-number))
    ans=abs(x-number)
tuples=tuple(zip(fib_list,residual))
tuples=list(tuples)
print(fib_list,residual)
x=min(tuples,key=lambda t:t[1])
print(x[0])


#optimized solution

def nearest_fibonacci(number):
    # Base Case
    if (number <=1):
        return number
    # Initialize the first & second
    n1= 0
    n2 = 1

    # Store the third term
    nth=n1+n2
    # Iterate until the third term
    while (nth <= number):
        # Update the first
        n1=n2

        # Update the second
        n2 = nth

        # Update the third
        nth = n1+n2

    # Store the Fibonacci number
    # having smaller difference with N
    if (number==n2)or(number==nth):
        return None
    elif (abs(nth - number) >=
            abs(n2 - number)):
        nearest_number = n2
    else:
        nearest_number = nth

    # Print the result
    return nearest_number