第一题：给立方体排序的小明
1.题目
2.问题分析与算法设计思路
由可以交换两个相邻的立方体，很容易想到冒泡排序的算法。我们只需要在冒泡排序的过程中记录需要交换的次数即可。
3.算法实现
有一些注释起来的代码，是我之前用于debug的，忽略即可
#include<iostream>using namespace std;
int SortMP(int a[], int len_a){ int count=0; //需要进行交换的次数 int end=len_a - 2; //遍历尾 for(int i=0; i < len_a - 1; i++){ for(int j=0; j <= end; j++){ if(a[j] > a[j+1]) { int t = a[j]; a[j] = a[j+1]; a[j+1] = t; count++; } } end--; } return count;}
int main(){ int a[10000]={}; int m=0; //测试用例数 int n=0; //立方体数
//开始 cin >> m; for(int i = 0; i < m; i++) { int count=0; //交换次数 int n=0; //立方体数 cin >> n; int count_max=0; //能够接受的最大交换次数 count_max = n * (n - 1) / 2 - 1; //输入立方体 for(int j = 0; j < n; j++){ cin>>a[j]; } //测试输入// cout<<"input"<<endl;// for(int j = 0; j < n; j++){// cout<<a[j]<<' ';// } // cout<<endl; //排序 count = SortMP(a, n);// cout<<"count "<<count<<endl; //测试“排序成功”// cout<<"after sort"<<endl;// for(int j = 0; j < n; j++){// cout<<a[j]<<' ';// } // cout<<endl; //将立方体置空 for(int j = 0; j < n; j++){ a[j] = 0; } //测试交换次数// cout<<"count "<<count<<endl;// cout<<"count_max "<<count_max<<endl; //判断交换次数 if(count <= count_max){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } return 0;}
复制代码
4.运行结果
我这里是每读取一组测试数据，就输出一个结果。这和读完所有数据后在开始输出结果的效果其实是一样的。
5.算法分析
算法的时间复杂度即为冒泡排序的时间复杂度：o(n2)。题中n<=5∗104，该时间复杂度应该还是可以接受的。
第二题：同时整除的数
1.题目
2.问题分析与算法设计思路
可以每一个种输出结果都使用一个if语句进行判断，这样思路会很简单而清晰。但显然，对于 3、5、7 的输出与否，都是可以单独判断的，因此我这里尝试的是将几种情况的输出联系起来。
3.算法实现
#include<iostream>using namespace std;
int main(){ int num=0;//输入的整数 bool by3=0;//能否被3整除 bool by5=0; bool by7=0; int flag=0;//是否已经被更小的数字整除（用来控制空格的输出） cin>>num; if(num % 3 ** 0) by3 = 1; if(num % 5 ** 0) by5 = 1; if(num % 7 ** 0) by7 = 1; if(by3) { cout<<"3"; flag=1; } if(by5) { if(flag) cout<<" "; cout<<"5"; flag=1; } if(by7) { if(flag) cout<<" "; cout<<"7"; } if(!by3 && !by5 && !by7) cout<<"n"; return 0;}
复制代码
4.运行结果
5.算法分析
这里程序中并不需要循环、递归的复杂的结构，算法的时间复杂度很低，应为：o(1)。
博主主页：CSDN清风莫追
感谢阅读
评论