devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法设计与分析实验报告-分治法相关练习题_试给出用分治法求某集合中元素值为偶数的元素个数的程序代码。

作者：知新_RL | 2024-05-19 11:56:47

赞

踩

试给出用分治法求某集合中元素值为偶数的元素个数的程序代码。

 校课程的简单实验报告。

算法设计与分析实验报告-递归与分治策略

算法设计与分析实验报告-动态规划算法

算法设计与分析实验报告-贪心算法 

        dijkstra迪杰斯特拉算法（邻接表法）

算法设计与分析实验报告-回溯法

算法设计与分析实验报告-分支限界法 

算法设计与分析实验报告-分治法相关练题

北京大学出版社-算法设计与分析

五、程序题

1. 试给出用分治法求某集合中元素值为偶数的元素个数的程序代码。

2. 试给出用i分治法求某集合中元素值为最大数的程序代码。

3. 根据分治法求某集合中元素值大于指定值的元素个数。要求给出分治法解决该问题的基本思路并给出递归实现代码。

4. 根据分治法求解棋盘覆盖问题。试写出该程序代码，可以只写函数

5. 给出归并排序的核心代码，并分析归并排序的时间复杂性。

6. 给出快速排序算法，以及快速排序的Partition函数。

7. 给出分治法设计的循环赛日程表。

8. 用分治法写出有序序列进行二分查找的过程

9. 对给定的含有n个元素的无序序列，求这个元素中第K小的元素

分治法求某集合中元素值大于指定值的元素个数。

基本思路：将求解范围l~r分为两半，变成2个子问题，递归求解两个子问题，再将两个子问题的解加和得到原问题解。 
递归出口：只有一个元素时与指定元素进行比较返回答案1或0. 
递归关系：两个子问题的解相加为原问题解。 
参数设置：数组arr，起始位置l，终点位置r，指定比较值x。
1. 试给出用分治法求某集合中元素值为偶数的元素个数的程序代码。
  1. //
  2. // Created by GiperHsiue on 2022/10/17.
  3. //
  4. // 分治法求某集合中元素值为偶数的元素个数。
  5. #include <iostream>
  6. using namespace std;
  7. int check(int arr[], int l, int r){
  8.     if(l == r) return arr[l] % 2 ? 0 : 1;
  9.     int mid = l + r >> 1;
  10.     return check(arr, l, mid) + check(arr, mid + 1, r);
  11. }
  12. int main(){
  13.     int n;
  14.     cin >> n;
  15.     int *arr = new int[n];
  16.     for(int i = 0; i < n; i ++) cin >> arr[i];
  17.     cout << check(arr, 0, n - 1);
  18.     return 0;
  19. }

运行如下：

2. 试给出用分治法求某集合中元素值为最大数的程序代码。
  1. //
  2. // Created by GiperHsiue on 2022/10/17.
  3. //
  4. //分治法求某集合中元素值为最大数。
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8. int check(int arr[], int l, int r){
  9.     if(l == r) return arr[l];
  10.     int mid = l + r >> 1;
  11.     return max(check(arr, l, mid), check(arr, mid + 1, r));
  12. }
  13. int main(){
  14.     int n;
  15.     cin >> n;
  16.     int *arr = new int[n];
  17.     for(int i = 0; i < n; i ++) cin >> arr[i];
  18.     cout << check(arr, 0, n - 1);
  19.     return 0;
  20. }

测试如下：

3. 根据分治法求某集合中元素值大于指定值的元素个数。要求给出分治法解决该问题的基本思路并给出递归实现代码。
  1. //
  2. // Created by GiperHsiue on 2022/10/17.
  3. //
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. int check(int arr[], int l, int r, int x){
  8.     if(l == r) return arr[l] > x ? 1 : 0;
  9.     int mid = l + r >> 1;
  10.     return check(arr, l, mid, x) + check(arr, mid + 1, r, x);
  11. }
  12. int main(){
  13.     int n, x;
  14.     cin >> n;
  15.     int *arr = new int[n];
  16.     for(int i = 0; i < n; i ++) cin >> arr[i];
  17.     cin >> x;
  18.     cout << check(arr, 0, n - 1, x);
  19.     return 0;
  20. }

测试如下：

4. 根据分治法求解棋盘覆盖问题。试写出该程序代码，可以只写函数。
  1. //
  2. // Created by GiperHsiue on 2022/10/20.
  3. //
  4. //棋盘覆盖问题
  5. #include <iostream>
  6. #include <cmath>
  7. #include <iomanip>
  8. using namespace std;
  9. char tile = '1'; // 骨牌的编号
  10. char **board;
  11. //(r,c)棋盘左上角坐标，(sr,sc)特殊方格坐标，size棋盘的行（列）数
  12. void cb(int r, int c, int sr, int sc, int size){
  13.     if(size == 1) return;
  14.     int t = tile++;
  15.     int s = size / 2;
  16.  
  17.     //左上角
  18.     if(sr < r + s && sc < c + s){
  19.         cb(r, c, sr, sc, s);
  20.     } else{
  21.         board[r + s -1][c + s - 1] = t;
  22.         cb(r, c, r + s - 1, c + s - 1, s);
  23.     }
  24.  
  25.     //右上角
  26.     if(sr < r + s && sc >= c + s){
  27.         cb(r, c + s, sr, sc, s);
  28.     } else{
  29.         board[r + s -1][c + s] = t;
  30.         cb(r, c + s, r + s - 1, c + s, s);
  31.     }
  32.  
  33.     //左下角
  34.     if(sr >= r + s && sc < c + s){
  35.         cb(r + s, c, sr, sc, s);
  36.     } else{
  37.         board[r + s][c + s - 1] = t;
  38.         cb(r + s, c, r + s, c + s - 1, s);
  39.     }
  40.  
  41.     //右下角
  42.     if(sr >= r + s && sc >= c + s){
  43.         cb(r + s, c + s, sr, sc, s);
  44.     } else{
  45.         board[r + s][c + s] = t;
  46.         cb(r + s, c + s, r + s, c + s, s);
  47.     }
  48. }
  49. int main(){
  50.     int k;
  51.     cout << "棋盘大小2^k * 2^k 输入K:";
  52.     cin >> k;
  53.     int n = pow(2, k);
  54.     board = new char*[n]; //动态创建棋盘数组
  55.     for(int i = 0; i < n; i ++) board[i] = new char[n];
  56.     for (int i = 0; i < n; ++i) {
  57.         for (int j = 0; j < n; ++j) {
  58.             board[i][j] = '.';
  59.         }
  60.     }
  61.     cout << "输入特殊方格位置：";
  62.     int sr, sc;
  63.     cin >> sr >> sc;
  64.     board[sr][sc] = '*';
  65.     cout << "初始化：" << endl;
  66.     for (int i = 0; i < n; ++i) {
  67.         for (int j = 0; j < n; ++j) {
  68.             cout << setw(4) << board[i][j];
  69.         }
  70.         cout << endl;
  71.     }
  72.     cb(0, 0, sr, sc, n);
  73.     cout << "覆盖后：" << endl;
  74.     for (int i = 0; i < n; ++i) {
  75.         for (int j = 0; j < n; ++j) {
  76.             if(i == sr && j == sc) cout << setw(4) << board[i][j];
  77.             else cout << setw(4) << board[i][j] - '0';
  78.         }
  79.         cout << endl;
  80.     }
  81.     return 0;
  82. }

测试如下：

5. 给出归并排序的核心代码，并分析归并排序的时间复杂性。
  1. //
  2. // Created by GiperHsiue on 2022/10/20.
  3. //
  4. //归并排序
  5. #include <iostream>
  6. using namespace std;
  7. int n;
  8.  
  9. void mergeSort(int a[], int l, int r){
  10.     if(l >= r) return;
  11.     int mid = (l + r) / 2;
  12.     mergeSort(a, l, mid), mergeSort(a, mid + 1, r);
  13.     //merge过程
  14.     int k = 0, i = l, j = mid + 1;
  15.     int *tmp = new int[n]();
  16.     while (i <= mid && j <= r) {
  17.         if (a[i] <= a[j]) tmp[k++] = a[i++];
  18.         else tmp[k++] = a[j++];
  19.     }
  20.     while(i <= mid) tmp[k++] = a[i++];
  21.     while (j <= r) tmp[k++] = a[j++];
  22.     //copy过程
  23.     for (i = l, j = 0;i <= r; i++, j++) {
  24.         a[i] = tmp[j];
  25.     }
  26. }
  27. int main(){
  28.     cin >> n;
  29.     int *a = new int[n]();
  30.     for (int i = 0; i < n; ++i) {
  31.         cin >> a[i];
  32.     }
  33.     mergeSort(a, 0, n - 1);
  34.     for (int i = 0; i < n; ++i) {
  35.         cout << a[i] << ' ';
  36.     }
  37.     return 0;
  38. }

时间复杂度分析：T(n)=2T(n/2)+n

        通过主方法可得T(n)=O(n*logn) 

主方法公式（Master）：

测试如下： 

6. 给出快速排序算法，以及快速排序的Partition函数。
  1. //
  2. // Created by GiperHsiue on 2022/10/20.
  3. //
  4. //快速排序
  5. #include <iostream>
  6. using namespace std;
  7. int Partition(int a[], int l, int r){
  8.     int x = a[l], i = l - 1, j = r + 1;
  9.     while (i < j){
  10.         do i++; while (a[i] < x);
  11.         do j--; while (a[j] > x);
  12.         if (i < j) swap(a[i], a[j]);
  13.     }
  14.     return j;
  15. }
  16. void quickSort(int a[], int l, int r){
  17.     if (l >= r) return;
  18.     int q = Partition(a, l, r);
  19.     quickSort(a, l, q), quickSort(a, q + 1, r);
  20. }
  21.  
  22. int main(){
  23.     int n;
  24.     cin >> n;
  25.     int *a = new int[n];
  26.     for (int i = 0; i < n; ++i) {
  27.         cin >> a[i];
  28.     }
  29.     quickSort(a, 0, n - 1);
  30.     for (int i = 0; i < n; ++i) {
  31.         cout << a[i] << ' ';
  32.     }
  33.     return 0;
  34. }

测试如下：

7. 给出分治法设计的循环赛日程表。
  1. //
  2. // Created by GiperHsiue on 2022/10/20.
  3. //
  4. // 循环赛日程表
  5. #include<iostream>
  6. #include<cmath>
  7. using namespace std;
  8.  
  9. void schedule(int k, int n, int** array);
  10.  
  11. int main()
  12. {
  13.     int k;  // 运动员的人数n=2^k
  14.     cout << "运动员的人数为n（n=2^k），请输入k的值：";
  15.     cin >> k;
  16.     int n = pow(2, k);  // 运动员的人数n=2^k
  17.  
  18.     int** array = new int* [n+1]; // 循环赛日程表，动态数组的创建
  19.     for (int i = 0;i < n+1;i++)
  20.         array[i] = new int[n+1];
  21.  
  22.     // 填充日程表
  23.     schedule(k, n, array);
  24.  
  25.     // 输出日程表
  26.     cout << "\n循环赛日程表为：\n";
  27.     for (int i = 1;i <= n;i++)
  28.     {
  29.         for (int j = 1;j <= n;j++)
  30.             cout << array[i][j] << " ";
  31.         cout << "\n";
  32.     }
  33.     // 删除二维数组
  34.     for (int i = 0;i < n + 1;i++)
  35.         delete[] array[i];
  36.     delete[] array;
  37.     return 0;
  38. }
  39.  
  40. void schedule(int k, int n, int** array)   // 数组下标从1开始
  41. {
  42.     for (int i = 1;i <= n;i++)  // 第一行排1-n
  43.         array[1][i] = i;
  44.  
  45.     int m = 1;  // 用来控制每一次填表时i行j列的起始填充位置
  46.  
  47.     for (int s = 1;s <= k;s++)  // k指分成k大部分进行填充日程表；s指第几大部分
  48.     {
  49.         n = n / 2;
  50.         for (int t = 1;t <= n;t++)  // 第s部分内的循环
  51.         {
  52.             for (int i = m + 1;i <= 2 * m;i++) // 行
  53.             {
  54.                 for (int j = m + 1;j <= 2 * m;j++) // 列
  55.                 {
  56.                     array[i][j + (t - 1) * m * 2] = array[i - m][j + (t - 1) * m * 2 - m];       //左上角等于右下角的值
  57.                     array[i][j + (t - 1) * m * 2 - m] = array[i - m][j + (t - 1) * m * 2];       //左下角等于右上角的值
  58.                 }
  59.             }
  60.         }
  61.         m *= 2;
  62.     }
  63. }

测试如下：

8. 用分治法写出有序序列进行二分查找的过程。
  1. //
  2. // Created by GiperHsiue on 2022/10/20.
  3. //
  4. //二分查找，给出过程
  5. #include <iostream>
  6. using namespace std;
  7. int t = 1;
  8. int BinSearch(int a[], int l, int r, int k){
  9.     int mid = 0;
  10.     if(l <= r){
  11.         mid = (l + r) / 2;
  12.         cout << "第" << t++ << "次比较:" << " mid = " << mid << " a[mid] = " << a[mid] << endl;
  13.         if (a[mid] == k) return mid;
  14.         else if (a[mid] < k) return BinSearch(a, mid + 1, r, k);
  15.         else return BinSearch(a, l, mid - 1, k);
  16.     }
  17.     return -1;
  18. }
  19. int main(){
  20.     int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, k;
  21.     for(auto x:a) cout << x << ' ';
  22.     cout << endl;
  23.     cin >> k;
  24.     int res = BinSearch(a, 0, 9, k);
  25.     cout << "查找结果位置下标：" << res;
  26.     return 0;
  27. }

测试如下：

9. 对给定的含有n个元素的无序序列，求这个元素中第K小的元素。

法1，可以利用快排思想，在快速排序基础上，在每次划分以后，判定所找元素在哪一边，再只对所在一半继续递归进行划分，直到找到确定位置返回。

法2如下；

  1. //
  2. // Created by GiperHsiue on 2022/10/20.
  3. //
  4. // 对给定的含有n个元素的无序序列，求这个序列中第k小的元素。
  5. // 
  6. #include <iostream>
  7. #include <vector>
  8. #include <algorithm>
  9. using namespace std;
  10.  
  11. int select(int a[], int start, int end, int k) {
  12.     int n = end - start;
  13.     if (n < 5) {
  14.         sort(a + start, a + end);
  15.         return a[start + k - 1];
  16.     }
  17.  
  18.     int s = n / 5;
  19.     int *m = new int[s];   //中位数数组
  20.     int i;
  21.     for (i = 0; i < s; i++) {
  22.         sort(a + start + i * 5, a + start + i * 5 + 5);
  23.         m[i] = a[start + i * 5 + 2];
  24.     }
  25.     sort(m, m + i);
  26.     int mid = m[i / 2];
  27.     int *a1 = new int[n];
  28.     int *a2 = new int[n];
  29.     int *a3 = new int[n];
  30.     int num1 = 0, num2 = 0, num3 = 0;
  31.     for (int i = start; i < end; i++) {
  32.         if (a[i] < mid)
  33.             a1[num1++] = a[i];
  34.         else if (a[i] == mid)
  35.             a2[num2++] = a[i];
  36.         else
  37.             a3[num3++] = a[i];
  38.     }
  39.     if (num1 >= k)
  40.         return select(a1, 0, num1, k);
  41.     if (num1 + num2 >= k)
  42.         return mid;
  43.     else
  44.         return select(a3, 0, num3, k - num1 - num2);
  45. }
  46.  
  47. int main() {
  48.     int n;
  49.     cout << "输入个数n：";
  50.     cin >> n;
  51.     int *a = new int[n];
  52.     cout << "输入数组元素：";
  53.     for (int i = 0; i < n; i++)
  54.         cin >> a[i];
  55.     int k;
  56.     cout << "输入所求第几小元素k：";
  57.     cin >> k;
  58.     cout << "第" << k << "小元素为：" << select(a, 0, n, k) << endl;
  59.     delete[] a;
  60.     return 0;
  61. }

测试如下：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/592740
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号