C语言实现：寻找最接近分数

C语言实现：寻找最接近分数

本文将介绍如何使用C语言编写程序，找到与给定分数最接近且分母不超过指定值的分数。

问题描述

给定三个正整数 x, y, n，你的任务是找到与分数 x / y 最接近的分母不超过 n 的分数。

也就是说要找到一对整数 a, b (1 <= b <= n, 0 <= a) 使得 |x / y - a / b| 尽可能小。

如果有多个满足条件的，输出分母最小的一个。如果依然有多个满足分母最小的，输出分子最小的一个。

输入

三个整数 x, y, n. (1 <= x, y, n <= 10 ^ 5)

输出

题目要求的分数，以'a/b'形式输出。

代码实现

#include <stdio.h>
#include <stdlib.h>

// 求最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 找到与分数x / y最接近的分母不超过n的分数
void findClosestFraction(int x, int y, int n) {
    int minDiff = x; // 初始化最小差值为分子
    int bestDenom = 1; // 初始化最接近的分母为1
    int bestNumer = 0; // 初始化最接近的分子为0

    for (int b = 1; b <= n; b++) {
        int a = b * x / y; // 计算分子
        int diff = abs(x * b - y * a); // 计算差值的绝对值
        if (diff < minDiff) { // 如果差值小于最小差值
            minDiff = diff;
            bestDenom = b;
            bestNumer = a;
        } else if (diff == minDiff) { // 如果差值等于最小差值，比较分母和分子
            if (b < bestDenom) {
                bestDenom = b;
                bestNumer = a;
            } else if (b == bestDenom && a < bestNumer) {
                bestNumer = a;
            }
        }
    }

    printf('%d/%d\n', bestNumer, bestDenom);
}

int main() {
    int x, y, n;
    scanf('%d %d %d', &x, &y, &n);

    findClosestFraction(x, y, n);

    return 0;
}

代码解释

上述程序中，我们使用了一个函数 findClosestFraction 来找到与分数 x / y 最接近的分母不超过 n 的分数。通过遍历所有可能的分母，并计算与给定分数的差值的绝对值，找到差值最小的那个分数。如果有多个满足条件的分数，根据题目要求输出分母最小的一个，如果依然有多个满足分母最小的，输出分子最小的一个。最后使用 printf 函数将结果以 'a/b' 的形式输出。