第一题：给立方体排序的小明
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 ( n 2 ) o(n^2)o(n
2
)。题中n < = 5 ∗ 1 0 4 n<=5*10^4n<=5∗10
4
，该时间复杂度应该还是可以接受的。
第二题：同时整除的数
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 ) o(1)o(1)。
