形如1, 1, 2, 3, 5, 8, 13, 21, 34, 55的数列,后一位是前面两位相加(斐波那契数列),写出函数要求找到第 N 位是多少,如:fib(3) => 3 , fib(5) => 8, 要求时间复杂度为O(n)。
const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, ouput: process.stdout }) let inArr = [] rl.on('line', line=>{ if(!line) return inArr.push(line.trim()) if(inArr.length === 1){ let n = +inArr[0] let dp = [1,1,2] for (let i = 3; i < n+1; i++) { dp[i]= dp[i-1]+dp[i-2] } console.log(dp[n]) } })
let n = ""; while(n = readline()){ let dp = new Array(n+1); dp[0] = 1; dp[1] = 1; for(let i = 2;i<=n;i++){ dp[i] = dp[i-1] + dp[i-2]; } console.log(dp[n]); }
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; struct Martix{ int row,col; long long martix[2][2]; Martix(){} Martix(int r,int c):row(r),col(c){} Martix(int n) { //单位方阵构造函数 this->row = n; this->col = n; this->martix[0][0] = 1; this->martix[1][1] = 1; this->martix[0][1] = 0; this->martix[1][0] = 0; } }; Martix multiply(Martix x,Martix y){ //矩阵乘法 Martix answer=Martix(x.row,y.col); for(int i=0;i<answer.row;++i) for(int j=0;j<answer.col;++j) { answer.martix[i][j]=0; for(int k=0;k<x.col;++k) answer.martix[i][j]+=(x.martix[i][k]*y.martix[k][j]); } return answer; } long long answer(int n){ if(n==0 || n==1){ return 1; } if(n==2){ return 2; } else { n-=1; Martix base=Martix(2,2); Martix ans=Martix(2); base.martix[0][0]=1; base.martix[0][1]=1; base.martix[1][0]=1; base.martix[1][1]=0; while(n!=0){ if(n%2==1){ ans=multiply(ans,base); } n>>=1; base=multiply(base,base); } return ans.martix[0][0]; } } int main(){ int n; while(scanf("%d",&n)!=EOF) { printf("%lld\n",answer(n+1)); } return 0; }
import java.util.Scanner; public class Main{ public static long fib(int num) { if(num==0||num==1) { return 1; } long [] it=new long [1000]; it[0]=1; it[1]=1; long result=0; for (int i = 2; i <=num; i++) { it[i]=it[i-1]+it[i-2]; result=it[i]; } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); System.out.println(fib(num)); sc.close(); } }
var fib = function(index){ let res = 1 for(let i = 1;i < index; i++){ res += fib(i - 1) } return res }在编译器上对的,牛客上不通过,我这对吗🤣
function fib(n){ if(n==0||n==1){ return 1 }else{ return fib(n-1)+fib(n-2); } } console.log(fib(5)) //递归的方法
typedef long long ll; #include<cstdio> ll fibo(int n){ if(!n || n == 1) return 1; ll fiboArr[n + 1]; fiboArr[0] = 1; fiboArr[1] = 1; for(int i = 2; i <= n; i++) fiboArr[i] = fiboArr[i - 2] + fiboArr[i - 1]; return fiboArr[n]; } int main(){ int N = 0; scanf("%d", &N); const ll res = fibo(N); printf("%lld", res); return 0; }