C++ 中的米迪定理

2025 年 5 月 21 日 | 5 分钟阅读

引言

数学和编程常常结合起来，以高效的方式解决复杂问题。Midy 定理是数论中一个鲜为人知但引人入胜的结果，它揭示了有理数的循环小数。在本文中，我们将探讨 Midy 定理的数学基础、历史、示例，并用 C++ 实现它，以展示其计算意义。

什么是 Midy 定理？

Midy 定理以 19 世纪数学家 E. Midy 的名字命名，它处理某些分数的循环小数展开式。具体来说，它是以下内容

假设一个分数，其中和是互质整数，其小数展开式具有偶数周期。在这种情况下，小数可以分为两个长度相同的部分，它们的和等于，其中是每个部分的长度。

示例

让我们以 1/7 为例。

1/7 的小数展开式为 0.142857‾1/7 = 0.\overline{142857}1/7=0.142857。
重复部分是 142857142857142857，周期为 6（偶数）。
将重复部分分为两半
第一部分：142142142
第二部分：857857857
将两部分相加
142+857=999142 + 857 = 999142+857=999

结论

这两个相等部分的和是 999，这证实了 Midy 定理。

Midy 定理描述了研究循环小数的可能性以及可能在密码学、数值分析等领域找到应用的模式或性质的存在。

Midy 定理的历史背景

Midy 定理由 E. Midy 在 19 世纪首次发现，背景是有理数的小数展开。虽然它不如数论中的其他定理那么出名，但它在循环小数和模算术研究中占有一席之地。Midy 的工作弥合了简单算术与对小数展开周期性更深层次的理解之间的鸿沟。

数学分解

为了应用 Midy 定理，我们必须执行以下操作

检查互质性
分子和分母必须互质才能应用 Midy 定理。它确保分数处于最简形式。
确定循环小数
使用长除法或模算术找到小数展开的重复部分，因为这个重复部分对于应用 Midy 定理至关重要。
检查周期性
确保小数周期为偶数。如果周期为奇数，则 Midy 定理不适用。
分割并求和
将循环小数分成两个相等的部分。检查它们的和是否等于，其中 n 是每个部分的长度。

理解小数周期

终止小数与非终止小数

小数表示某些分数，它们要么终止，要么无限循环。

当且仅当分母只包含 2 和/或 5 作为素因子时，才会产生一个终止小数。
当分母包含其他素因子时，非循环小数具有周期性模式。

非循环小数的周期性

非循环小数的重复模式称为其周期。例如，

周期为 1。
周期为 6。

周期的长度取决于分母，可以通过模算术的一些工作来计算。

在 C++ 中编程实现 Midy 定理

C++ 是解决此问题的好选择，因为它速度快且支持模算术。让我们看一下代码。

步骤 1：设置

创建一个新的 C++ 文件，例如 midys_theorem.cpp，并包含所有必要的头文件

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>   

步骤 2：找到小数周期

可以使用模算术确定的小数周期。除以后的余数会在某个点重复，该点就是周期。

int findDecimalPeriod(int p, int q) {
    std::vector<int> remainders(q, -1);
    int remainder = p % q;
    int position = 0;

    while (remainder != 0 && remainders[remainder] == -1) {
        remainders[remainder] = position;
        remainder = (remainder * 10) % q;
position++;
        }
        return (remainder == 0)? 0 : position - remainders[remainder];
    }   

步骤 3：提取循环小数

一旦找到周期，我们就可以提取循环小数。

std::string getRepeatingDecimal(int p, int q, int period) {
    std::string decimalPart;
    int remainder = p % q;

for (int i = 0; i < period; ++i) {
        remainder *= 10;
        decimalPart += (remainder / q) + '0';
        remainder %= q;
    }

    return decimalPart;
}   

步骤 4：检查 Midy 定理

分离循环小数并检查它们的和

bool verifyMidysTheorem(const std::string& decimalPart) {
    int length = decimalPart.size();

    if (length % 2!= 0) {
        std::cerr << "Period is not even, Midy's theorem does not apply." << std::endl;
        return false;
    }

    int halfLength = length / 2;
std::string part1 = decimalPart.substr(0, halfLength);
    std::string part2 = decimalPart.substr(halfLength);

    int sum = std::stoi(part1) + std::stoi(part2);
    int expectedSum = std::pow(10, halfLength) - 1;

    return sum == expectedSum;
}   

步骤 5：主函数

在主函数中组合所有步骤

int main() {
    int p, q;
    std::cout << "Enter numerator (p): ";
std::cin >> p;
    std::cout << "Enter denominator (q): ";
    std::cin >> q;

    if (std::__gcd(p, q) != 1) {
        std::cerr << "p and q are not coprime." << std::endl;
        return 1;
    }

    int period = findDecimalPeriod(p, q);

if (period == 0) {
        std::cout << "The fraction has a terminating decimal." << std::endl;
        return 0;
    }

    std::cout << "Decimal period: " << period << std::endl;
    std::string repeatingDecimal = getRepeatingDecimal(p, q, period);
std::cout << "Repeating part: " << repeatingDecimal << std::endl;

    if (verifyMidysTheorem(repeatingDecimal)) {
        std::cout << "Midy's theorem is verified." << std::endl;
    } else {
        std::cout << "Midy's theorem does not hold for this fraction." << std::endl;
    }

    return 0;
}   

输出

示例 1

输入

Enter numerator (p): 1
Enter denominator (q): 7   

输出

Decimal period: 6
Repeating part: 142857
Midy's theorem is valid.

示例 2

输入

Enter numerator (p): 1
Enter denominator (q): 6   

输出

The decimal expansion terminates.

Midy 定理的应用

Midy 定理在 C++ 中有以下几个应用

密码学：循环小数有助于解密模算术。
小数分析：寻找可应用于数学定理的非终止小数模式
教学工具：教授数论和有理数的性质。

结论

总之，Midy 定理揭示了循环小数中的秘密关系，它对数论具有巨大价值。它在 C++ 中的实现使抽象数学与计算实用性之间架起了桥梁。这个练习展示了理论与编程的结合如何解决复杂问题，探索引人入胜的模式，并增强对数学原理的理解。

下一主题Morris-traversal-for-preorder-in-cpp

C++ 中的米迪定理

引言

什么是 Midy 定理？

示例

结论

Midy 定理的历史背景

数学分解

理解小数周期

终止小数与非终止小数

非循环小数的周期性

在 C++ 中编程实现 Midy 定理

步骤 1：设置

步骤 2：找到小数周期

步骤 3：提取循环小数

步骤 4：检查 Midy 定理

步骤 5：主函数

Midy 定理的应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的米迪定理

引言

什么是 Midy 定理？

示例

结论

Midy 定理的历史背景

数学分解

理解小数周期

终止小数与非终止小数

非循环小数的周期性

在 C++ 中编程实现 Midy 定理

步骤 1：设置

步骤 2：找到小数周期

步骤 3：提取循环小数

步骤 4：检查 Midy 定理

步骤 5：主函数

Midy 定理的应用

结论

相关帖子

C++ 迷宫

C++ 中的 Giuga 数

C++ Std::pmr::monotonic_buffer_resource