参考免费微信小程序:皆我百晓生 作答,经由专家-皆知整理回复,如问题解决,望采纳;如仍有疑问,请评论回复。
解决这个问题的关键在于找到与给定的最简真分数最接近的另一个最简真分数。我们可以采用一个相对高效的方法,这个方法基于一个事实:两个分数的接近程度可以通过它们与某个公共分数的差值来衡量,这个公共分数通常是它们的调和平均数附近的某个值。但更实际的算法是遍历所有可能的分数,比较它们与目标分数的差的绝对值,并记录下差值最小的那个。然而,直接遍历会非常低效,所以我们要利用数学特性来优化搜索过程。
算法思路
计算目标分数的倒数:给定分数(N/D),其倒数为(D/N)。因为我们要找的是最接近的分数,寻找的过程可以转化为在倒数的尺度上进行,这样可以更直观地理解接近性,且有助于我们使用线性搜索的策略。
寻找最接近的倒数:理想情况下,我们希望找到一个分数,其倒数与(D/N)相差最小。由于我们要找的分数的分子分母都必须是最简形式,我们实际上是在寻找与(D/N)最接近的、分母不超过32767的所有分数的倒数。
优化搜索:对于每个可能的分母(d)(从1到32767),计算其对应的分子(n = \lceil d \cdot (D/N) \rceil),然后检查这个分数是否已经简化,如果不是最简形式,则继续尝试下一个分母。但是,考虑到效率,我们应该意识到,对于每一个分母,我们实际上是在寻找能最接近(D \cdot d / N)的整数,这个过程可以通过逐步增加分子来逼近,同时确保分子分母的最大公约数为1。
避免重复和无效计算:通过迭代分母,并使用欧几里得算法检查简化,可以有效地找到答案。为了找到数值最小的解,我们应该从(D+1)开始遍历分母,直到找到第一个满足条件的分数。
完整代码实现
// 用于std::gcd
#include <iostream>
#include <algorithm>
using namespace std;
// 函数用于计算最大公约数
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int N, D;
cin >> N >> D;
// 计算目标分数的倒数
double target = static_cast<double>(D) / N;
int minDiff = INT_MAX;
int bestNum, bestDenom;
// 从D+1开始,因为我们希望找到不同于原分数的最简分数
for (int denom = D + 1; denom <= 32767; ++denom) {
// 计算理论上的分子,然后调整以确保最简
int num = static_cast<int>(target * denom) + 1; // 向上取整
while (true) {
if (gcd(num, denom) == 1) { // 当前分数是最简的
double diff = abs(target - static_cast<double>(num) / denom);
if (diff < minDiff) {
minDiff = diff;
bestNum = num;
bestDenom = denom;
}
break; // 找到了最简形式,跳出循环
}
--num; // 否则,尝试减少分子以寻找最简形式
}
}
cout << bestNum << " " << bestDenom << endl;
return 0;
}
这段代码首先读取输入的分数,然后通过遍历可能的分母来寻找最接近的目标分数的倒数所对应的分数,确保每次找到的分数是最简形式的,并且记录下差值最小的那一对分子和分母。注意,这里使用了gcd函数来检查并确保找到的分数是最简的。此算法虽然在最坏情况下时间复杂度较高,但在实际运行中,由于多数情况下的早期终止,效率相对可以接受。