首页 > 试题广场 >

求数列第n项

[编程题]求数列第n项

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

米兔从兔米那里了解到有一个无限长的数字序列 1, 2，3，3，4，4，4, 5，5，5，5，5 ...,(已知此数列有一定规律，现将这些数字按不同数值堆叠，相同值的数字在同一层)。米兔想知道这个数字序列的第n个数所在的那一层之前的所有层里共有多少个数。

输入描述:

n(n<=1e18)

输出描述:

第n个数所在的那一层之前的所有层里共有多少个数

示例1

输入

输出

算法知识视频讲解

小小呆萌坤

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{    
    class Program
    {
        public static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
        }
        public static void Func(string line)
        {
            long n = long.Parse(line);
            if (n <= 2)
            {
                Console.WriteLine(Math.Max(n - 1, 0));
                return;
            }
            long a = 1, b = 1;
            while (b<=n)
            {
                long t = a;
                a = b;
                b += t;
            }
            Console.WriteLine(a-1);
        }
    }
}

斐波那契数答案就是当b>n时前一个数(a)-1 并不需要什么记录层数啊,在拿去减,麻烦!

编辑于 2020-01-13 17:01:05 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    ll n;
    cin>>n;
    if(n<=1){
        cout<<0<<endl;
        return 0;
    }
    if(n==2){
        cout<<1<<endl;
        return 0;
    }
    ll a=1, b=1;
    ll s = a + b, t;
    while(s < n){
        t = a + b;
        s += t;
        a = b;
        b = t;
    }
    cout<<s-t<<endl;

    return 0;
}

发表于 2019-12-23 00:17:35 回复(0)

暴力算法

//每个数字出现的次数是1，1，2，3，5，……也就是斐波那契数列
//因为不使用递归的做法，a用于记录前一个数，cnt代表当前数字的个数
//ans则是每次加cnt，代表每一层数的累加，也代表该层最后一个数的序列
//所以在每次while循环中，都跳跃cnt。
//直到大于n，输出。注意处理n=1，ans=0
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long ans = 0;
        long cnt = 1;
        long a = 0;
        while(true){
            if(ans+cnt >= n) break;
            ans += cnt;
            cnt += a;
            a = cnt-a;
        }
        System.out.println(ans);
    }
}

发表于 2019-09-07 14:09:55 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    if(n==0 || n==1)
    {
        cout<<0;
        return 0;
    }
    if(n==2)
    {
        cout<<1;
        return 0;
    }
    long long first=1,second=1;
    long long sum=first+second;
    long long cur=0;
    for(int i=2;;i++)
    {
        cur=first+second;
        sum+=cur;
        first=second;
        second=cur;
        if(sum>=n)
        {
            cout<<sum-cur;
            return 0;
        }
    }
}

发表于 2019-07-04 15:10:03 回复(0)

Python

ElonB

""""
斐波那契数列
"""

if __name__ == "__main__":
    n = int(input().strip())
    ans = 0
    a, b = 0, 1
    while True:
        if ans + b >= n:
            break
        ans += b
        a, b = b, a + b
    print(ans)

发表于 2019-07-14 12:32:01 回复(0)

C/C++

广州市民林先生

解析：题目1, 2，3，3，4，4，4, 5，5，5，5，5 ...，明显每一个相同的数组成一层，构成斐波那契数列，然后要求输入n为第n个数，输出这个数所在层的前面所有层的数字个数之和。举个例子，输入n = 4，也就是第四个数，而第四个数是3，那么要求输出就应该3这一层之前的所有层的数字个数之和，也就是1和2的总个数，所以应该输出2。

所以需要用一个sum来计数（计算斐波那契数列的和），这个"和"代表的就是当前(i和i之前)所有的数字总个数，当sum >= n的时候，就可以输出答案了。那在sum < n的过程，需要做的工作就是i，j迭代，然后让sum依次增加i，直到 sum >= n。这个时候的sum代表的是从开头加到 i 所在这一层的所有数字个数之和，而最后答案需要输出的是i所在这一层之前的所有数字个数之和，所以输出sum - i 即可。代码：

#include <iostream>
using namespace std;

int main(){
    long long n;
    cin >> n;
    if(n <= 1){
        cout << 0 << endl; //第1个数之前 没有数
        return 0;
    }
    long long i = 1;
    long long j = 1;
    long long sum = 1;
    while(sum < n) {
        j = i + j;
        i = j - i;
        sum += i;
    }
    cout << sum - i << endl;
    return 0;
}

编辑于 2020-06-05 23:35:01 回复(2)

WMYW

//上面都是讨论了n等于1和2的情况
//一步到位，不用讨论条件n等于1和2的情况
#include<iostream>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    long long sum=0;
    long long i=1;
    long long j=-1;
    long long count=0;
    while(count<n)
    {
        sum=i+j;
        j=i;
        i=sum;
        count+=sum;
    }
    count-=sum;
    cout<<count;
}

发表于 2020-03-12 09:39:03 回复(0)

Ped

var n = readline();
function fibb(n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    var a = 1,
        b = 1,
        c = 0;
    var result = 2;
    while(true) {
        if (result >= n ) break;
        c = a + b;
        result += c;
        a = b;
        b = c;
    }
    return result - c;
}
print(fibb(n));

发表于 2019-10-07 18:43:14 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    if n<=2{
        fmt.Print(n-1)
        return
    }
    a,b,c:=0,1,1
    sum:=2
    for i:=3;;i++{
        a=b
        b=c
        c=a+b
        sum+=c
        if sum>=n{
            fmt.Print(sum-c)
            break
        }
    }
}

发表于 2023-03-23 10:15:37 回复(0)

Java

肥咩咪

测试用例的数比较大，不能用int型，要用long
对斐波那契数列进行累加求和sum，如果这个和sum大于等于输入的n，记录此时的索引i，这个索引i就是n所在的层数。然后遍历第1层到n-1层，累加求和，就是最终结果。

import java.util.*;
public class Main
{
    public static void main(String [] args)
    {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextLong())
        {
            long n=sc.nextLong();
            long sum=0;
            long index=0;//第n个数所处的层数
            for(long i=1;;i++)
            {
                sum+=fib(i);
                if(sum>=n)//假如说累加和大于等于n了，说明此时的i就是第n个数所处的行数
                {
                    index=i;
                    break;
                }
            }
            long before=index-1;
            long s=0;
            for(long i=1;i<=before;i++)
            {
                s+=fib(i);
            }
            System.out.println(s);

        }

    }

    private static long fib(long n)//斐波那契函数
    {
        long a=1;
        long b=1;
        for(long i=1;i<n-1;i++)
        {
            b=a+b;
            a=b-a;
        }
        return b;
    }
}

发表于 2020-03-28 11:19:18 回复(0)

JavaScript

随遇而安_

var line =readline();
var N=parseInt(line);
print(getNum(N))

function getNum(n){
    if(n==1){
        return 0
    }else if(n==2){
        return 1
    }else{
        var feibo=new Array();
        feibo[0]=1;
        feibo[1]=1;
        var sum=feibo[0]+feibo[1];
        for(var i=2;;i++){
            feibo[i]=feibo[i-1]+feibo[i-2];
            sum+=feibo[i];
            if(sum>=n){
                return 2*feibo[i-1]+feibo[i-2]-1
            }
        }
    }
}

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为65.00%

用例:
567161432008720451

对应输出应该为:

420196140727489672

你的输出为:

420196140727489660

大佬们看看哪里有问题啊！！！！！！！！！！！！！！！！！！！！！

发表于 2019-09-06 15:59:54 回复(5)

Python

贾志统

def func(n):
    if n <= 1:
        return 0
    a = 0
    b = 1
    counter = 1
    while counter < n:
        #temp = a + b
        #a = b
        #b = temp
        a, b = b, a+b
        counter += b
    return counter - b


input_num = int(input())
print(func(input_num))

发表于 2019-09-06 10:34:12 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int main()
{
    // 每个数字的个数是按斐波那契数列排的
    // 用sum记录当前已经排了多少数字
    // fibo记录下一个数字的个数
    long long n,first=1,second=1,sum=2,fibo=2;
    cin>>n;
    if(n==1) {
        cout<<0; return 0;
    }
    if(n==2){
        cout<<1;return 0;
    }
    while(sum<n)
    {
        fibo = first + second;
        sum += fibo;
        first = second;
        second = fibo;
    }
    cout<<sum-fibo<<endl;
    
    return 0;
}

发表于 2019-08-13 22:20:48 回复(0)

lentolove

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(bf.readLine());
        //one表示第n-1层的数字个数，two表示第n层的数字个数，sum表示第n层的总数字个数
        //如果 sum + two的个数大于等于n，则前一层所有个数就是sum，直接return
        long one = 0, two = 1, sum = 0;
        while (sum < n) {
            long temp = one + two;
            one = two;
            two = temp;
            if (sum + one >=n) {
                System.out.println(sum);
                return;
            } else {
                sum += one;
            }
        }
    }
}

发表于 2019-07-30 15:53:31 回复(0)

Polestar_a

n = int(input())
a,b,res,num = 0,1,0,0
while(num<n):
    res = a+b
    a=b
    b=res
    if num+a>=n:
        break
    else:
        num+=a
print(num)

发表于 2019-07-12 09:35:24 回复(0)

sea_sid

斐波那契数列：F(1)=1，F(2)=1， F{n)=F(n-1)+F(n-2) //n>=2

求和公式：S(n) = 2F(n+2) - 1

来自：https://blog.csdn.net/Z_sea/article/details/83059095

发表于 2019-07-01 10:32:11 回复(0)

zhouqctech

// 获取数字序列的第n个数所在的那一层之前的所有层里的数字个数之和
function getCount(n) {
  let currentLayer = checkInWhichLayer(n);
  if (currentLayer <= 1) {
    return 0;
  } else {
    return getTotalLayerCount(currentLayer - 1);
  }
}

// 获取某一层里的数字个数
function getLayerCount(layer) {
  if (layer < 1) {
    return;
  } else if (layer === 1 || layer === 2) {
    return 1;
  } else {
    return getLayerCount(layer - 1) + getLayerCount(layer - 2)
  }
}

// 获取从第1层到第n层所有层里的数字个数总和
function getTotalLayerCount(layer) {
  if (layer === 1) return 1;
  if (layer === 2) return 2;
  let sum = 0;
  if (layer > 2) {
    for(let i = 1; i <= layer; i++) {
      sum += getLayerCount(i);
    }
  }
  return sum;
}

// 检测第n个数在第几层
function checkInWhichLayer(n, layer = n) {
//     console.log("n: " + n)
//     console.log("layer: " + layer)
    if (n === 1) return 1;

    if (n > 1) {
      if (n < getTotalLayerCount(layer)) {
//         console.log("less than current layer count");
        if (n > getTotalLayerCount(layer - 1)) {
//           console.log("greater than previous layer count");
          return layer;
        } else if (n === getTotalLayerCount(layer - 1)){
//           console.log("equal to previous layer count");
          return layer - 1;
        } else {
          return checkInWhichLayer(n, layer - 1);
        }
      } else if (n === getTotalLayerCount(layer)) {
        return layer;
      }
  }
}

发表于 2019-05-14 15:55:32 回复(0)

还在努力的小丸子

大神们，请问我的代码哪里出了问题呢？？？？

发表于 2019-04-12 10:34:14 回复(0)

李小木的微博

var sum=0
var f=[];
var n;
function fib(n){
for(i=0;;i++){
if (i==0){
 f[i]=0;
 }
else if(i==1){
f[i]=1;
}
else{
 f[i]=f[i-1]+f[i-2];

}
sum=sum+f[i];
 if (sum>=n){
sum=sum-f[i];
  break;
 }
}
return sum
}
console.log(fib(n));

发表于 2019-04-04 17:43:37 回复(0)

zhanzhansame

随便用js写了下过程，js对于具体获取输入的数字，这个编辑器怎么处理机制不太懂，所以就不加了，用其他语言会比较好点

	
	
		function myF(n){
	

	
		 var myArr = new Array();
	

	
		 myArr[0] = 1;
	

	
		 myArr[1] = 1;
	

	
		 var sum = myArr[0] + myArr[1];
	

	
		 for(var i=2;;i++){
	

	
		 myArr[i] = myArr[i-1] + myArr[i-2];
	

	
		 sum += myArr[i];
	

	
		 if(sum >= n){
	

	
		 return sum-myArr[i];
	

	
		 }
	

	
		 }
	

	
		}
	

	
		console.log(myF(6))   //输出为4