当前位置：首页 > article >正文

python-SZ斐波那契数列/更相减损数

article 2024/11/15 8:09:20

一：SZ斐波那契数列
题目描述
你应该很熟悉斐波那契数列，不是吗？现在小理不知在哪里搞了个山寨版斐波拉契数列，如下公式：
F(n)=
{
$\ \ \ \ \ \ \ \ \ \ \ \ $ a,( n=1)
$\ \ \ \ \ \ \ \ \ \ \ \ $ b,( n=2)
$\ \ \ \ \ \ \ \ \ \ \ \ $ F(n−1)+F(n−2),(n>2并且n是奇数)
$\ \ \ \ \ \ \ \ \ \ \ \ $ F(n−1)+F(n−2)+F(n−3)(n>2并且n是偶数)
}
这里 a 和 b 是定值，现给出 a，b 和 n，你的任务是计算 F(n)。
输入格式
输入共 T+1 行。
第一行有一个正整数 T，表示测试实例的个数。
接下来 TT行，每行一个测试实例，每个测试实例包括三个正整数 a，b 和 n。
输出格式
对于每个测试实例，输出一行包含一个正整数 F(n)。
样例输入输出
样例输入
2
1 2 3
1 3 6
样例输出
3
24
数据范围
对于 100% 的数据，保证T≤10,a,b≤10,n≤30。
来源/分类（难度系数：二星）
模拟

完整代码展示：
def F(a,b,n):
list_1=[a,b,a+b]
begin=3
while begin<n+1:
if (begin+1)%2==0: list_1.append(list_1[-1]+list_1[-2]+list_1[-3])
elif (begin+1)%2==1:
list_1.append(list_1[-1]+list_1[-2])
begin+=1
return list_1[n-1]
m=int(input())
list_2=[]
for i in range(m):
list_3=list(map(int,input().split()))
list_2.append(list_3)
for i in range(0,len(list_2)):
print(F(list_2[i][0],list_2[i][1],list_2[i][2]))

def F(a,b,n):
    list_1=[a,b,a+b]
    begin=3
    while begin<n+1:
        if (begin+1)%2==0:
            list_1.append(list_1[-1]+list_1[-2]+list_1[-3])
        elif (begin+1)%2==1:
            list_1.append(list_1[-1]+list_1[-2])
        begin+=1
    return list_1[n-1]
m=int(input())
list_2=[]
for i in range(m):
    list_3=list(map(int,input().split()))
    list_2.append(list_3)
for i in range(0,len(list_2)):
    print(F(list_2[i][0],list_2[i][1],list_2[i][2]))

代码解释：
“def F(a,b,n):
list_1=[a,b,a+b]
begin=3
while begin<n+1:
if (begin+1)%2==0:
list_1.append(list_1[-1]+list_1[-2]+list_1[-3])
elif (begin+1)%2==1:
list_1.append(list_1[-1]+list_1[-2])
begin+=1
return list_1[n-1] ”，按照题意自定义一个函数F(),传递三个形参a,b,n,即斐波那契函数的第1项a,2项b和所求项n。（建立一个空列表list_1,将a,b,a+b分别作为list_1的第1，2，3项。令begin为循环密码子，当begin<n+1时：如果begin+1能被2整除，则将list_1后三项和添加进list_1末尾，否则将list_1后两项添加进list_1末尾。每循环一次，begin+1，直至begin==n+1,跳出整个while循环，最终返回list_1的末尾元素值）。
“m=int(input()) ”，导入用户输入的测试实例的个数m。
“list_2=[]
for i in range(m):
list_3=list(map(int,input().split()))
list_2.append(list_3) ”，建立一个空列表list_2,循环m次：导入用户输入的a,b,n，并将其储存在列表list_3中，接着将list_3添加进list_2中。
“for i in range(0,len(list_2)):
print(F(list_2[i][0],list_2[i][1],list_2[i][2])) ”，遍历list_2中的元素，将list_2[i][0]~list_2[i][2]作为实参传递进F()函数，并打印F（）函数返回值。

运行效果展示:

二：更相减损数:
题目描述
利用更相减损术求两个整数的最大公约数，即每次将较大的数变成大数减去小数的值。
输入格式
输入两个正整数 m , n 。
输出格式
输出一个整数。
样例输入输出
样例输入
4 6
样例输出
2
数据范围
对于 100% 的数据，保证 1≤m,n≤106 。
来源/分类（难度系数：二星）
递归最大公约数数学

完整代码展示：

x,y=map(int,input().split())
if x > y:
x,y=y,x
for fac in range(x,0,-1):
if x % fac == 0 and y % fac == 0 :
print('{}'.format(fac))
break

x,y=map(int,input().split())
if x > y:
    x,y=y,x
for fac in range(x,0,-1):
    if x % fac == 0 and y % fac == 0 :
        print('{}'.format(fac))
        break

代码解释：
“x,y=map(int,input().split())
if x > y:
x,y=y,x ”,导入用户输入的两个正整数x,y,并判断x,y的·大小关系：如果x,y,则将x,y交换值（即保证x为x,y中最小值）。
“for fac in range(x,0,-1):
if x % fac == 0 and y % fac == 0 :
print('{}'.format(fac))
break ”，依次遍历x~1的所有数fac，并判断x，y是否同时能被fac整除,如果是：则打印fac,终止循环。

运行效果展示：