棋盘覆盖问题和快速排序问题

算法分析与设计 实验项目 学号 日期 一、实验目的 1．深刻理解并掌握“分治算法”的设计思想； 2．提高应用“分治算法”设计技能； 二、实验要求 实现《棋盘覆盖》问题和《快速排序》问题的分治算法，并进行算法时间复杂性分析。 三、程序清单 //棋盘覆盖算法实验代码 1. #define _CRT_SECURE_NO_WARNINGS //此处以忽略VS 2017所报C4996 error 2. #include 3. 4. int num = 0; 5. int Matrix[100][100]; 6. void chessBoard(int tr, int tc, int dr, int dc, int size); 7. 8. void chessBoard(int tr, int tc, int dr, int dc, int size) 9. { 10. 11. int s, t; 12. if (size == 1) return; 13. s = size / 2; 14. t = ++num; 15. if (dr < tr + s && dc < tc + s) 16. { 17. chessBoard(tr, tc, dr, dc, s); 18. } 19. else 20. { 1

递归与分治算法 222016XXXXXXXX 2024.3.21 班级 姓名 成绩 计科二班 XXXXXXX 21. Matrix[tr + s - 1][tc + s - 1] = t;

22. chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); 23. }

24. if (dr < tr + s && dc >= tc + s) 25. {

26. chessBoard(tr, tc + s, dr, dc, s); 27. }

28. else 29. {

30. Matrix[tr + s - 1][tc + s] = t;

31. chessBoard(tr, tc + s, tr + s - 1, tc + s, s); 32. }

33. if (dr >= tr + s && dc < tc + s) 34. {

35. chessBoard(tr + s, tc, dr, dc, s); 36. } 37. else 38. {

39. Matrix[tr + s][tc + s - 1] = t;

40. chessBoard(tr + s, tc, tr + s, tc + s - 1, s); 41. }

42. if (dr >= tr + s && dc >= tc + s) 43. {

44. chessBoard(tr + s, tc + s, dr, dc, s); 45. } 46. else 47. {

48. Matrix[tr + s][tc + s] = t;

49. chessBoard(tr + s, tc + s, tr + s, tc + s, s); 50. } 51. } 52.

53. int main() 54. {

55. int size, r, c, row, col; 56. printf(\请输入棋盘的行列号\); 57. scanf(\, &size);

58. printf(\请输入特殊方格的行列号\); 59. scanf(\, &row, &col); 60. chessBoard(0, 0, row, col, size); 61.

62. for (r = 0; r < size; r++) 63. {

64. for (c = 0; c < size; c++)

2

65. {

66. printf(\, Matrix[r][c]); 67. }

68. printf(\); 69. } 70.

71. system(\); 72.

73. return 0; 74. }

//快速排序算法代码

1. #include 2. using namespace std;

3. int partition(vector &vi, int low, int up) 4. {

5. int pivot = vi[up]; 6. int i = low - 1;

7. for (int j = low; j < up; j++) 8. {

9. if (vi[j] <= pivot) 10. { 11. i++;

12. swap(vi[i], vi[j]); 13. } 14. }

15. swap(vi[i + 1], vi[up]); 16. return i + 1; 17. }

18. void quickSort(vector &vi, int low, int up) 19. {

20. if (low < up) 21. {

22. int mid = partition(vi, low, up); 23. quickSort(vi, low, mid - 1); 24. quickSort(vi, mid + 1, up); 25. } 26. }

27. void qSort(vector &vi) 28. {

29. quickSort(vi, 0, vi.size() - 1); 30. } 31.

3

32. int main() 33. {

34. int a[99999];

35. int max = 100000, min = 0; 36. srand((unsigned)time(NULL)); 37. for (int i = 0; i < 10000; i++) {

38. a[i] = rand() % (int)(max - min + 1) + min; 39. }

40. vector va(a, a + 9999); 41.

42. cout << \; 43. for (auto x : va) 44. cout << x << \; 45. cout << endl; 46.

47. qSort(va); 48.

49. cout << \; 50. for (auto x : va) 51. cout << x << \; 52. cout << endl; 53. system(\); 54. return 0; 55. }

四、程序测试 //棋盘覆盖算法

4

//快速排序算法 五、运行结果 //棋盘覆盖算法 5