首页 > 试题广场 >

递推数列

[编程题]递推数列

热度指数：25719 时间限制：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

华科平凡

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)

愣头青丶别处仰望

思路：典型的空间换时间的题

题目本身很简单，拿出来主要是想说一下空间换时间，时间换空间的思维。
这题本来是递归的问题，但是递归会有大量重复计算。
所以采用一个数组存储临时结果，避免重复计算。
常规的递归算法改非递归算法的思路就是空间换时间。
这个在树、图的遍历中经常会出现，要求你采用非递归算法。


#include<stdio.h>
#include<stdlib.h>
int main(){
    int a0,a1,p,q,k;
    while(scanf("%d %d %d %d %d",&a0,&a1,&p,&q,&k)!=EOF){
        int *a=(int *)calloc(k+1,sizeof(int));
        a[0]=a0,a[1]=a1;
        for(int i=2;i<=k;i++)
            a[i]=(p*a[i-1]+q*a[i-2])%10000;
        printf("%d\n",a[k]);
    }
    return 0;
}

发表于 2018-01-29 10:35:37 回复(0)

C++

之一不之

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int dp[maxn];

int main(){
    int a0,a1,p,q,k;
    cin>>a0>>a1>>p>>q>>k;
    dp[0]=a0%10000;dp[1]=a1%10000;
    for(int i=2;i<=k;i++){
        dp[i]=(p*dp[i-1]+q*dp[i-2])%10000;
    }
    cout<<dp[k]<<endl;
    return 0;
}

发表于 2021-09-01 21:43:31 回复(1)

用户抉择

#include <stdio.h>

int main(){
    int a0,a1,p,q,k;
    int i;
    while(scanf("%d %d %d %d %d",&a0,&a1,&p,&q,&k)!=EOF){
        int a[k+1];
        a[0]=a0;
        a[1]=a1;
        for(i=2;i<k+1;i++) a[i]=(p*a[i-1]+q*a[i-2])%10000;
        printf("%d\n",a[k]);
    }
}

循环比递归时间复杂度低(•̀ᴗ•́)و

发表于 2021-02-04 22:46:49 回复(1)

sunX&Y

#include<bits/stdc++.h>

using namespace std;

long long a0, a1, p, q, k;

int main()
{
    while(cin >> a0 >> a1 >> p >> q >> k)
    {
        long long t;
        for(int i = 2;i <= k; i++)
        {
            t = (p*a1 + q*a) % 10000;
            a0 = a1; a1 = t;
        }
        cout << t << '\n';
    }
    return 0;
}

发表于 2021-01-22 17:30:50 回复(0)

素人鱼夫

#include<iostream>
using namespace std;
typedef long long INT; //算简单吗
int main()
{
   INT a0,a1,p,q,k;
    while(cin>>a0>>a1>>p>>q>>k) //先按照常规思路
    {
        INT result;
        if(k==0)
        {
            result=a0%10000;
        }     
        else if(k==1)
        {
            result=a1%10000;
        }
        else
        {
            INT i=1;
            while(i<k)
            {
                result=(q*a0+p*a1)%10000;
                a0=a1;
                a1=result;
                i++;
            }
           
        }
        cout<<result<<endl;
             
        
    }
    return 0;
}

发表于 2020-03-26 22:14:34 回复(0)

Java

LHC0512

Java 解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a0 = scanner.nextInt();
        int a1 = scanner.nextInt();
        int p = scanner.nextInt();
        int q = scanner.nextInt();
        int k = scanner.nextInt();
        
        int[] an = new int[k+1];
        an[0]= a0;
        an[1]= a1;
        for (int i = 2; i <= k; i++) an[i]= (p*an[i-1]+q*an[i-2])%10000;
        System.out.println(an[k]);
    }
}

发表于 2020-03-18 11:17:29 回复(0)

C/C++

牛客480180948号

/*
思路：矩阵递推公式：
[An;An-1]=[p,q;0,1]^(k-1) *[A1;A0]
*/

#include <iostream>
#include <valarray>

using namespace std;

typedef valarray<int> va;
const int NUM =10000;

va mod_pin(const va& v){ //矩阵平方
	va val(4);
	val[0]=(v[0]*v[0]+v[1]*v[2])%NUM;
	val[1]=(v[0]*v[1]+v[1]*v[3])%NUM;
	val[2]=(v[2]*v[0]+v[3]*v[2])%NUM;
	val[3]=(v[2]*v[1]+v[3]*v[3])%NUM;
	return val;
}

va mod_chen(const va& v,const va& v1){//矩阵乘法
	va val(4);
	val[0]=(v[0]*v1[0]+v[1]*v1[2])%NUM;
	val[1]=(v[0]*v1[1]+v[1]*v1[3])%NUM;
	val[2]=(v[2]*v1[0]+v[3]*v1[2])%NUM;
	val[3]=(v[2]*v1[1]+v[3]*v1[3])%NUM;
	return val;
}

int main(){
	valarray<int> val(4);
	int a0,a1,p,q,k;
	cin>>a0>>a1>>p>>q>>k;
    //输入完毕
    
    //矩阵初始化
	val[0]=p;
	val[1]=q;
	val[2]=1;
	val[3]=0;
	val%=NUM;
	k--;

        //求val的k次方
	va ans(1,4);
	ans[1]=0;
	ans[2]=0;
	while(k!=0){
		if(k%2==1)
			ans = mod_chen(ans,val);//矩阵乘法
		k=k>>1;
		val=mod_pin(val);//矩阵平方
	}
	int an = (ans[0]*a1+ans[1]*a0)%NUM;
	cout <<an<<endl;
	return 0;
}

时间复杂度最优：logn；

思路：矩阵递推公式：
[An;An-1]=[p,q;0,1]^(k-1) *[A1;A0]

运行时间：3ms
占用内存：504k

编辑于 2020-02-25 15:13:11 回复(0)

冲就完事了s

#include <stdio.h>
(737)#include <stdint.h>

int main()
{
    //freopen("data.txt", "r", stdin);
    int a[10000], p, q, k;
    scanf("%d%d%d%d%d", &a[0], &a[1], &p, &q, &k);
    for (int i = 2; i <= k; i++)
    {
        a[i] = (p * a[i - 1] + q * a[i - 2]) % 10000;
    }
    printf("%d\n", a[k]);

    return 0;
}

发表于 2020-02-21 16:28:16 回复(0)

C/C++

奔跑的牛阿牛

遇到了两个问题：1.用递归的话时间上可能会无法通过，改成迭代后有所改善；2.看了大家的讨论后，可能还是需要用递归的思想去理解每一项答案，每次计算都模

#include<iostream>
#include<cstdio>

using namespace std;

int main(){
    int a[1000];
    int p,q,k;
    while(cin>>a[0]>>a[1]>>p>>q>>k){
        for(int i=2; i<=k; i++){
            a[i] = (p*a[i-1]+q*a[i-2])%10000;
        }
        cout<<a[k]<<endl;
    }
    return 0;
}

发表于 2020-02-19 11:42:45 回复(1)

C/C++

譕訫QAQ

刚开始理解错了题义然后使用了一个简单的递归就过了测试用例以为没问题了结果错了数值过大

需要对每个 a[i] 进行对10000求模才能不出现数值过大导致的错误

#include <iostream>

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <cstring>
using namespace std;

int main(void)
{
    int a0,a1,p,q,k;
    while(cin>>a0>>a1>>p>>q>>k)
    {
        int a[k+1];
        memset(a,0,sizeof(a));
        a[0]=a0;
        a[1]=a1;
        for(int i=2;i<=k;i++)
            a[i]=(a[i-1]*p+a[i-2]*q)%10000;
        cout<<a[k]<<endl;
    }
    return 0;
}

发表于 2019-11-16 23:38:38 回复(0)

C/C++

hello古斯卡

int main() {
    int a0, a1, p, q, k;
    cin >> a0 >> a1 >> p >> q >> k;
    int sum = 0;
    for (int i = 2; i <= k; i++) {
        sum = (p * a1 + q * a0) % 10000;
        a0 = a1;
        a1 = sum;
    }
    cout << sum << endl;
    return 0;
}

发表于 2019-10-16 23:41:21 回复(0)

C/C++

江山如画不比你

简单的递推求解，需要注意的是要对每个a[i]求模，否则会因超出int范围导致答案错误

#include<stdio.h>
int main(){
    int a[10001],p,q,k;
    while(scanf("%d%d%d%d%d",&a[0],&a[1],&p,&q,&k)!=EOF){
        for(int i=2;i<=k;i++){
            a[i] = (a[i-1]*p+a[i-2]*q)%10000;
        }
        printf("%d\n",a[k]);
    }
    return 0;
}

发表于 2019-03-17 10:21:39 回复(0)

C/C++

算法小屁孩

#include<bits/stdc++.h>
int a[1000];
int main(){
    int p,q,k;
    while(scanf("%d %d %d %d %d",&a[0],&a[1],&p,&q,&k)!=EOF){
        for(int i=2;i<=k;i++)
            a[i]=(p*a[i-1]+q*a[i-2])%10000;
        printf("%d\n",a[k]);
    }
}

发表于 2019-03-15 17:57:51 回复(0)

Sirice



import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a0 = sc.nextInt();
        int a1 = sc.nextInt();
        int p = sc.nextInt();
        int q = sc.nextInt();
        int k = sc.nextInt();

        long [] a = new long [k+1];
        a[0] = a0;
        a[1] = a1;

        for (int i = 2; i <= k; i++) {
            a[i] = p * a[i - 1] + q * a[i - 2];
            if(a[i]>100000) {
                a[i] = a[i]% 10000;
            }
        }
        System.out.println(a[k] % 10000);

    }

}

直接算会超过long，所以对每个数都截断就好啦

发表于 2019-01-14 12:59:10 回复(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)

Java

/xinCupid☆

开个大小为2的数组就够了

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            int a0 = reader.nextInt();
            int a1 = reader.nextInt();
            int p = reader.nextInt();
            int q = reader.nextInt();
            int k = reader.nextInt();
            long[] a = {a0, a1};
            for (int i = 2; i <= k; ++i) {
                long tmp = p*a[1]%10000 + q*a[0]%10000; 
                a[0] = a[1];
                a[1] = tmp;
            }
            System.out.println(a[1]%10000);
        }
    }
}

发表于 2018-03-27 22:39:08 回复(0)

C/C++

练习时长两年半的Java练习生

#include<stdio.h>
int main(){
   int a[2],p,q,k,res,i;
   for(;~scanf("%d %d %d %d %d",&a[0],&a[1],&p,&q,&k);printf("%d\n",res%10000))
        for (res=k>1?0:a[k],i = 2; i <= k;i++)
            res = (q*a[0]+p*a[1])%10000,a[0]=a[1],a[1]=res;
}

发表于 2018-01-11 21:26:32 回复(0)

元气の悟空

#include<stdio.h>
const int mod=10000;
struct Matrix{
	long v[2][2];
	void init(int a,int b,int c,int d){
		v[0][0]=a,v[0][1]=b,v[1][0]=c,v[1][1]=d;
	}
    Matrix operator *(Matrix &tmp){
    	Matrix res;
    	res.init(0,0,0,0);
    	for(int i=0;i<2;++i)
    	    for(int j=0;j<2;++j)
    	        for(int k=0;k<2;++k){
    	        	res.v[i][j]+=v[i][k]*tmp.v[k][j];
    	        	res.v[i][j]%=mod;
    	        }
    	return res;
    }
};
Matrix pow(Matrix x,long y){
	Matrix res;
	res.init(1,0,0,1);
	for(;y;y>>=1,x=x*x)
	    if(y&1)res=res*x;
	return res;
}
int main(){
	int a0,a1,p,q,k;
	while(scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k)!=EOF){
		Matrix mat;
		mat.init(0,q,1,p);
		mat=pow(mat,k);
		long res=(a0*mat.v[0][0]+a1*mat.v[1][0])%mod;
		printf("%ld\n",res);
	}
}//矩阵快速幂

发表于 2017-08-04 08:41:21 回复(0)

hooli

#include "stdio.h"

int main() {
	long a, b, ak;
	long a0, a1, p, q, k;
	while (scanf("%ld %ld %ld %ld %ld", &a0, &a1, &p, &q, &k) != EOF) {
		a = a1;
		b = a0;
		for (long i = 2; i <= k; i++) {
            if(i == 1)break;
			ak = (p*a + q*b)%10000;
			b = a;
			a = ak;
		}
		printf("%ld\n", a%10000 );
	}
	return 0;
}

发表于 2017-01-07 12:27:19 回复(2)