0%

算法分析之递归和分治

研一上算法分析期末复习题

1. 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<vector>
using namespace std;

void InsertSort(vector <int> T, int len) {
for (int i = 1; i < len; ++i) {
int key = T[i];
int j = i - 1;
while (j >= 0 && T[j] > key ) {
T[j + 1] = T[j];
j = j - 1;
}
T[j+1] = key;
}
for (int i = 0; i < T.size(); ++i)
cout << T[i] << ",";
cout << endl;
}
int main(void) {
vector <int> v = {10,3,4,5,6,8,9,7,2,1,100,300,200};
cout << v.size() << endl;
InsertSort(v, v.size());
}

2. 快排

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
#include<iostream>
int Paritition1(int A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot) {
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot) {
++low;
}
A[high] = A[low];
}
A[low] = pivot;
//每轮结果显示
for (int i = 0; i < 10; ++i) {
std::cout << A[i] << ",";
}
std::cout << std::endl;
return low;
}

void QuickSort(int A[], int low, int high)
{
if (low < high) {
int pivot = Paritition1(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
int main() {
int A[10] = { 1,9,8,5,3,4,2,7,6,10 };
QuickSort(A, 0, 9);
return 0;
}

3. 顺序统计量(n个数中找打前m大的数字)

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
#include<iostream>
using namespace std;
int Partition(int T[],int low,int high) {
int pivot = T[low];
while (low < high) {
while (low<high && T[high]>pivot) --high;
T[low] = T[high];
while (low < high && T[low] < pivot) ++low;
T[high] = T[low];
}
T[low] = pivot;//or T[right]=pivot
return low;
}
int arrangeRight(int T[], int low, int high,int K) {
int end = high, start = low;
low = Partition(T, low, high);
int num = end - low + 1;
if (num == K)
return low;
else if (num > K)
arrangeRight(T, low + 1, end, K);
else if (end - low + 1 < K)
arrangeRight(T, start, low - 1, K - num);
}
void PrintResult(int T[],int low,int high) {
for (int i = low; i <= high; ++i)
cout << T[i] <<",";
cout << endl;
}
void QuickSort(int T[], int low, int high) {
if (low < high) {
int p = Partition(T, low, high);
QuickSort(T, low, p-1);
QuickSort(T, p + 1, high);
}
}

int main() {
int T[15] = { 6,8,1,3,5,7,4,2,9,10,15,12,11,13,14 };
int low = 0, high = 14, K = 3;
int p = arrangeRight(T, low, high, K);
QuickSort(T, p, high);
PrintResult(T, p, high);
return 0;
}

4. 二路归并排序

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
#include<iostream>
using namespace std;

void merge(int List[], int low, int mid, int high){
//low为第1有序区的第1个元素,mid+1为第2有序区第1个元素且为第1有序区的最后1个元素
int i = low;
//j 指向第 2 有序区的第 1 个元素,high 为第 2 有序区的最后一个元素
int j = mid + 1;
//temp数组暂存合并的有序序列
int* temp = new int[high - low + 1];
//设置临时数组的指示标志 k
int k = 0;
//内存分配失败
if (!temp) {
cout << "数组分配失败!";
exit(0);
}
//顺序选取两个有序区的较小元素,存储到t数组中,因为是递增排序
while (i <= mid && j <= high) {
//较小的元素,存入temp临时数组中
if (List[i] <= List[j]) {
temp[k++] = List[i++];
}
else {
temp[k++] = List[j++];
}
}
//比完之后,假如第1个有序区仍有剩余,则直接全部复制到 temp 数组
while (i <= mid) {
temp[k++] = List[i++];
}
//比完之后,假如第2个有序区还有剩余,则直接全部复制到 temp 数组
while (j <= high) {
temp[k++] = List[j++];
}
//将排好序的序列,重存回到 list 中 low 到 high 区间
for (i = low, k = 0; i <= high; i++, k++) {
List[i] = temp[k];
}
delete[]temp;
}
void mergeSort(int List[], int low, int high){
int mid = (low + high) / 2;
if (low < high){
mergeSort(List, low, mid);
mergeSort(List, mid + 1, high);
merge(List, low, mid, high);
}
}

int main(void){
int source[10] = {1,9,8,5,3,4,2,7,6,10};
mergeSort(source, 0, 9);
for (int i = 0; i < 10; i++) {
cout << source[i] << ',';
}
return 0;
}

5. 逆序对数

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
#include<iostream>
using namespace std;
static int totalpairs = 0;
void StatisticNumpair(int T[], int low, int mid, int high) {
int s = low,m = mid+1;
int* temp = new int[high - low + 1];
int k = 0;
while (s <= mid && m <= high) {
if (T[m] < T[s]) {
temp[k++] = T[m++];
totalpairs += mid - s+1;
}
else {
temp[k++] = T[s++];
}
}
while (s <= mid) {
temp[k++] = T[s++];
}
while (m <= high) {
temp[k++] = T[m++];
}
// 这个复制特别重要,不可写成
//for (int i = low; i <= high; i++)
//T[i] = temp[k];

for (int i = low, k = 0; i <= high; i++, k++) {
T[i] = temp[k];
}

delete[] temp;
}
void ReverseNumpair(int T[],int low,int high) {
int mid = (low + high) / 2;
if (low < high) {
ReverseNumpair(T, low, mid);
ReverseNumpair(T, mid + 1, high);
StatisticNumpair(T, low, mid, high);
}
}
int main() {
int T[9] = { 15,2,6,3,4,5,1,11,10};
ReverseNumpair(T, 0, 8);

cout << totalpairs << endl;

for (int i = 0; i <= 8; ++i) {
cout << T[i] << ",";
}
cout << endl;

return 0;
}

6. 最大,最小元

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
#include <iostream>
using namespace std;
void minmax(int* a, int i, int j, int* min, int* max) {
int lmin, lmax, rmin, rmax, mid;
if (i == j) {
*min = a[i];
*max = a[j];
}
else if (j == i + 1) {
if (a[i] > a[j]) {
*min = a[j];
*max = a[i];
}
else {
*min = a[i];
*max = a[j];
}
}
else {
mid = (i + j) / 2;
minmax(a, i, mid, &lmin, &lmax);
minmax(a, mid + 1, j, &rmin, &rmax);
*min = (lmin > rmin) ? rmin : lmin;
*max = (lmax > rmax) ? lmax : rmax;
}
}
int main() {
int a[] = { 6,10,32,8,19,20,2,100,14 };
int min, max;
minmax(a, 0, 8, &min, &max);
cout << "min:" << min <<" "<< "max:" << max << endl;
return 0;
}

7. 汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
void Hanoi(int n,char src,char mid, char dest){
if (n == 1) {
cout << src << "-->" << dest << endl;
return;
}
Hanoi(n - 1, src, dest, mid);
cout << src << "-->" << dest << endl;
Hanoi(n - 1, mid, src, dest);
return;
}
int main() {
int n;
cin >> n;
Hanoi(n, 'A', 'B', 'C');
return 0;
}

8. 正整数幂乘(a的n次方)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//法一:
#include<iostream>
#include<cmath>
using namespace std;
int calc(int a, int n){
if (n == 1)
return a;
if (n % 2 == 0)
a = pow(calc(a, n / 2),2);
else
a = pow(calc(a, (n - 1) / 2),2)*a;
return a;
}
int main(){
int a, n;
cin >> a >> n;
a = calc(a, n);
cout << a << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//法二:
#include<iostream>
using namespace std;
long long quickpower(long long x, long long y){
long long ans = 1, cnt = x;
while (y){
if (y & 1){
ans *= cnt;
}
cnt *= cnt;
y >>= 1;
}
return ans;
}
int main(){
long long x, y, ans;
cin >> x >> y;
ans = quickpower(x, y);
cout << ans;
return 0;
}

9. Fibonacci数列

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
#include<iostream>
using namespace std;
struct matrix
{
int m[2][2];
}ans,base;

matrix multi(matrix a, matrix b) {
matrix temp;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
temp.m[i][j] = 0;
for (int k = 0; k < 2; ++k) {
temp.m[i][j] += a.m[i][k] * b.m[k][j];
}
}
}
return temp;
}
int fabonacci(int n) {
base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
base.m[1][1] = 0;
ans.m[0][0] = ans.m[1][1] = 1;
ans.m[0][1] = ans.m[1][0] = 0;
while (n) {
if (n & 1) {
ans = multi(ans, base);
}
base = multi(base, base);
n >>= 1;
}
return ans.m[1][0] + ans.m[1][1];
}
int main() {
int n;
while (cin >> n) {
int result = fabonacci(n);
cout << result << endl;
}
return 0;
}

10. 整数的划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int equationCount(int n, int m){
if (n == 1 || m == 1)
return 1;
else if (n < m)
return equationCount(n, n);
else if (n == m)
return 1 + equationCount(n, n - 1);
else
return equationCount(n, m - 1) + equationCount(n - m, m);
}

int main(void){
int n;
while (cin>>n){
cout<<equationCount(n, n)<<endl;
}
return 0;
}