当前位置：首页 > article >正文

【入门篇】欧几里德最差序列——多语言求解版

article 2025/2/22 17:07:39

欧几里德最差序列
在这里插入图片描述
一个题目概念陷阱题，刚看第一眼题目会觉得很简单，用一个数组把结果保存，然后指定下标输出，但是发现测试用例只能运行两个成功。然后仔细阅读题目，你发现n是有范围的（n<=40）,那么这道题没这么简单。接下来你查阅欧几里得的相关资料，发现它的核心算法是求余数，可是得到的结果和这个题目的输入输出更没相关性了。恭喜你，被这道题目坑了！！！其实题目很简单，仔细观察数字规律，你会发现是个斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……因此，题目的核心是计算斐波那契数列的某一项。

斐波那契数列定义：

F(0) = 1
F(1) = 2
对于 n >= 2，F(n) = F(n-1) + F(n-2)

题目解读：

问题要求：

输入一个整数 a1，表示斐波那契数列的第 a1 项。
需要输出斐波那契数列的第 a1 项的值。

斐波那契数列的定义是：

第 1 项：1
第 2 项：2
第 n 项：a[n] = a[n-1] + a[n-2] (对于 n >= 3)

代码解读：

import java.util.Scanner;  // 导入Scanner类，用于输入

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  // 创建Scanner对象，接收输入
        int a1 = sc.nextInt();  // 接收输入的整数a1，表示要求输出的斐波那契数列的项数
        int[] a = new int[41];  // 创建一个数组a，存储前41项斐波那契数列
        
        a[0] = 1;  // 斐波那契数列的第1项
        a[1] = 2;  // 斐波那契数列的第2项
        
        // 使用动态规划方法，计算出斐波那契数列的第3项到第41项
        for (int i = 2; i < a.length; i++) {
            a[i] = a[i - 1] + a[i - 2];  // 每一项是前两项的和
        }
        
        // 输出斐波那契数列的第a1项（数组下标从0开始，因此a1-1）
        System.out.println(a[a1 - 1]);  
        
        sc.close();  // 关闭Scanner对象
    }
}

题目说明：

斐波那契数列从第1项和第2项开始分别是1和2，然后每一项是前两项之和。例如：
- 第1项是1
- 第2项是2
- 第3项是3
- 第4项是5
- 第5项是8
- 第6项是13
- 以此类推。
程序通过动态规划填充数组 a，然后输出第 a1 项。若输入 a1=5，则输出第5项的值8。

测试示例：

输入：

输出：

下面是分别使用 Java、C、C++ 和 Python 实现求解斐波那契数列第 a1 项的代码。

1. Java 实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  // 创建Scanner对象，接收输入
        int a1 = sc.nextInt();  // 接收输入的整数a1，表示要求输出的斐波那契数列的项数
        int[] a = new int[41];  // 创建一个数组a，存储前41项斐波那契数列
        
        a[0] = 1;  // 斐波那契数列的第1项
        a[1] = 2;  // 斐波那契数列的第2项
        
        // 使用动态规划方法，计算出斐波那契数列的第3项到第41项
        for (int i = 2; i < a.length; i++) {
            a[i] = a[i-1] + a[i-2];  // 当前项是前两项的和
        }
        
        System.out.println(a[a1 - 1]);  // 输出第a1项的值，数组下标从0开始，所以用a1 - 1
        sc.close();  // 关闭Scanner对象
    }
}

2. C 实现

#include <stdio.h>

int main() {
    int a1;
    scanf("%d", &a1);  // 输入要查找的斐波那契数列的项数
    
    int a[41];  // 数组a存储前41项斐波那契数列
    a[0] = 1;  // 斐波那契数列的第1项
    a[1] = 2;  // 斐波那契数列的第2项
    
    // 使用动态规划方法计算斐波那契数列的第3项到第41项
    for (int i = 2; i < 41; i++) {
        a[i] = a[i-1] + a[i-2];  // 当前项是前两项的和
    }
    
    printf("%d\n", a[a1 - 1]);  // 输出第a1项，数组下标从0开始，所以用a1 - 1
    return 0;
}

3. C++ 实现

#include <iostream>
using namespace std;

int main() {
    int a1;
    cin >> a1;  // 输入要求的项数
    
    int a[41];  // 数组a存储前41项斐波那契数列
    a[0] = 1;  // 斐波那契数列的第1项
    a[1] = 2;  // 斐波那契数列的第2项
    
    // 使用动态规划方法计算斐波那契数列的第3项到第41项
    for (int i = 2; i < 41; i++) {
        a[i] = a[i-1] + a[i-2];  // 当前项是前两项的和
    }
    
    cout << a[a1 - 1] << endl;  // 输出第a1项，数组下标从0开始，所以用a1 - 1
    return 0;
}

4. Python 实现

# 输入要求的项数
a1 = int(input())

# 创建数组a，存储前41项斐波那契数列
a = [0] * 41
a[0] = 1  # 斐波那契数列的第1项
a[1] = 2  # 斐波那契数列的第2项

# 使用动态规划方法计算斐波那契数列的第3项到第41项
for i in range(2, 41):
    a[i] = a[i-1] + a[i-2]  # 当前项是前两项的和

# 输出第a1项，数组下标从0开始，所以用a1 - 1
print(a[a1 - 1])