Fibonacci Finding:
You're given three numbers: A,B, and N, and all you have to do is to find the number FN where
FO=A
F1=B
FFF-1+F-2 for i>=2
As the number can be very large, output it modulo 109 + 7.
Input Format
The input line containing three integers:A,B and N
separated by space
Constraints
1<=A,B,N<=109
Output Format
output a single integer FN-
Sample Input:
9 1 7
Sample Output:
85
Explanation:
FO=9
F1=1
F2=1+9=10
F3=10+1=11
F4=11+10=21
F5=21+11=32
F6=32+21=53
F7=43+32=85
Sample input
9 1 7
Sample output
85
Program:
#include<stdio.h>
#define MOD 1000000007
long long fib(long long a,long long b,int n){
long long x, y = b, z = a;
for(int i = 2 ; i <= n ; i++){
x = (y + z) % MOD;
z = y;
y = x;
}
return x;
}
int main(){
long long a,b;
int n;
scanf("%lld %lld %d", &a , &b ,&n);
printf("%lld\n",fib(a, b, n));
}
Explanation:
Code defines a function named fib that calculates the nth Fibonacci number, given two starting values a and b. The function takes three parameters: a and b are the first and second terms of the Fibonacci sequence, respectively, and n is the index of the desired term. The function returns the nth Fibonacci number.
The #define MOD 1000000007 statement defines a constant named MOD with the value 1000000007. This is used to compute the result modulo this value, as a way to keep the result within a reasonable range and avoid integer overflow.
The for loop in the fib function starts from the third term (i=2) and iteratively calculates the subsequent terms using the formula F(n) = F(n-1) + F(n-2), where F(n) is the nth term of the Fibonacci sequence. The calculation is done using three variables: x, y, and z, where x holds the current term being calculated, y holds the value of the previous term (F(n-1)), and z holds the value of the term before the previous (F(n-2)).
At each iteration of the loop, the value of x is computed by adding y and z and taking the result modulo MOD. Then, the value of z is updated to y, and the value of y is updated to x. After the loop completes, the function returns the value of x, which is the nth Fibonacci number.
Finally, the main function reads in the values of a, b, and n from the user using scanf, calls the fib function with these values, and prints the result using printf.
0 Comments