深入理解法里序列：从数学原理到高效代码实现

你好！作为开发者，我们经常需要处理数据排序、生成特定序列或者进行有理数近似计算。今天，我们将深入探讨一个既古老又在现代算法中占有一席之地的数学概念——法里序列。

在这篇文章中，我们不仅会学习什么是法里序列，还将通过大量的实际代码示例（涵盖 C++、Java 和 Python），从零开始构建高效的生成算法。我们会一起探讨其中的数学逻辑，解决潜在的精度问题，并分析如何优化性能。准备好了吗？让我们开始这场关于有理数与秩序的探索之旅。

什么是法里序列？

简单来说，法里序列是针对一个给定的正整数 $n$（我们称之为“阶数”），在 $0$ 到 $1$ 之间生成的一系列特定的分数。

它的核心定义包含以下三个要点：

• 范围限制：序列中的所有分数值必须在 $[0, 1]$ 之间，即从 $0/1$ 开始，到 $1/1$ 结束。
• 分母约束：所有分数的分母必须小于或等于给定的阶数 $n$。
• 既约形式：这是最关键的一点。序列中的每个分数都必须是最简分数（既约分数）。这意味着分子和分母的最大公约数（GCD）必须为 1。例如，对于 $n=4$，分数 $2/4$ 不在序列中，因为它可以化简为 $1/2$；序列只会保留 $1/2$。

数学上，我们将阶数为 $n$ 的法里序列记为 $F_n$。

#### 直观示例

为了让你对法里序列有一个直观的感受，让我们看看前几个阶数的序列是什么样的：

• $n=1$ (F1): $0/1, 1/1$

(只包含 0 和 1)

• $n=2$ (F2): $0/1, 1/2, 1/1$

(中间插入了分母为 2 的最简分数)

• $n=3$ (F3): $0/1, 1/3, 1/2, 2/3, 1/1$

(注意顺序，1/3 < 1/2 < 2/3)

• $n=4$ (F4): $0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1$

(没有 2/4，因为它等于 1/2；没有 4/4，因为它等于 1/1)

• $n=7$ (F7): $0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1$

为什么要关注它？

除了作为数论中的一个优雅结构，法里序列在实际开发中也有很多应用场景：

• 有理数近似：它可以帮我们找到最接近某个无理数的简单分数。
• 福特圆：这是几何学中与法里序列紧密相关的概念，每个分数对应一个相切或分离的圆。
• 算法设计：生成法里序列涉及遍历、筛选（GCD判断）和排序，是练习算法思维的好题目。

—

核心算法思路：暴力破解与筛选

作为开发者，当我们拿到一个需求时，最先想到的往往是最直观的解决方案。生成法里序列也不例外。

我们的基本思路如下：

• 穷举所有可能：生成所有分母 $y$ 从 $2$ 到 $n$，分子 $x$ 从 $1$ 到 $y-1$ 的分数 $x/y$。当然，别忘了固定的端点 $0/1$ 和 $1/1$。
• 筛选最简分数：对于每一个生成的分数，计算分子 $x$ 和分母 $y$ 的最大公约数（GCD）。如果 GCD 等于 1，说明这是最简分数，保留它；否则，丢弃它。
• 排序：将筛选出来的所有分数按照数值从小到大排序。

#### 关键点：分数的比较

在排序时，我们不能直接用 INLINECODEd986eeb9 和 INLINECODE03a3eb53 做浮点数除法，因为计算机的浮点数精度可能会导致错误（例如 $1/3$ 和 $333333/1000000$）。

标准的做法是使用交叉相乘：

要比较 $a/b$ 和 $c/d$，我们只需比较 $a \times d$ 和 $c \times b$。

• 如果 $a \times d < c \times b$，则 $a/b < c/d$。

—

t### 代码实现：直观方案

让我们用代码把这个思路实现出来。我们将提供三种主流语言的版本：C++、Java 和 Python。

#### 1. C++ 实现

在 C++ 中，我们可以利用 INLINECODEaa65bd64 或 INLINECODEaaef99ec 来存储分数，并自定义 sort 函数的比较逻辑。

// C++ program to print Farey Sequence of given order
#include 
#include 
#include  // 用于 sort
using namespace std;

// 定义一个结构体来表示法里序列中的一项 (分数 x/y)
class Term {
public:
    int x, y; // x是分子, y是分母

    // 构造函数
    Term(int x, int y) : x(x), y(y) {}
};

// 自定义比较函数，用于排序
// 核心逻辑：a/b < c/d 等价于 a*d < c*b
bool cmp(Term a, Term b) {
    return a.x * b.y < b.x * a.y;
}

// 计算最大公约数 (GCD) 的辅助函数
// 使用欧几里得算法
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// 生成并打印法里序列的主函数
void farey(int n) {
    // 使用 vector 存储所有的分数项
    vector v;

    // 第一步：遍历所有可能的分母和分子
    // 分母 y 从 2 到 n
    // 分子 x 从 1 到 y-1 (确保分数小于1)
    for (int y = 2; y <= n; ++y) {
        for (int x = 1; x < y; ++x) {
            // 第二步：检查是否为既约分数
            // 如果分子分母互质(GCD为1)，则加入列表
            if (gcd(x, y) == 1)
                v.push_back(Term(x, y));
        }
    }

    // 第三步：排序
    sort(v.begin(), v.end(), cmp);

    // 输出结果
    cout << "0/1 "; // 显式打印第一项
    for (int i = 0; i < v.size(); ++i)
        cout << v[i].x << "/" << v[i].y << " ";
    cout << "1/1" << endl; // 显式打印最后一项
}

// 驱动程序
int main() {
    int n = 7;
    cout << "法里序列 F" << n << " 包含以下元素：" << endl;
    farey(n);
    return 0;
}

#### 2. Java 实现

在 Java 中，我们可以使用 INLINECODEe82e338f 来存储对象，并利用 INLINECODEffeacc5e 配合自定义的 Comparator。

import java.util.*;

// 表示分数 x/y 的类
class Term {
    public int x, y;

    public Term(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class FareyGenerator {

    // 计算 GCD
    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static void farey(int n) {
        List v = new ArrayList();

        // 遍历所有可能的分数
        for (int y = 2; y <= n; ++y) {
            for (int x = 1; x < y; ++x) {
                // 仅保留互质的分数
                if (gcd(x, y) == 1)
                    v.add(new Term(x, y));
            }
        }

        // 使用自定义比较器进行排序
        Collections.sort(v, new Comparator() {
            @Override
            public int compare(Term a, Term b) {
                // 比较逻辑：a*d 与 c*b 的差值
                // 返回负数表示ab
                return a.x * b.y - b.x * a.y;
            }
        });

        // 打印输出
        System.out.print("0/1 ");
        for (int i = 0; i < v.size(); ++i) {
            Term t = v.get(i);
            System.out.print(t.x + "/" + t.y + " ");
        }
        System.out.println("1/1");
    }

    public static void main(String[] args) {
        int n = 7;
        System.out.println("法里序列 F" + n + " 包含以下元素：");
        farey(n);
    }
}

import math

def farey(n):
    # 初始化结果列表，包含首尾两项
    # 这里的列表生成式会生成中间项
    res = []
    
    # 遍历分母 y 从 2 到 n
    for y in range(2, n + 1):
        # 遍历分子 x 从 1 到 y-1
        for x in range(1, y):
            # 检查是否互质
            if math.gcd(x, y) == 1:
                res.append((x, y))
    
    # 排序：利用 lambda 函数进行交叉相乘比较
    # key 指定为计算浮点值也可以，但为了精确性，我们保持分数形式
    # Python 的 sort 接受一个可调用对象，我们可以利用 funtools.cmp_to_key
    # 但为了简单展示，这里使用分数值作为 key（Python 浮点精度对于小范围 n 通常足够）
    # 若追求极致严谨，可使用 cmp_to_key 实现 a*d < c*b 逻辑
    res.sort(key=lambda frac: frac[0] / frac[1])
    
    # 格式化输出
    output_str = "0/1 " + " ".join(f"{x}/{y}" for x, y in res) + " 1/1"
    print(output_str)

if __name__ == "__main__":
    n = 7
    print(f"法里序列 F{n} 包含以下元素：")
    farey(n)