斐波那契凤尾

[编程题]斐波那契凤尾

热度指数：14710 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

输入描述:

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出描述:

对应每一组输入，输出第n个斐波那契数的最后6位。

示例1

输入

1<br/>2<br/>3<br/>4<br/>100000

输出

1<br/>2<br/>3<br/>5<br/>537501

算法知识视频讲解

Java

这个科密不会敲代码

在这里判断斐波那契数不能用递归，会导致栈溢出，用非递归则不会

注意输出形式，形式不对，通不过（被输出折磨了一天）

import java.util.Scanner;

/**
 * @Author Huang
 * @Title
 * @Date 2022/5/31 10:50
 */
public class Main{
    static int[] fibArr = new int[100001];
    public static void main(String[] args) {
        setFibArr();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            System.out.printf((n < 29 ? "%d\n" : "%06d\n"),fibArr[n]);
        }
    }

    public static void setFibArr() {
        fibArr[0] = 1;
        fibArr[1] = 1;
        for (int i = 2; i < 100001; i++) {
            fibArr[i] = (fibArr[i - 1] + fibArr[i - 2]) % 1000000;
        }
    }
}

发表于 2022-05-31 17:16:40 回复(0)

Java

reke

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] fib = new int[100001];
        fib[0] = 1;
        fib[1] = 1;
        for(int i = 2; i < fib.length; i++){
            fib[i] = (fib[i-1]+fib[i-2])%1000000;
        }
        while(sc.hasNext()){
            int n = sc.nextInt();
                 //因为牛客的“严谨”，不得不%06d
            System.out.printf((n<25 ? "%d\n":"%06d\n"), fib[n]);
        }
    }
}

编辑于 2021-07-20 22:08:32 回复(0)