The 14th Blue Bridge Cup Training Camp——Practice problem-solving stage (disorder stage)—basic practice Fibonacci sequence
Table of contents
Basic Exercise Fibonacci Sequence
foreword
Some of the recent articles may be very fragmented, and where they are written, they will be sorted out in detail after a while. Here, other types of questions are arranged in the back row first, because the last test of Lanqiao is the understanding of the logic of the questions. Ability, that is, dp analysis ability, so the main goal is set here, the recent questions will be very scattered, many, basically some dp practice questions from the whole network for secondary training, students preparing for the competition are weak It is not recommended to watch it first, of course, the exception of the quick brain, you can just skip everything before and watch it directly, as long as you have a good math score in high school, then there is no problem, in fact, dp is a summary of the rules, We only need to deduce the mathematical laws corresponding to the topic and then operate directly. It may be a one-dimensional array or a two-dimensional array. Generally speaking, there are many two-dimensional arrays, but if it can be reduced to, it is recommended to reduce it to, because if If you look at the time complexity, you will know what's going on, so here I wish everyone can understand all kinds of disorder, and try to help everyone.
Basic Exercise Fibonacci Sequence
resource constraints
Memory limit: 256.0MB C/C++ time limit: 1.0s Java time limit: 3.0s Python time limit: 5.0s
Problem Description
The recursive formula of the Fibonacci sequence is: Fn=Fn-1+Fn-2, where F1=F2=1.
When n is relatively large, Fn is also very large. Now we want to know what is the remainder of dividing Fn by 10007.
input format
The input contains an integer n.
output format
Output a line containing an integer representing the remainder of dividing Fn by 10007.
Explanation: In this question, the answer is to ask for the remainder of dividing Fn by 10007, so we only need to be able to calculate the remainder, instead of calculating the exact value of Fn first, and then divide the calculated result by 10007 to get the remainder and calculate directly The remainder is often simpler than calculating the original number first and then taking the remainder.
sample input
10
sample output
55
sample input
22
sample output
7704
Data Size and Conventions
1 <= n <= 1,000,000
Solution: It is the rabbit sequence we often see, but the solution needs to use the idea of DP. Here it needs array processing, and the final result needs to be modulo 10007.
C language
You can see that the array and the modulus can be directly operated, but we have to start counting from March.
#include <stdlib.h>
#include <stdio.h>
#define MOD 10007
#define MAXN 1000001
int n, i, F[MAXN];
int main()
{
scanf("%d", &n);
F[1] = 1;
F[2] = 1;
for (i = 3; i <= n; ++i)
F[i] = (F[i-1] + F[i-2]) % MOD;
printf("%d\n", F[n]);
return 0;
}
C++ language
It is almost indistinguishable from the C language.
#include <stdlib.h>
#include <stdio.h>
#define MOD 10007
#define MAXN 1000001
int n, i, F[MAXN];
int main()
{
scanf("%d", &n);
F[1] = 1;
F[2] = 1;
for (i = 3; i <= n; ++i)
F[i] = (F[i-1] + F[i-2]) % MOD;
printf("%d\n", F[n]);
return 0;
}Java language
It looks a little more complicated, but it can also be presented in an array and recursive way, but recursion will cause memory overflow, so it is not recommended.
import java.io.*;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
int f1 = 1, f2 = 1, f3 = 0;
if (n < 3) {
System.out.print("1");
return;
}
for (int i = 3; i <= n; i++) {
if (f1 > 10007)
f1 = f1 % 10007;
if (f2 > 10007)
f2 = f2 % 10007;
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
System.out.print(f3 % 10007);
}
}Python language
It is very convenient to have a list comprehension, and we directly calculate the change process of all contents in a loop. This is the clever solution to the problem.
a, b, x, n = 0, 1, int(input())%20016, 10007
while x > 0:
a, b, x = b%n, a+b, x-1
print(a)
Summarize
We let the Python language show off this topic again. In the process of solving problems, the skills of using Python language can help us solve the most problems in the shortest code. Of course, the premise is that you need to have your own thinking to better control Python. language to write better methods.