thinksns网站开发网站推广教程

蓝桥杯C++大学B组一个月冲刺记录2024/3/13

规则:每日三题

向日葵的花语是说不出的爱恋
不过今天有点水题了

1.有序分数

给定一个整数 N，请你求出所有分母小于或等于 N，大小在 [0,1] 范围内的最简分数，并按从小到大顺序依次输出。

这个题在被划分为递归一章，是由于Stern-Brocot Tree可以通过中序递归来解决这个问题
但是这个题数据范围仅n <160。所以时间复杂度为O(n²logn)的暴力做法也可以解决这个题

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;typedef pair<int,int>PII;vector<PII>q;int n;bool cmp(PII a,PII b){return a.first * b.second < a.second * b.first;
}int gcd(int a,int b){return b?gcd(b,a % b):a;
}int main(){cin >> n;q.push_back({0,1});for(int i = 1;i <= n; ++i){for(int j = 1;j <= i;++j){if(gcd(i,j) == 1) q.push_back({j,i});}     }sort(q.begin(),q.end(),cmp);for(int i = 0;i < q.size();++i){cout << q[i].first << '/' << q[i].second << endl;}return 0;    
}

以下是y总的递归做法，时间复杂度O(n²)

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n;void dfs(int a, int b, int c, int d)
{if (a + c > n) return;dfs(a, b, a + c, b + d);printf("%d/%d\n", b + d, a + c);dfs(a + c, b + d, c, d);
}int main()
{scanf("%d", &n);puts("0/1");dfs(1, 0, 1, 1);puts("1/1");return 0;
}

2.递归实现指数型枚举

从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。

简单的dfs，比较巧妙的是用二进制编码来记录状态

#include<iostream>using namespace std;const int M = 20;int p[M];
int n;void dfs(int i){if(i > n){for(int i = 1;i <= n; ++i){if(p[i] == 1) cout << i << ' ';else continue;   }cout << '\n';}else{p[i] = 1;dfs(i + 1);p[i] = 0;dfs(i + 1);}}int main(){cin >> n;dfs(1);return 0;
}