C++请设计算法，求解一个整数n(1<n<=100)返回所有0到1之间（不包括 0和1）满足分母小于等于n的最简分数，分数可以以任意顺序返回。 用结构化程序设计方法编程验证算法的正确性。 输入格式：输入若干个正整数，最后以0结束，输入数据之间由一个空格分隔。 输出格式：每行输出对应输入中每个整数对应的计算结果，每个最简分数之间以空格符隔开。

以下是 C++ 的算法实现：

#include<iostream>
using namespace std;

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

int main() {
    int n;
    while(cin >> n && n != 0) {
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                if(gcd(i, j) == 1) {
                    cout << j << "/" << i << " ";
                }
            }
        }
        cout << endl;
    }
    return 0;
}

首先读入一个整数 n，表示分母不超过 n。然后从 2 开始枚举分母 i，对于每个分母 i，枚举分子 j。若分子和分母互质，则说明这是一个最简分数，输出即可。

相关问题

C++请设计算法,求解一个整数n(1<n<=100)返回所有0到1之间(不包括 0和1)满足分母小于等于n的最简分数,分数可以以任意顺序返回。 用结构化程序设计方法编程验证算法的正确性。 输入格式:输入若干个正整数,最后以

C++实现：

#include <iostream>
#include <vector>
using namespace std;

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

// 求最简分数
void simplify(int& numerator, int& denominator) {
    int divisor = gcd(numerator, denominator);
    numerator /= divisor;
    denominator /= divisor;
}

// 求满足分母小于等于n的最简分数
vector<pair<int, int>> getSimpleFractions(int n) {
    vector<pair<int, int>> fractions;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            simplify(j, i);
            fractions.push_back({j, i});
        }
    }
    return fractions;
}

int main() {
    int n;
    while (cin >> n) {
        auto fractions = getSimpleFractions(n);
        for (auto& f : fractions) {
            cout << f.first << "/" << f.second << " ";
        }
        cout << endl;
    }
    return 0;
}

算法思路：

遍历所有分母小于等于n的分数，将它们化为最简分数并存储起来，最后返回这些最简分数。

验证算法正确性：

当输入n为3时，输出结果为：

1/2 1/3 2/3

符合预期。

给Jim一个整数n(1<n<=100)，请Jim返回所有0到1之间（不包括 0和1）满足分母小于等于n的最简分数。分数可以以任意顺序返回。 请设计算法，求解上述问题。用结构化程序设计方法编程验证算法的正确性。 输入格式： 输入若干个正整数，最后以0结束，输入数据之间由一个空格分隔。 输出格式： 每行输出对应输入中每个整数对应的计算结果，每个最简分数之间以空格符隔开。C++

以下是C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

//辗转相除法求最大公约数
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int main(){
    int n;
    while(cin >> n && n != 0){
        vector<pair<int, int>> res; //记录结果
        for(int i = 1; i < n; i++){
            if(gcd(i, n) == 1){ //分子和分母互质
                res.push_back({i, n});
            }
        }
        for(int i = 0; i < res.size(); i++){
            cout << res[i].first << "/" << res[i].second << " ";
        }
        cout << endl;
    }