对任意给定的一个自然数n(n<=10),将分母小于等于n的不可约的真分数按上升次序排序,并且在第一个分数前加0/1,而在最后一个分数后加1/1, 这个序列称为n级的法雷序列。 当n=8时序列为:0/1,1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7/8,1/1。c++
时间: 2023-10-27 20:07:14 浏览: 166
排序算法(用C++描述)
以下是将分母小于等于n的不可约真分数按升序排序,并在第一个分数前加0/1,最后一个分数后加1/1 的 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 求两个数的最大公约数
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// 判断一个分数是否为不可约真分数
bool isProperFraction(int numerator, int denominator) {
int commonDivisor = gcd(numerator, denominator);
return commonDivisor == 1 && numerator < denominator;
}
// 比较两个分数的大小(按升序排序)
bool compareFractions(pair<int, int> a, pair<int, int> b) {
return a.first * b.second < b.first * a.second;
}
// 生成n级的法雷序列
vector<pair<int, int>> generateFareySequence(int n) {
vector<pair<int, int>> fareySequence;
fareySequence.push_back(make_pair(0, 1));
for (int denominator = n; denominator >= 1; denominator--) {
for (int numerator = 1; numerator < denominator; numerator++) {
if (isProperFraction(numerator, denominator)) {
fareySequence.push_back(make_pair(numerator, denominator));
}
}
}
fareySequence.push_back(make_pair(1, 1));
sort(fareySequence.begin(), fareySequence.end(), compareFractions);
return fareySequence;
}
int main() {
int n;
cout << "请输入自然数n(n<=10): ";
cin >> n;
vector<pair<int, int>> fareySequence = generateFareySequence(n);
for (auto fraction : fareySequence) {
cout << fraction.first << "/" << fraction.second << endl;
}
return 0;
}
```
在上述代码中,我们首先定义了一个 `pair<int, int>` 类型的向量 `fareySequence` 来存储分数。然后,我们使用 `generateFareySequence` 函数生成了 n 级的法雷序列,并将其存储在 `fareySequence` 中。最后,我们按顺序输出法雷序列中的每个分数。
请注意,为了使分数能够按升序排序,我们还定义了一个 `compareFractions` 函数来比较两个分数的大小。在输出法雷序列时,我们使用 `fraction.first` 和 `fraction.second` 分别表示分数的分子和分母。
阅读全文