vs2012网站开发环境,阿勒泰地区住建设局网站,wordpress 公司建站,软件开发系统设计蓝桥杯C大学B组一个月冲刺记录2024/3/13
规则:每日三题 向日葵的花语是说不出的爱恋 不过今天有点水题了 1.有序分数 给定一个整数 N#xff0c;请你求出所有分母小于或等于 N#xff0c;大小在 [0,1] 范围内的最简分数#xff0c;并按从小到大顺序依次输出。 这个题在被划…蓝桥杯C大学B组一个月冲刺记录2024/3/13
规则:每日三题 向日葵的花语是说不出的爱恋 不过今天有点水题了 1.有序分数 给定一个整数 N请你求出所有分母小于或等于 N大小在 [0,1] 范围内的最简分数并按从小到大顺序依次输出。 这个题在被划分为递归一章是由于Stern-Brocot Tree可以通过中序递归来解决这个问题 但是这个题数据范围仅n 160。所以时间复杂度为O(n2logn)的暴力做法也可以解决这个题
#includeiostream
#includevector
#includealgorithmusing namespace std;typedef pairint,intPII;vectorPIIq;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(n2)
#include iostream
#include cstring
#include algorithmusing 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比较巧妙的是用二进制编码来记录状态
#includeiostreamusing 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;
}
