首页 > 试题广场 >

求数列第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

输入

输出

算法知识视频讲解

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
            }
        }
    }
}