AlgorithmCode/fib.cpp at master · ZMK112/AlgorithmCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>

// int fib2(int n){
//     if(n == 0){
//         return 0;
//     }
//     else if(n == 1)
//     {
//         return 1;
//     }
//      else
//      {
//         return fib(n - 1) + fib(n - 2);
//      }

// }

int fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if(n == 1){
        return 1;
    }
    else
    {
        long long fib_one = 1;
        long long fib_two = 0;
        long long fibn = 0;
        for (int i = 2; i <= n; i++)
        {
            fibn = (fib_one + fib_two)%1000000007;
            fib_two = fib_one;
            fib_one = fibn;
        }
        return fibn;
    }
}

int numWays(int n)
{
    if(n == 0){
        return 1;
    }
    if (n == 1){
        return 1;
    }
    int one = 1;
    int two = 1;
    int way = 0;
    for (int i = 2; i <= n; i++)
    {
        way = (one + two) % 1000000007;
        one = two;
        two = way;
    }
    return way;
}


int main()
{
    int c = numWays(2);
    printf("%d",c);
    return 0;
}