有理分数逼近问题题解

题目分析

问题描述：给定浮点数$a$和整数$L$，寻找分子$N$和分母$D$（$1 \leq N,D \leq L$），使得分数$N/D$与$a$的绝对误差最小。若存在多个解，输出其中任意一个。

输入格式：输入包含浮点数$a$和整数$L$（$1 \leq L \leq 10^5$）。
输出格式：输出最优分数的分子和分母$N$ $D$。

算法思路

该问题属于有理分数逼近问题，代码采用贪心调整策略逐步寻找最优解：

1. 初始化分子$top=1$和分母$bottom=1$，从最小分数开始搜索。
2. 比较当前分数$top/bottom$与目标值$a$的大小：
   • 若$top/bottom < a$，则增大分子$top$（使分数接近$a$）。
   • 若$top/bottom \geq a$，则增大分母$bottom$（使分数减小）。
3. 每次调整后计算误差，记录误差最小的分数作为最优解。

代码关键步骤

1. 初始化：分子$top$和分母$bottom$从$1$开始，误差$min$初始化为较大值（如$16$）。
2. 循环调整：
   • 计算当前分数$tmp=top/bottom$。
   • 若$tmp < a$，说明分数偏小，增大分子$top$以接近$a$。
   • 若$tmp \geq a$，说明分数偏大，增大分母$bottom$以减小分数。
3. 误差记录：每次调整前比较误差，若当前误差更小，则更新最优解$ans_n$和$ans_d$。

示例分析

输入：$3.1415926$ $1000$

• 初始$top=1, bottom=1$，分数$1/1=1 < 3.1415926$，$top$增加到$2$。
• 分数$2/1=2 < 3.1415926$，$top$增加到$3$（$3/1=3 < 3.1415926$）。
• $top=4$时，$4/1=4 > 3.1415926$，改为增大$bottom$到$2$，分数$4/2=2 < 3.1415926$，$top$增加到$5$（$5/2=2.5 < 3.1415926$）。
• 继续调整，最终在$top=22, bottom=7$时，分数$22/7 \approx 3.142857$，误差较小，成为最优解。

复杂度分析

• 时间复杂度：$O(L)$，最坏情况下需遍历$top$和$bottom$从$1$到$L$，总循环次数为$O(L)$。
• 空间复杂度：$O(1)$，仅使用常数级变量。

关键点

1. 贪心策略：通过动态调整分子和分母，使分数逐步逼近目标值$a$，适用于$L$较小的场景。
2. 误差比较：每次调整前更新最小误差，确保记录最优解。
3. 边界条件：当$top$或$bottom$超过$L$时终止循环，保证分数的分子和分母不超过限制。

标程

#include <iostream>
using namespace std;
 
int main(){
    double a, tmp, min = 16;
    int top, bottom, L, ans_n, ans_d;
    cin >> a >> L;
    top = bottom = 1;
    while (top <= L && bottom <= L) {
        tmp = (double)top / bottom;
        if (tmp < a) {
            if (a - tmp < min) {  // 误差更小则更新最优解
                min = a - tmp;
                ans_n = top;
                ans_d = bottom;
            }
            top++;  // 分数小于a时增大分子
        } else {
            if (tmp - a < min) {  // 误差更小则更新最优解
                min = tmp - a;
                ans_n = top;
                ans_d = bottom;
            }
            bottom++;  // 分数大于等于a时增大分母
        }
    }
    cout << ans_n << " " << ans_d << endl;
    return 0;
}

总结

该算法通过贪心调整分子和分母，在$O(L)$时间内找到近似分数，逻辑简单且高效。尽管理论上最优有理逼近需使用连分数展开（如渐进分数），但此方法在实际应用中对多数情况有效，尤其适用于编程竞赛中的快速求解。