title: 算法设计与分析实验一：带权中位数
date: 2021-05-19

算法设计与分析实验一：带权中位数

1.题目重述
设有n个互不相同的元素 x1,x2,…, xn，每个元素 xi带有一个权值 wi，且∑𝑛 𝑖=1 𝑤𝑖 = 1。若元素 xk满足∑𝑥𝑖<𝑥𝑘 𝑤𝑖 ≤ 1 2 且∑𝑥𝑖>𝑥𝑘 𝑤𝑖 ≤ 1 2，则称元素 xk为 x1,x2,…, xn的带权中位数。请编写一个算法，能够在最坏情况下用 O(n)时间找出 n 个元素的带权中位数。

2.题目分析
基于寻找无序数组第k小个数的select算法，以rand()选出的pivot将数组分为三个部分，并进行前后两部分权值总和的判断。
若leftWeight <=0.5 && rightWeight <=0.5，pivot为带权中位数。否则，若leftWeight > rightWeight，则带权中位数在pivot左侧数组中，将右侧权值赋给pivot，进行递归，leftWeight<= rightWeight同理。

3.程序设计
用Term类存储元素及权值，用Term_array类存储Term动态数组，包括起始指针，数组大小和头尾等。用函数swaparr交换数组内两个元素，用函数copyele复制元素，用函数partition以xiabiaop开始划分，最后用函数isWm检查是否找到带权中位数。用cycle作循环变量，测试20组数据，每组数据用文件的形式输入。

4.代码

  1. #include"iostream"
  2. #include"cstdlib"
  3. #include"fstream"
  4. using namespace std;
  5. class term
  6. {
  7. public:
  8.     double num;
  9.     double weight;
  10. };
  11. class Term_array
  12. {
  13. public:
  14.     term *elmt;
  15.     int num;
  16.     int head;
  17.     int tail;
  18.     Term_array(int Element_num)
  19.     {
  20.         num = Element_num;
  21.         head = 0;
  22.         tail = num - 1;
  23.         elmt = new term[Element_num];//记得中括号
  24.         for (int i = 0; i < Element_num; i++)
  25.         {
  26.             elmt[i].num = 0;
  27.             elmt[i].weight = 0;
  28.         }
  29.     }
  30.     ~Term_array()
  31.     {
  32.         if (elmt)
  33.             delete[]elmt;
  34.     }
  35. };
  36. void swaparr(int ele1, int ele2, Term_array &arr)
  37. {
  38.     double num_tmp = arr.elmt[ele1].num;
  39.     double weight_tmp = arr.elmt[ele1].weight;
  40.     arr.elmt[ele1].num = arr.elmt[ele2].num;
  41.     arr.elmt[ele1].weight = arr.elmt[ele2].weight;
  42.     arr.elmt[ele2].num = num_tmp;
  43.     arr.elmt[ele2].weight = weight_tmp;
  44. }
  45. void copyele(int ele1, int ele2, Term_array &arr)
  46. {
  47.     arr.elmt[ele1].num = arr.elmt[ele2].num;
  48.     arr.elmt[ele1].weight = arr.elmt[ele2].weight;
  49. }
  50. int partition(int p, Term_array &arr)//以下标p开始划分
  51. {
  52.     int start = arr.head;
  53.     swaparr(start, p, arr);//与0号交换位置
  54.     term tmp = arr.elmt[start];
  55.     int l = arr.head; int r = arr.tail;
  56.     while (l < r)
  57.     {
  58.         while (l < r&&arr.elmt[r].num >= tmp.num)
  59.         {
  60.             r--;
  61.         }
  62.         copyele(l, r, arr);
  63.         while (l < r&&arr.elmt[l].num <= tmp.num)
  64.         {
  65.             l++;
  66.         }
  67.         copyele(r, l, arr);
  68.     }
  69.     arr.elmt[l] = tmp;
  70.     return l;
  71. }
  72. int isWm(int &l, Term_array &arr)
  73. {
  74.     int flag = 0;
  75.     double lsum = 0.0;
  76.     double rsum = 0.0;
  77.     for (int i = 0; i < l; i++)
  78.         lsum += arr.elmt[i].weight;
  79.     for (int i = l + 1; i < arr.num; i++)
  80.         rsum += arr.elmt[i].weight;
  81.     if (lsum <= 0.5&&rsum <= 0.5)
  82.         flag = 0;
  83.     else if (lsum < rsum)
  84.         flag = -1;
  85.     else if (lsum > rsum)
  86.         flag = 1;
  87.     return flag;
  88. }
  89. int main()
  90. {
  91.     ifstream input("exp1_in.txt");
  92.     for (int cycle = 0; cycle < 20; cycle++)
  93.     {
  94.         int Element_Num = 0;
  95.         int Wm = 0;
  96.         input >> Element_Num;
  97.         Term_array arr(Element_Num);
  98.         for (int i = arr.head; i <= arr.tail; i++)
  99.         {
  100.             input >> arr.elmt[i].num;
  101.         }
  102.         for (int i = arr.head; i <= arr.tail; i++)
  103.         {
  104.             input >> arr.elmt[i].weight;
  105.         }
  106.         if (arr.num > 1)
  107.         {
  108.             int rand_num = (rand() % (arr.tail - arr.head + 1) + arr.head);//生成随机数
  109.             int pos = partition(8, arr);//随机开始划分
  110.         //接下来判断是否是带权中位数
  111.             int flag = 0;
  112.             while (1)
  113.             {
  114.                 flag = isWm(pos, arr);
  115.                 if (flag == 0)//恰好是带权中位数
  116.                 {
  117.                     Wm = arr.elmt[pos].num;
  118.                     break;
  119.                 }
  120.                 else if (flag == -1)//右边大于左边,在右边找
  121.                 {
  122.                     arr.head = pos + 1;
  123.                     rand_num = (rand() % (arr.tail - arr.head + 1) + arr.head);
  124.                     pos = partition(rand_num, arr);
  125.                 }
  126.                 else if (flag == 1)
  127.                 {
  128.                     arr.tail = pos - 1;
  129.                     rand_num = (rand() % (arr.tail - arr.head + 1) + arr.head);
  130.                     pos = partition(rand_num, arr);
  131.                 }
  132.             }
  133.         }
  134.         else
  135.             Wm = arr.elmt[0].num;
  136.         cout << Wm << endl;
  137.     }
  138.     return 0;
  139. }

5.测试结果
算法设计与分析实验一：带权中位数 - 图1
附：输入文件
链接：https://pan.baidu.com/s/1zGwKLOLE5mTLJXMQg_gC3w
提取码：h0t1