【算法作业】实验二：给立方体排序的小明&&同时整除的数

---

第一题：给立方体排序的小明

1.题目

2.问题分析与算法设计思路

由可以交换两个相邻的立方体，很容易想到冒泡排序的算法。我们只需要在冒泡排序的过程中记录需要交换的次数即可。

3.算法实现

有一些注释起来的代码，是我之前用于debug的，忽略即可

#include
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"<
//		for(int j = 0; j < n; j++){
//			cout<
//		} 
//		cout<
		
		//排序 
		count = SortMP(a, n);
//		cout<<"count "<
		
		//测试“排序成功”
//		cout<<"after sort"<
//		for(int j = 0; j < n; j++){
//			cout<
//		}  
//		cout<
		
		//将立方体置空
		for(int j = 0; j < n; j++){
			a[j] = 0;
		} 
		
		//测试交换次数
//		cout<<"count "<
//		cout<<"count_max "<
		 
		//判断交换次数 
		if(count <= count_max){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

4.运行结果

我这里是每读取一组测试数据，就输出一个结果。这和读完所有数据后在开始输出结果的效果其实是一样的。

5.算法分析

算法的时间复杂度即为冒泡排序的时间复杂度：$o(n^2)$。题中$n<=5\ast 10^4$，该时间复杂度应该还是可以接受的。

---

第二题：同时整除的数

1.题目

2.问题分析与算法设计思路

可以每一个种输出结果都使用一个if语句进行判断，这样思路会很简单而清晰。
但显然，对于3、5、7的输出与否，都是可以单独判断的，因此我这里尝试的是将几种情况的输出联系起来。

3.算法实现

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

4.运行结果

5.算法分析

这里程序中并不需要循环、递归的复杂的结构，算法的时间复杂度很低，应为：$o(1)$。

---

个人主页：清风莫追

感谢阅读