我要招人

去企业版

首页 > 试题广场 >

递推数列

[编程题]递推数列

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

输出

算法知识视频讲解

Java

Forward2019

使用递归的优化形式；

import java.util.Scanner;

public class Ditui {

public static void main(String[] args) {

int a0,a1,p,q,k,temp =0;

Scanner sc = new Scanner(System.in);

a0 = sc.nextInt();

a1 = sc.nextInt();

p = sc.nextInt();

q = sc.nextInt();

k = sc.nextInt();

sc.close();

int i =1;

while(i<k){

temp = (p*a1 + q*a0)%10000;

a0 = a1;

a1 = temp;

i++;

}

System.out.println(temp);

}

发表于 2020-05-22 18:05:39 回复(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)

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)

Java

fhqplzj

import java.util.Scanner;

/**
 * Created by fhqplzj on 17-1-26 at 下午2:20.
 */
public class My6 {
    private static final int MOD = 10000;

    private static int getKth(int a0, int a1, int p, int q, int k) {
        a0 %= MOD;
        a1 %= MOD;
        if (k == 0) {
            return a0;
        }
        int a2 = a1;
        for (int i = 2; i <= k; i++) {
            a2 = ((p * a1 % MOD) + (q * a0 % MOD)) % MOD;
            a0 = a1;
            a1 = a2;
        }
        return a2;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int a0 = scanner.nextInt();
            int a1 = scanner.nextInt();
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            int k = scanner.nextInt();
            System.out.println(getKth(a0, a1, p, q, k));
        }
    }
}

发表于 2017-01-26 14:35:50 回复(0)