现在的位置: 首页 > 综合 > 正文

算法导论-9-2-c-带权中位数

2013年08月20日 ⁄ 综合 ⁄ 共 2836字 ⁄ 字号 评论关闭

算法导论-9-2其它题目见第9章 排序和顺序统计学

 

题目:

说明如何利用一个线性时间的中位数算法(如9.3节中的SELECT),来在最坏情况下O(n)时间内求出n个数的带权中位数

思考:

step1:利用SELECT中寻找中值的中值的算法,找到主元

step2:用主元把数组分为三段,即A[1..q-1] < A[q] < A[q+1..r]

step3:计算A[1..q-1]<0.5和A[1..q]>=0.5的权值和,是否满足题目中的公式

step4:若满足,A[q]就是所求的数

step5:若不满足,就继续递归使用本算法进行递归查找。偏大就找前半段,偏小就找后半段

代码:

#include <iostream>
using namespace std;

struct node
{
	int value;
	double weight;
};
void Print(node *A, int len)
{
	int i;
	for(i = 1; i <= len; i++)
		cout<<A[i].value<<' ';
	cout<<endl;
	for(i = 1; i <= len; i++)
		cout<<A[i].weight<<' ';
	cout<<endl;
}
/*************最坏情况线性时间的选择**************************************************/
//已经出现很多次了,不解释
int Partition(node *A, int p, int r)
{
	int i = p-1, j;
	for(j = p; j < r; j++)
	{
		if(A[j].value <= A[r].value)
		{
			i++;
			swap(A[i], A[j]);
		}
	}
	swap(A[i+1], A[r]);
	return i+1;
}
node Select(node *A, int p, int r, int i);
//对每一组从start到end进行插入排序,并返回中值
//插入排序很简单,不解释
node Insert(node *A, int start, int end, int k)
{
	int i, j;
	for(i = 2; i <= end; i++)
	{
		node t = A[i];
		for(j = i; j >= start; j--)
		{
			if(j == start)
				A[j] = t;
			else if(A[j-1].value > t.value)
				A[j] = A[j-1];
			else
			{
				A[j] = t;
				break;
			}
		}
	}
	return A[start+k-1];
}
//根据文中的算法,找到中值的中值
node Find(node *A, int p, int r)
{
	int i, j = 0;
	int start, end, len = r - p + 1;
	node *B = new node[len/5+1];
	//每5个元素一组,长度为start到end,对每一组进行插入排序,并返回中值
	for(i = 1; i <= len; i++)
	{
		if(i % 5 == 1)
			start = i+p-1;
		if(i % 5 == 0 || i == len)
		{
			j++;
			end = i+p-1;
			//对每一组从start到end进行插入排序,并返回中值,如果是最后一组,组中元素个数可能少于5
			node ret = Insert(A, start, end, (end-start)/2+1);
			//把每一组的中值挑出来形成一个新的数组
			B[j] = ret;	
		}
	}
	//对这个数组以递归调用Select()的方式寻找中值
	node ret = Select(B, 1, j, (j+1)/2);
	//delete []B;
	return ret;
}
//以f为主元的划分
int Partition2(node *A, int p, int r, node f)
{
	int i;
	//找到f的位置并让它与A[r]交换
	for(i = p; i < r; i++)
	{
		if(A[i].value == f.value)
		{
			swap(A[i], A[r]);
			break;
		}
	}
	return Partition(A, p, r);
}
//寻找数组A[p..r]中的第i大的元素,i是从1开始计数,不是从p开始
node Select(node *A, int p, int r, int i)
{
	//如果数组中只有一个元素,则直接返回
	if(p == r)
		return A[p];
	//根据文中的算法,找到中值的中值
	node f = Find(A, p, r);
	//以这个中值为主元的划分,返回中值在整个数组A[1..len]的位置
	//因为主元是数组中的某个元素,划分好是这样的,A[p..q-1] <= f < A[q+1..r]
	int q = Partition2(A, p, r, f);
	//转换为中值在在数组A[p..r]中的位置
	int k = q - p + 1;
	//与所寻找的元素相比较
	if(i == k)
		return A[q];
	else if(i < k)
		return Select(A, p, q-1, i);
	else
		//如果主元是数组中的某个元素,后面一半要这样写
		return Select(A, q+1, r, i-k);
		//但是如果主元不是数组中的个某个元素,后面一半要改成Select(A, q, r, i-k+1)
}
//寻找数组A[p..r]中的第i大的元素,i是从1开始计数,不是从p开始
node Select2(node *A, int p, int r, double i)
{
	//如果数组中只有一个元素,则直接返回
	if(p == r)
		return A[p];
	//根据文中的算法,找到中值的中值
	node f = Find(A, p, r);
	//以这个中值为主元的划分,返回中值在整个数组A[1..len]的位置
	//因为主元是数组中的某个元素,划分好是这样的,A[p..q-1] <= f < A[q+1..r]
	int q = Partition2(A, p, r, f);
	//转换为中值在在数组A[p..r]中的位置
	int k = q - p + 1;
	//与所寻找的元素相比较
	double w = 0;
	for(int j = p; j <= k; j++)
		w += A[j].weight;
	if(w-A[k].weight < i && w >= i)
		return A[q];
	else if(w-A[k].weight >= i)
		return Select2(A, p, q-1, i);
	else
		//如果主元是数组中的某个元素,后面一半要这样写
		return Select2(A, q+1, r, i-w);
		//但是如果主元不是数组中的个某个元素,后面一半要改成Select(A, q, r, i-k+1)
}
int main()
{
	int n, sum = 0, i;
	cin>>n;
	node *A = new node[n+1];
	int *B = new int[n+1];
	//生成随机数据
	for(i = 1; i <= n; i++)
	{
		A[i].value = rand() % 100;
		do{B[i] = rand() % 100;}while(B[i]==0);
		sum = sum + B[i];
	}
	//将权值规格化
	for(i = 1; i <= n; i++)
		A[i].weight = (double)B[i]/sum;
	//打印生成的数据
	Print(A, n);
	//求带权中位数
	cout<<Select2(A, 1, n, 0.5).value<<endl;
	return 0;
}

 

抱歉!评论已关闭.