C++请设计算法,求解一个整数n(1<n<=100)返回所有0到1之间(不包括 0和1)满足分母小于等于n的最简分数,分数可以以任意顺序返回。 用结构化程序设计方法编程验证算法的正确性。 输入格式:输入若干个正整数,最后以
时间: 2024-02-27 14:54:01 浏览: 39
C++实现:
```cpp
#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时,输出结果为:
```text
1/2 1/3 2/3
```
符合预期。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)