首页 > 试题广场 >

斐波那契凤尾

[编程题]斐波那契凤尾

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

算法知识视频讲解

C/C++

hanjiangxue

/*
 * 详解：https://blog.csdn.net/qq_33375598/article/details/104606946
 */
#include <cstdio>

typedef long long ll;
const int MAXN = 100010;
int F[MAXN] = {1,1};

int main(int argc, char const *argv[]){
    int n;
    for (int i = 2; i <= 100000; ++i) {//打表（空间换时间）时间复杂度O(n+Q),n为表长，Q为查询次数
        F[i] = (F[i -1] + F[i-2])% 1000000;
    }
    while(scanf("%d", &n) != EOF){
            printf((n < 25 ?"%d\n" : "%06d\n"),F[n]);//F[25]=121393第一个6位数,因此当n大于等于25时，补齐前面的0
    }
    return 0;
}

发表于 2020-03-02 10:49:10 回复(0)

C/C++

Caffeine

思路： 就是刚。
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    int a[100002] = { 0 };
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i < 100002; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
        if (a[i] / 1000000 > 0)
        {
            a[i] = a[i] % 1000000;
        }
    }
    int n;
    while (cin >> n)
    {
        if(n < 37)
            cout << a[n ] << endl;
        else
        {
            cout << setfill('0') << setw(6) << a[n] << endl;
        }
    }
}

发表于 2018-08-11 17:59:32 回复(0)

C/C++

Hylance

#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
   long f[100001]={1,2};
   for(int i=2;i<100000;i++)
   {
       f[i]=(f[i-1]+f[i-2])%1000000;
   }
   int n;
   while(cin>>n)
   {
      if(n<31)
        cout<<f[n-1]<<endl;
      else
        cout<<setw(6)<< setfill ('0')<<f[n-1]<<endl;

   }
}

发表于 2018-04-14 16:08:58 回复(0)

C/C++

K猎食者

//用了一个矩阵快速幂的方法，详细的可以去网上搜下关于斐波那契数列这方面的知识。

//我忘记了输出补零的格式。看到前面的一位朋友的代码，实在是感到汗颜。共勉

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAX = 100003;
const int RULE = 1000000;
long long data[MAX];
bool jinwei[MAX];
int f(int index);
void check(int index){
    data[index] = f(index);
    if(data[index]/RULE > 0){
        jinwei[index] = 1;
        data[index]%=RULE;
    }
}
int f(int index){
    if(data[index]){
        return data[index];
    }else{
        int le = index/2;
        int ri = index - index/2;
        check(le);
        check(le+1);
        check(ri);
        check(ri-1);
        data[index] = data[le+1]*data[ri] + data[le]*data[ri-1];
        if(data[index]/RULE > 0){
            jinwei[index] = 1;
            data[index]%=RULE;
        }
        return data[index];
    }
}

int main(){
    data[0] = 0;
    data[1] = data[2] = 1;
    memset(jinwei,0,sizeof(jinwei));
    int n;
    while(scanf("%d",&n)!=EOF){
        int re = f(n+1);
        if(jinwei[n+1]){
            if(re > 99999){
                printf("%d\n",re);
            }else if(re > 9999){
                printf("0%d\n",re);
            }else if(re > 999){
                printf("00%d\n",re);
            }else if(re > 99){
                printf("000%d\n",re);
            }else if(re > 9){
                printf("0000%d\n",re);
            }else{
                printf("00000%d\n",re);
            }
        }else{
            printf("%d\n",re);
        }

    }
    return 0;
}

发表于 2018-03-27 16:11:31 回复(0)

LuxSun

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n=in.nextInt();
			long a=0,b=1,sum=0;
			for (int i = 0; i < n; i++) {
				sum=(a+b)%1000000;
				a=b;
				b=sum;
			}
			System.out.println(sum);
		}
	}
}

这代码凭什么超时？！

发表于 2017-07-12 10:15:24 回复(3)

淡泊、明志

#include<stdio.h>
int main(){
    int Arr[100001];
    int n = 0;
    Arr[0] = 1;
    Arr[1] = 1;
    for (int i = 2; i <= 100000; i++)
    {
        Arr[i] = Arr[i - 1] + Arr[i - 2];
        Arr[i] = Arr[i] % 1000000;
    }
    while (scanf("%d",&n) != EOF){
        //前面补0,要用06d
        printf((n < 29 ? "%d\n" : "%06d\n"),Arr[n]);
    }
    return 0;
}

编辑于 2015-05-25 17:28:21 回复(5)

菜鸟葫芦娃

题目输入描述：

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

对于这样类似的题目,最好的方式是进行预处理,把要计算的数值进行第一次计算的时候存储下来,然后剩下的测试用例只进行查找即可，因为查找比计算更加高效，再加上一次运算总比次次运算要快。不要担心第一次计算那么大数值时候回超时，因为这个数量级的运算还是很快的。

代码如下：

import java.util.Scanner;
public class Main{
    static int[] fib = new int[100001];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        fib[0] = 1;
        fib[1] = 1;
        while (in.hasNext()) {
            int n = in.nextInt();
            System.out.printf((n<25?"%d\n":"%06d\n"), getFibonacci(n));
        }
        in.close();
    }
    static int getFibonacci(int n) {
        if (fib[2] == 0) {
            for (int i = 2; i <100001; i++) {
                fib[i] = (fib[i-1] + fib[i-2]) % 1000000;
            }
        }
        return fib[n];
    }

发表于 2015-06-19 15:51:09 回复(5)

C/C++

WZ_Dale

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> F(100001, 0);
    F[0] = 1;
    F[1] = 1;
    //提前计算斐波那契数列，只保留后6位
    for(int i = 2; i <= 100000; ++i){
        F[i] = F[i - 2] + F[i - 1];
        F[i] = F[i] % 1000000;//由于是相加，所以只要后六位不影响下一个数的结果
    }
    int n;
    while(cin >> n){
        if(n < 29){
            //斐波那契数列小于6位
            printf("%d\n", F[n]);
        }
        else{
            printf("%06d\n", F[n]);
        }
    }
    return 0;
}

发表于 2020-08-20 11:27:30 回复(0)

在做测评的卡尔很强大

sum1 = 1

sum2 = 1

samp = [1, 1]

for i in range(99999):

sum2 = sum1 + sum2

sum1 = sum2 - sum1

sum2 = sum2 % 1000000

samp.append(sum2)

while 1:

try:

n = int(input())

print(samp[n])

except:

break

"""为什么我python用列表会超内存啊。有没有大佬解释一下，有没有什么好多办法解决啊"""

发表于 2023-04-11 21:55:09 回复(1)

24届小菜只因

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<unsigned long long> nums(100001, 0);
    nums[0] = 1, nums[1] = 1;
    int t = 0; bool flag = false;
    for (int i = 2; i <= 100000; i++)
    {
        nums[i] = nums[i - 1] + nums[i - 2];
        if (nums[i] >= 1000000 && flag == false) t = i, flag = true;// 计算下斐波那契数组从哪一个开始超出6位
        nums[i] = nums[i] % 1000000;//由于是相加，所以只要后六位不影响下一个数的结果
    }
    int n;
    while(cin >> n)
    {
        if (n >= t)
            printf("%06d\n", nums[n]);
        else cout << nums[n] << endl;
    }
    return 0;
}

发表于 2023-02-26 22:09:09 回复(0)

C/C++

侬是一个好人

#include<iostream>
using namespace std;

int main()
{
    //本题不光看单个测试用例的用时,还看多组用例的总用时
    //用数组存储起来斐波那切数，下个测试用例可以直接查找
    
    int border = -1;  //边界，i超过这个后，得到的斐波那切数超过六位数
    long long ans[100001] = {0};
    ans[1] = 1;
    ans[2] = 2;
    for(int i = 3; i <= 100000; i++)
    {
        long long next = ans[i-1] + ans[i-2];
        if(border == -1 && next >= 100000){ //border=-1保证找到的是第一个(边界)
            border = i + 1;  //第i+1个斐波那切数超过六位数
        }
        ans[i] = next % 1000000;
    }
    
    int n;
    while(cin >> n)
    {
        if(n >= border){
            printf("%06d\n",ans[n]);
        }else{
            printf("%d\n",ans[n]);
        }
    }
    return 0;
}

发表于 2023-02-14 16:53:51 回复(0)

未见花闻

// write your code here

import java.util.*;

public class Main {
    public static long[] fibs = new long[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        //生成fib
        fibs[0] = 1;
        fibs[1] = 1;
        //标记结果是否达到7位数，因为7位数后需输出后六位，含0也需输出
        int flag = 0;
        for (int i = 2; i < fibs.length; i++) {
            long ret = fibs[i - 1] + fibs[i - 2];
            fibs[i] = ret % 1000000;
            if (flag == 0 && ret >= 1000000) flag = i;
        }
        
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n < flag) System.out.println(fibs[n]);
            else System.out.printf("%06d\n", fibs[n]);
        }
    }
}

发表于 2022-09-30 19:16:49 回复(0)

一个被现实忽略的人

import java.util.*;
public class Main {
    public static void main(String[] args){
        int border = -1;
        long[] ans = new long[100000];
        ans[0] = 1;
        ans[1] = 2;
        for(int i =2;i< 100000;i++){
            long next = ans[i-1] + ans[i-2];
            if(border == -1 && next >=1000000){
                border = i+1;
            }
            ans[i] = next % 1000000 ; 
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            if(border >= n){
               System.out.println(ans[n-1]);
            }else{
                
                System.out.printf("%06d\n",ans[n-1]);
            }
            
        }
        sc.close();
    }
}

发表于 2022-08-01 23:33:41 回复(0)

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)

大大的糖果果

把已经求得的存进list集合里这样，不够了再扩容。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        while(sc.hasNext()){
            int n = sc.nextInt();
            if(n < list.size()){
                int a = list.get(n-1);
                if(n > 25){
                    System.out.printf("%06d\n",a);
                }else{
                    System.out.println(a);
                }
            }else{
                int ln = list.size();
                int a = list.get(ln-1) , b = list.get(ln-2) , c = list.get(ln-3);
                for(int i = ln+1;i <= n;i++){
                    c = b;
                    b = a;
                    list.add(a = (b + c) % 1000000);
                }
                if(n > 25){
                    System.out.printf("%06d\n",a);
                }else{
                    System.out.println(a);
                }
            }
        }
    }
}

发表于 2022-05-11 00:37:22 回复(0)

来学习的小张

import java.util.Scanner;
public class Main {
public static int[] arr = new int[100001];
    public static int fun(int n){
        arr[0] = 1;
        arr[1] = 1;
       if(arr[2] == 0){
            for(int i = 2;i < 100001;i++){
                arr[i] = arr[i - 1] + arr[i - 2];
                arr[i] = arr[i] % 1000000;
                }
    }
    return arr[n];
}
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    while (in.hasNextInt()) {
        int n = in.nextInt();
        int res = fun(n);
        System.out.printf(n < 29 ? "%d\n" : "%06d\n",res);
        }
    }
}

编辑于 2022-05-15 20:15:21 回复(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)

一条余弦Cos

#include<iostream>
using namespace  std;
int main()
{
    int F[100000]={0};
    F[0]=1;
    F[1]=1;
    //
    for(int i=2; i<=100000; ++i)
    {
        F[i]=F[i-1]+F[i-2];
        F[i]=F[i]%1000000;//只保留后六位
    }
    int n;
    while(cin>>n)
    {
        if(n<29)
            printf("%d\n",F[n]);
        else
            printf("%06d\n",F[n]);
    }
    return 0;
}

发表于 2021-06-01 19:55:20 回复(0)

我不是董皓宇。

//哪位哥哥姐姐看看我这个为什么通过不了呗
#include<iostream>
#include<iomanip>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        int a = 1;
        int b = 0;
        int c = 0;
        while(n--)
        {
            c = a+b;
            c %= 1000000;
            b = a;
            a = c;
        }
        cout<<setfill('0')<<setw(6)<<c<<endl;
    }
}

编辑于 2020-03-04 22:16:10 回复(1)

hestyle

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    //建立一张表，用于记录斐波拉契尔数列的各项值
    int fTable[100001] = {0, 1, 2};
    for (int i = 3; i < 100001; ++i) {
        fTable[i] = fTable[i - 1] + fTable[i - 2];
        //需要对每项进行求余，否则会溢出
        fTable[i] = fTable[i] % 1000000;
    }
    int number = 0;
    //scanf返回值为正确输出数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &number) != - 1) {
        //题目有些坑，number >= 29时前面补0,要用06d（输出结果不足六位需要补0）
        printf((number < 29 ? "%d\n" : "%06d\n"),fTable[number]);
    }
    return 0;
}

发表于 2020-03-03 08:35:52 回复(0)