Each case contains a number n and you are expected to calculate Fn.(0<=n<=30) 。
For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.
1
1
#include<iostream> using namespace std; int** multi(int** m1, int** m2)//简易矩阵乘法 { int** ans = new int* [2]; for (int t = 0; t < 2; t++) ans[t] = new int[2]; for (int i = 0; i < 2; i++)//i:行 { for (int j = 0; j < 2; j++)//j:列 { int sum = 0; for (int k = 0; k < 2; k++)//k:元素 { sum += m1[i][k] * m2[k][j]; } ans[i][j] = sum; } } return ans; } int fibonacci_3(int n)//矩阵快速幂法O(logn) { int i; int** mat = new int* [2]; for ( i = 0; i < 2; i++) mat[i] = new int[2]; mat[0][0] = 1, mat[0][1] = 1, mat[1][0] = 1, mat[1][1] = 0; /*//求n次幂一般写法 int** base = mat; for ( i = 0; i < n; i++) { mat = multi(mat, base); } reutrn mat[0][1];*/ //快速幂 int** ans = new int* [2]; for (i = 0; i < 2; i++) ans[i] = new int[2]; ans[0][0] = 1, ans[0][1] = 0, ans[1][0] = 0, ans[1][1] = 0;//单位阵 while (n != 0) { if (n % 2 == 1) ans = multi(ans, mat); n /= 2; mat = multi(mat, mat); } return ans[0][1]; } int main() { int n; while (cin>>n) { cout << fibonacci_3(n) << endl; } return 0; }
//简单的递归题,麻烦路过的朋友点个赞拿个徽章~谢谢 #include<iostream> (720)#include<cstdio> using namespace std; int Function(int n){ if(n == 0||n == 1){ return n; }else{ return (Function(n - 1)+Function(n - 2)); } } int main(){ int n; while(scanf("%d",&n) != EOF){ printf("%d",Function(n)); } return 0; }
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); //由于输入的n大小不确定,使用动态数组ArrayList ArrayList<Integer> dp = new ArrayList<>(); dp.add(0); dp.add(1); for (int i = 2; i <= n; i++) // 状态转移方程: dp[n]=dp[n-1]+dp[n-2] dp.add(dp.get(i-1)+dp.get(i-2)); System.out.println(dp.get(n)); } }
if(n>=2){
#include<iostream>
using namespace std;
int tmp[100000]={-1};
int fibonacci(int x)
{
if(x==0) return 0;
if(x==1) return 1;
int a,b;
if(tmp[x-2]!=-1)
a = tmp[x-2];
else
{
a = fibonacci(x-2);
tmp[x-2] = a;
}
if(tmp[x-1]!=-1)
b = tmp[x-1];
else
{
b= fibonacci(x-1);
tmp[x-1] = b;
}
return a+b;
};
int main()
{
for(int i=0;i<100000;i++)
{
tmp[i] = -1;
}
int x;
scanf("%d",&x);
cout<<fibonacci(x)<<endl;
return 0;
}
#include<iostream> using namespace std; int main(){ int n; while(cin>>n){ int a[31]; a[0]=0,a[1]=1; for(int i=2;i<=30;i++) a[i]=a[i-2]+a[i-1]; cout<<a[n]<<endl; } }
#include <stdio.h> long long int Fibonacci(int n){ if(n == 0) return 0; static long long int a = 0; static long long int b = 1; for(int i = 2; i <= n; ++i){ long long int t = a + b; a = b; b = t; } return b; } int main() { int n; scanf("%d",&n); printf("%lld",Fibonacci(n)); return 0; }
#include <iostream> using namespace std; int f(int x){ return x==0||x==1?x:f(x-1)+f(x-2); } int main() { int n; while(cin>>n){ cout<<f(n)<<endl; } return 0; }
#include <stdio.h> int Fun(int n){ if (n == 0) { return 0; } if (n == 1) { return 1; } return Fun(n-1)+Fun(n-2); } int main() { int n; scanf("%d", &n); printf("%d", Fun(n)); return 0; }