斐波那契数列

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]);
    }
    //}
}

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(fib(n));
    }  
    public static int fib(int n){
        int prev =1;
        int next =1;
        if(n==1 || n==2) return 1;
        int cur = 0;
        for(int i = 2; i < n; i++){
            cur = prev + next;
            prev = next;
            next = cur;
        }
        return cur;
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int prev1 = 1;
        int prev2 = 1;
        for (int i = 3; i <= n; i++) {
            int cur = prev2 + prev1;
            prev2 = prev1;
            prev1 = cur;
        }
        System.out.println(prev1);
    }
}

import java.util.Scanner;

public class Main {

    public static void main(String[] argv) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n <= 2) {
            System.out.println(1);
            return;
        }

        int s1 = 1;
        int s2 = 1;
        for (int i = 3; i <= n ; i++) {
            int s3 = s1 + s2;
            s1 = s2;
            s2 = s3;
        }

        System.out.println(s2);
    }


}

import java.util.*;

public class Main{
    public static void main(String[] arg){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        if (n<3) System.out.println(1);
        else{
            int[][] arr = mat(n-2);
            System.out.println(arr[0][0]+arr[0][1]);
        }
    }
    
    public static int[][] mat(int n){
        int[][] arr = new int[2][2];
        if (n==1){
            arr[0][0]  = arr[0][1] = arr[1][0] = 1;  arr[1][1] = 0;
        }
        else {
            if ((n&1)==1) {
                int[][] temp = mat(n-1);
                arr[0][0] = temp[0][0]+temp[1][0];
                arr[0][1] = temp[0][1]+temp[1][1];
                arr[1][0] = temp[0][0];
                arr[1][1] = temp[0][1];
            }
            else {
                int[][] temp = mat(n>>1);
                arr[0][0] = temp[0][0]*temp[0][0]+temp[0][1]*temp[1][0];
                arr[0][1] = temp[0][0]*temp[0][1]+temp[0][1]*temp[1][1];
                arr[1][0] = temp[1][0]*temp[0][0]+temp[1][1]*temp[1][0];
                arr[1][1] = temp[1][0]*temp[0][1]+temp[1][1]*temp[1][1];
            }
        }
        return arr;
    }
}