递推数列

[编程题]递推数列

热度指数：25728 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。求第k个数对10000的模。

输入描述:

输入包括5个整数：a0、a1、p、q、k。

输出描述:

第k个数a(k)对10000的模。

示例1

输入

20 1 1 14 5

输出

算法知识视频讲解

Python

gcoffer

python

while True:
    try:
        a0,a1,p,q,k=map(int,input().split())
        i=2
        L=[a0,a1]
        while(i<=k):
            L.append(L[-1]*p+L[-2]*q)
            i+=1;
        print(L[-1]%10000)
    except:
        break

编辑于 2021-03-19 17:44:22 回复(0)

Python

lx的流星

while True:
    try:
        a0,a1,p,q,k=map(int,input().strip().split(' '))
        if k==1:
            print(a0%10000)
        elif k==2:
            print(a1%10000)
        else:
            list1=[a0,a1]
            for i in range(2,k+1):
                result=p*list1[i-1]+q*list1[i-2]
                list1.append(result)
            print(list1[-1]%10000)
    except:
        break

发表于 2019-08-26 13:02:14 回复(0)

Python

TimeMac

try:
    while True:
        a,b,p,q,k = list(map(int,input().split()))
        num = 2
        while num <= k:
            b,a = p*b+q*a,b
            num += 1
        print(b%10000)
except Exception:
    pass

编辑于 2018-10-09 23:30:00 回复(0)

Python

华科平凡

python solution, easy to understand:

while True:
    try:
        a,b,c,d,e=map(int,input().split())
        start=[a,b]
        for i in range(e-1):
            start.append(c*start[-1]+d*start[-2])
        print(start[-1]%10000)
    except:
        break

编辑于 2017-10-03 21:56:34 回复(1)

Python

红尘梦断都城

#法1：递归求解，太耗时编译不通过
a0,a1,p,q,k = list(map(int,input().split()))
def f(n):
    if n == 0:
        return a0
    elif n==1:
        return a1
    else:
        return p*f(n-1) + q*f(n-2)
print(f(k)%10000)

#法2，常规方法
a0,a1,p,q,k = list(map(int,input().split()))
a=[a0,a1]
for i in range(2,k+1):
    a.append((p*a[i-1] + q*a[i-2])%10000)
print(a[k]%10000)

#法3，常规方法，只记录两个中间值
while 1:
    try:
        a0,a1,p,q,k = list(map(int,input().split()))
        if k==0:
            print(a0%10000)
        elif k==1:
            print(a1%10000)
        else:
            for i in range(2,k+1):
                temp = p*a1 + q*a0
                a0,a1 = a1,temp%10000
            print(temp%10000)
    except:
        break

编辑于 2017-09-02 17:17:57 回复(0)