第 10 题

x = int(input())
if f(x) == g(x):
    print(True)
else:
    print(False)

主程序读入x，依次调用f(x)、g(x)，比较两个返回值；相等时输出True，否则输出False。先看f如何求值，再看g的更新过程。

def f(n):
    if n <= 2:
        return n
    return f(n-1) + f(n-2)

对正整数n，出口给出f(1)=1、f(2)=2；n>2时满足f(n)=f(n-1)+f(n-2)。因此各项依次为1、2、3、5、8、……。每次非出口调用都要计算两个子问题，且相同参数的子问题会被重复计算。

def g(n):
    a, b = 1, 2
    for i in range(3, n+1):
        a, b = b, a + b
    if n >=2:
        return b
    else:
        return a

a、b初值为1、2。循环中同时赋值使用更新前的值，使a变为原来的b，b变为原来两数之和，因而将相邻两项向后推进一项。第i轮结束后，a、b分别保存第i-1项和第i项。n≥3时循环推进至第n项并返回b；n=2时不进入循环，返回初值b=2；n=1时返回a=1。