The 14th Blue Bridge Cup Training Camp——Practice problem-solving stage (disorder stage)—basic practice Fibonacci sequence

The 14th Blue Bridge Cup Training Camp——Practice problem-solving stage (disorder stage)—basic practice Fibonacci sequence

Table of contents

The 14th Blue Bridge Cup Training Camp——Practice problem-solving stage (disorder stage)—basic practice Fibonacci sequence

foreword

Basic Exercise Fibonacci Sequence

C language

C++ language

Java language

Python language

Summarize

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.

Tags: Java Algorithm Python C++

Posted by jonners on Wed, 15 Feb 2023 01:38:13 +0530