大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围:
要求:空间复杂度 ,时间复杂度 ,本题也有时间复杂度 的解法
仅输入一个正整数 n。
输出斐波那契数列中第 n 个数。
4
3
根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案为3。
1
1
2
1
import java.util.* fun main() { val n = readLine()!!.toInt() // val n = 4 println(fib(n)) } private fun fib(n: Int): Int { // 1 1 2 3 5 8 if (n < 1) return 0 if (n == 1) return 1 if (n == 2) return 1 val dp = IntArray(n + 1) dp[1] = 1 dp[2] = 1 for (i in 3..n) { dp[i] = dp[i - 2] + dp[i - 1] } return dp[n] }
public static int getInt(int num){ if(num == 1 || num == 2){ return 1; }else{ return getInt(num-1)+getInt(num-2); } }
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] dp = new int[40]; dp[0] = 1; dp[1] = 1; if(n < 3) { System.out.println(1); }else { for(int i = 2;i < n;i++) { dp[i] = dp[i - 1] + dp[i - 2]; } System.out.println(dp[n-1]); } scan.close(); }
#include <stdio.h> int main() { int n; int arr[500] = {1, 1}; while (scanf("%d", &n) != EOF) { if (n < 1) { return 0; } else { for (int i = 0; i < n; ++i) { if (i == 0 || i == 1) { arr[i] = 1; } else { arr[i] = arr[i - 1] + arr[i - 2]; } } printf("%d", arr[n-1]); } } return 0; }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 //while (in.hasNextInt()) { // 注意 while 处理多个 case /*int a = in.nextInt(); int b = in.nextInt(); System.out.println(a + b);*/ int num = in.nextInt(); int arr[] = new int[num + 1]; arr[1] = 1; arr[2] = 1; for(int i = 3;i <= num ;i++){ arr[i] = arr[i - 1] + arr[i - 2]; } System.out.println(arr[num]); } //} }
while(n = +readline()){ var result =1 ; for(let i=0,x =0,y=1;i<n-1;i++ ){ result = x+y; x=y; y=result; } console.log(result) }
n = int(input()) l = [1,1] if n <=2 : print(1) else: for i in range(3,n+1): c = l[-1]+l[-2] l.append(c) print(l[-1])