寻找与实数分数相等的最简自然数分数及算法优化问题

咱们来逐个解决你的三个问题，给你实用的优化方案和代码修改建议，直接搞定你现在遇到的效率低、精度设置和范围预判问题：

1. 算法效率优化：用连分数法替代暴力枚举 #

你当前的暴力枚举法，每次只给nA或nB+1，遇到需要大数的情况（比如1.0001/1.010001这种比值接近1的场景），速度慢到离谱，完全不实用。连分数法是寻找实数最简分数近似的高效方案，它能快速收敛到目标比值的最简分数，迭代次数比暴力法少几个数量级。

原理简述 #

把目标比值x = rA/rB展开成连分数，截断连分数得到的渐进分数都是最简形式，而且是在分母不超过某个值的前提下最接近x的分数。这种方法天生适合找最简分数，效率极高。

优化后的完整代码 #

#include <iostream>
#include <cmath>
#include <windows.h>
#include <climits>

using namespace std;

// 计算最大公约数，用来化简分数
unsigned long long gcd(unsigned long long a, unsigned long long b) {
    while (b != 0) {
        unsigned long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 连分数法寻找符合精度要求的最简分数
bool findIrreducibleFraction(double targetRatio, unsigned long long maxLimit, 
                            unsigned long long &nA, unsigned long long &nB, double precision) {
    double integerPart = floor(targetRatio);
    double fractionalPart = targetRatio - integerPart;
    
    unsigned long long a = static_cast<unsigned long long>(integerPart);
    // 连分数递推的初始值
    unsigned long long numPrevPrev = 0, numPrev = 1;
    unsigned long long denPrevPrev = 1, denPrev = 0;
    unsigned long long numCurrent = a * numPrev + numPrevPrev;
    unsigned long long denCurrent = a * denPrev + denPrevPrev;

    while (true) {
        // 检查当前分数是否满足精度要求
        double currentRatio = static_cast<double>(numCurrent) / denCurrent;
        if (fabs(currentRatio - targetRatio) <= precision) {
            // 化简成最简分数
            unsigned long long commonDivisor = gcd(numCurrent, denCurrent);
            nA = numCurrent / commonDivisor;
            nB = denCurrent / commonDivisor;
            return true;
        }

        // 检查是否超出unsigned long long范围
        if (numCurrent > maxLimit || denCurrent > maxLimit) {
            return false;
        }

        // 保留你要的进度查看功能：按空格显示当前状态
        if (GetAsyncKeyState(VK_SPACE) & 0x8000) {
            cout << "当前近似值: nA=" << numCurrent << ", nB=" << denCurrent 
                 << ", 比值=" << currentRatio << ", 目标比值=" << targetRatio << endl;
        }

        // 处理下一个连分数项，避免除以0
        if (fractionalPart < 1e-12) break;
        double reciprocal = 1.0 / fractionalPart;
        integerPart = floor(reciprocal);
        fractionalPart = reciprocal - integerPart;
        a = static_cast<unsigned long long>(integerPart);

        // 更新递推式，计算下一组分子分母
        numPrevPrev = numPrev;
        numPrev = numCurrent;
        denPrevPrev = denPrev;
        denPrev = denCurrent;
        numCurrent = a * numPrev + numPrevPrev;
        denCurrent = a * denPrev + denPrevPrev;
    }

    // 最后检查一次最终的分数是否符合要求
    double currentRatio = static_cast<double>(numCurrent) / denCurrent;
    if (fabs(currentRatio - targetRatio) <= precision) {
        unsigned long long commonDivisor = gcd(numCurrent, denCurrent);
        nA = numCurrent / commonDivisor;
        nB = denCurrent / commonDivisor;
        return true;
    }
    return false;
}

int main() {
    double rA, rB;
    cout << "请输入rA和rB: ";
    cin >> rA >> rB;
    double targetRatio = rA / rB;
    // unsigned long long的最大值
    const unsigned long long MAX_LIMIT = ULLONG_MAX;
    // 6位精度的误差阈值
    const double PRECISION = 1e-6;

    unsigned long long nA, nB;
    bool found = findIrreducibleFraction(targetRatio, MAX_LIMIT, nA, nB, PRECISION);

    if (found) {
        cout << "找到最简分数对: nA=" << nA << ", nB=" << nB << endl;
        cout << "当前比值: " << static_cast<double>(nA)/nB << ", 目标比值: " << targetRatio << endl;
    } else {
        cout << "在unsigned long long范围内，未找到符合6位精度要求的分数对。" << endl;
    }

    return 0;
}

2. 如何设置6位精度的比较 #

直接用==比较浮点数是大忌，浮点数本身有精度误差，永远不要这么做！要设置6位精度，应该比较两个比值的绝对误差是否小于1e-6，或者用更严谨的相对误差（适合比值极大或极小的情况）：

• 绝对误差判断（代码里用的就是这个）：

  fabs(currentRatio - targetRatio) <= 1e-6
  

• 相对误差判断（更适合极端比值）：

  fabs((currentRatio - targetRatio) / targetRatio) <= 1e-6
  

两者选一个就行，根据你的实际场景调整。

3. 预先判断unsigned long long范围内是否存在解 #

要预判是否有解，可以从这几个角度入手：

方法1：有限小数的精确判断 #

如果rA和rB都是有限小数（比如665.32、875.1这种），可以先把它们转成整数形式：

1. 找出rA和rB的小数位数最大值k（比如665.32有2位，875.1有1位，k=2）；
2. 把rA和rB都乘以10^k，得到整数A和B（比如66532和8751）；
3. 化简分数A/B，得到最简形式p/q；
4. 如果p和q都不超过ULLONG_MAX，那肯定存在解，就是(p,q)；否则无解。

方法2：无限小数/无理数的近似解预判 #

如果rA/rB是无限小数（比如你的测试用例1.0001/1.010001），那不存在精确相等的自然数对，只能找近似解。这时候可以用狄利克雷逼近定理：对于任意实数x，存在无穷多对整数(p,q)使得|x - p/q| < 1/q²。如果你的精度是1e-6，那么1/q² <= 1e-6 → q>=1000，只要q不超过ULLONG_MAX，就大概率存在符合精度的近似解。

方法3：连分数提前终止检查 #

在连分数迭代过程中，如果当前的分子或分母已经超过ULLONG_MAX，直接判定范围内无解，不用继续迭代了。

测试用例说明 #

• rA=1426.33, rB=12.7：转成整数是142633和1270，化简后是142633/1270，两个数都在unsigned long long范围内，所以有精确解；
• rA=1.0001, rB=1.010001：比值是无限小数，没有精确解，但连分数法能快速找到符合6位精度的近似最简分数。

内容的提问来源于stack exchange，提问作者Hydra Zerg