给Jim一个整数n(1<n<=100),请Jim返回所有0到1之间(不包括 0和1)满足分母小于等于n的最简分数。分数可以以任意顺序返回。 用结构化程序设计方法编程验证算法的正确性。 输入格式: 输入若干个正整数,最后以0结束,输入数据之间由一个空格分隔。 输出格式: 每行输出对应输入中每个整数对应的计算结果,每个最简分数之间以空格符隔开
时间: 2024-02-13 11:06:05 浏览: 58
读取mnist数据集到numpy数组中,方便python调用.zip
好的,以下是给出的结构化程序设计方法:
1. 读入整数n
2. 如果n等于0,跳转到步骤7
3. 初始化一个空的vector,用于存储所有满足条件的最简分数
4. 枚举所有可能的分子j,对于每个分子j,枚举所有可能的分母i,如果i小于j且i <= n,且i和j互质,则将最简分数(j, i)加入到vector中
5. 输出vector中的所有最简分数,每个最简分数之间以空格符隔开,输出完毕后换行
6. 跳转到步骤1
7. 程序结束
以下是对应的C++代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 求最大公约数
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
vector<pair<int, int>> getFractions(int n) {
vector<pair<int, int>> res;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (gcd(i, j) == 1) {
res.push_back({j, i});
}
}
}
return res;
}
int main() {
int n;
while (cin >> n && n != 0) {
vector<pair<int, int>> res = getFractions(n);
for (auto p : res) {
cout << p.first << "/" << p.second << " ";
}
cout << endl;
}
return 0;
}
```
以上代码中,我们使用了循环结构和条件结构来实现了上述的算法流程。具体来说,我们使用了一个while循环来不断读入整数n,如果n等于0则跳出循环,否则调用`getFractions()`函数得到所有满足条件的最简分数,然后输出即可。
整个程序的结构清晰易懂,也很容易验证其正确性。
阅读全文