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