分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net
 
/*
 * 求n个数的中位数 - C++ - by Chimomo
 *
 * 对于一组有有限个数的数据来说，它们的中位数是这样的一种数：
 * 这群数据里的一半的数据比它大，而另外一半数据比它小。
 *
 * 计算有限个数的数据的中位数的方法是：把所有的同类数据按照大小的顺序排列。
 * 如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；
 * 如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。
 */

#include <iostream>
#include <cassert>
#include <stack>
#include <math.h>

using namespace std;

int QuickSortOnce(int a[], int low, int high) {

    // 将首元素作为枢轴。
    int pivot = a[low];
    int i = low, j = high;

    while (i < j) {

        // 从右到左，寻找首个小于pivot的元素。
        while (a[j] >= pivot && i < j) {
            j--;
        }

        // 执行到此，j已指向从右端起首个小于或等于pivot的元素。
        // 执行替换。
        a[i] = a[j];

        // 从左到右，寻找首个大于pivot的元素。
        while (a[i] <= pivot && i < j) {
            i++;
        }

        // 执行到此，i已指向从左端起首个大于或等于pivot的元素。
        // 执行替换。
        a[j] = a[i];
    }

    // 退出while循环，执行至此，必定是i=j的情况。
    // i（或j）指向的即是枢轴的位置，定位该趟排序的枢轴并将该位置返回。
    a[i] = pivot;

    return i;
}

void QuickSort(int a[], int low, int high) {
    if (low >= high) {
        return;
    }

    int pivot = QuickSortOnce(a, low, high);

    // 对枢轴的左端进行排序。
    QuickSort(a, low, pivot - 1);

    // 对枢轴的右端进行排序。
    QuickSort(a, pivot + 1, high);
}

int EvaluateMedian(int a[], int n) {
    QuickSort(a, 0, n - 1);

    if (n % 2 != 0) {
        return a[n / 2];
    } else {
        return (a[n / 2] + a[n / 2 - 1]) / 2;
    }
}

int main() {
    int a[9] = {-5, 345, 88, 203, 554, 1, 89, 909, 1001};
    cout << EvaluateMedian(a, 9) << endl;
    return 0;
}

// Output:
/*
203

*/

实验五    输油管道问题的设计与实现
 
[实验目的]
 
1、掌握分治算法的基本原理
 
2、利用分治策略编程解决输油管道问题
 
[实验内容]
 
问题描述
 
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置，即它们的x 坐标（东西向）和y 坐标（南北向），应如何确定主管道的最优位置， 即使各油井到主管道之间的输油管道长度总和最小的位置？
 
1.请给出分析与解答；
 
2.给出代码和运行结果；
 
3.估算算法的时间复杂度。
 
关于确定主管道的最优位置：由于主管道是由东向西，则主管道的铺设位置只和各油井位置的y坐标有关，要求的最优主管道的位置y坐标应是各个油井y坐标的中位数。
 
反证法证明之：
 
油井数目为奇数：假设主管道的最优位置ｙ坐标值为y_ave,不是各个油井位置ｙ坐标的中位数y_mid，我们可以假设y_ave>y_mid，ｙ坐标小于y_ave的油井数目为m,ｙ坐标大于y_ave的油井数目为n，显然有m>n。当我们将主管道位置下移距离x时(假设此时仍满足y_ave>=y_mid)，各油井到主管道之间的输油管道长度总和应增加nx-mx，显然nx-mx<0(m>n)，即存在一个比_ave更优的位置使得各油井到主管道之间的输油管道长度总和更小，这与假设矛盾。当y_ave>y_mid时，同理可证。
 
油井数目为偶数时：同理可证 。
 
分析：于是此题就转化为了求中位数，关于求中位数，可以先排序，然后中间那个就是所求，但是为了体现分治的思想，同时追求更高的效率，于是本次用随机选择算法，随机选择算法和快速排序有点像。
 
随机选择算法求中位数：如果是奇数个点，就是中间那个，如果是偶数个点，下面代码求的是中间靠左的那个数，当然油田放在中间靠右的那个也可以，各油井到主管道之间的输油管道长度总和是一样的，随机选择算法和快排差不多，先让第一个数找到对应的位置，比它小的放左边，比它大的放它右边，然后如果被排序的位置是中位数，则返回之，如果中位数的位置小于这个位置，就对左区域进行随机选择算法，反之则对右区域进行随机选择算法。
 
测试数据1：
 
5
 
1 2
 
2 2
 
1 3
 
3 -2
 
3 3
 
运行结果截图：
 
 
 
 
测试数据2：
 
6
 1 6
 2 -2
 1 3
 3 -2
 3 3
 1 1
 
运行结果截图：
 
 
 
 
时杂度分析：该算法的时间复杂度为O(n).
 
获取源代码请阅读全文：https://ai.52learn.online/525

#include<stdio.h>
#include<stdlib.h>
int partition(int *a,int l,int r)
{
	int i=l-1;
	int j=r,temp;
	int x=a[r];
	while(1)
	{
		while(a[++i]<x);
		while(x<a[--j])
			if(j==l)
				break;
			if(i>=j)
				break;
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
	}
	temp=a[i];
	a[i]=a[r];
	a[r]=temp;
	return i;
}
int getMax(int *a,int l,int r,int k)
{
	int i;
	if(r<=l)
		return a[l];
	i=partition(a,l,r);
	if(i==(k-1))
		return a[i];
	else
		if(i>=k)
			return getMax(a,l,i-1,k);
		else
			return getMax(a,i+1,r,k);
}
int main()
{
	int i,n,a[10000+16];
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	printf("%d\n",getMax(a,0,n-1,n/2+1));
}

  
// 利用随机化快速排序求带权中位数.cpp : Defines the entry point for the console application.
 //
 //中位数：n个元素集合中，第n/2小的元素，如果是偶数个，则选择中间二个的算术平均值。
 //带权中位数：对于n个互不相同的元素集合x1、x2……xn，其权重依次为w1、w2……wn。按x值排好序后，
 //从第一个元素的权值开始进行权值求和，第一个出现权值和大于等于所有元素的权值和的一半的元素
 //先按利用随机化快速排序算法给关键字排序，然后从排序后元素0开始递推累加每个关键字的权，
 //如果在某一个i时，累加的权大于等于总权的一半，那么这个i就是带权中位数的序号。
 //随机化快速排序的平均时间为nlgn。
 
#include "stdafx.h"
 #include "stdafx.h"
 #include<iostream>
 #include<ctime>
 #define N 100
 using namespace std;
 
struct Node
 {
  double value;
  double weight;
 };
 Node nodes[N];
  //产生一个随即下标，用其对应的数组元素作为比较标准(即一趟快速的主元）
 int random(int m,int n)                       
 {
   srand((unsigned)time(NULL));
   return m + (rand()%(n-m+1));
 }
 //一趟快速排序
 int qartition(Node *nodes,int begin,int end)    
 {
  
   int i = begin-1,j=begin;
   double x = nodes[end].value;
   while(j<end)
   {
    if(nodes[j].value<=x)
    {
     i++;
     Node temp = nodes[i];
     nodes[i]=nodes[j];
     nodes[j]=temp;
    }
    j++;
   }
   Node temp = nodes[end];
   nodes[end]=nodes[i+1];
   nodes[i+1]=temp;
   return i+1;
 }
  //一趟随机化快速排序
 int random_qartition(Node *nodes,int begin,int end)    
 {
    int q = random(begin,end);
    Node temp = nodes[end];
    nodes[end]=nodes[q];
    nodes[q]=temp;
    return qartition(nodes,begin,end);
 }
 //随机化快速排序
 void random_fast_sort(Node *nodes,int begin,int end)   
 {
  if(begin<end)
  {
        int p = random_qartition(nodes,begin,end);
      random_fast_sort(nodes,begin,p-1);
      random_fast_sort(nodes,p+1,end);
  }
 }
 //得到带权的中位数
 Node GetMidWeight(Node *nodes,int begin,int end,double SumWeight)
 {
  double midSum = 0.0;
  int i;
  for(i=begin;i<=end;i++)
  {
   midSum+=nodes[i].weight;
   if(midSum>=SumWeight/2)
    break;
  }
  return nodes[i];
 }
 int _tmain(int argc, _TCHAR* argv[])
 {
  int cases;
  cout<<"请输入案例个数："<<endl;
  cin>>cases;
  while(cases--)
  {
   cout<<"请输入数据个数："<<endl;
   int n;
   cin>>n;
   int i;
   double sum = 0.0;
   cout<<"请输入每一对值和其权值"<<endl;
   for(i=0;i<n;i++)
   {
    cin>>nodes[i].value>>nodes[i].weight;
    sum+=nodes[i].weight;
   }
   random_fast_sort(nodes,0,n-1);
   cout<<"带权中位数为："<<endl;
   Node node = GetMidWeight(nodes,0,n-1,sum);
   cout<<node.value<<endl;
   cout<<"其权值为："<<endl;
   cout<<node.weight<<endl;
  }
  system("pause");
  return 0;
 }