主题:[讨论]讨论一个算法问题。
senluo
[专家分:10] 发布于 2010-11-08 12:51:00
一个算法问题:
某城市有1000个名人。某杂志调查,得到该1000个名人的财产数据(不一定连续但假定不重复),
同时又调查了这1000个名人的影响力(1000个数据,同样,不一定连续,假定不重复)。现在,该杂
志要根据这两组数据选出同时最有钱又最有影响力的一位名人。请问您有什么最小运算量的好方法吗?
如果觉得为难,那么再选出最接近“最有钱又最有影响力”的名人又如何?
注:类似于两个排列组合然后序号累加这种已经算是大运算量了。
回复列表 (共3个回复)
沙发
senluo [专家分:10] 发布于 2010-11-08 13:50:00
这问题相当难??不会没人回,然后沉掉吧?
那我再把题意具体化一下看看。这个题目可以这么理解:
有一个1000的三维数组array[ID号][财富][影响力] ,“ID号”指各“名人”0~999,“财富”是一组不重复数据,“影响力”也是一组不重复数据。现在要选出“财富”和“影响力”都最大的那个“ID号”。
需要注意的是,“财富”最大值的那个“名人”不一定就是“影响力”最大,甚至有可能很小。
板凳
聋眼睛瞎耳朵 [专家分:50] 发布于 2010-11-08 21:36:00
你这个问题就有点含糊……什么叫最有钱又最有影响力,这连个判断标准都没有,是两者的和吗??
我想你应该是想知道什么排序算法比较好吧……我个人认为快速排序算法对于元素多且无序的情况,比较实用而迅速。
template<class T>
void QuickSort(T A[],int n)
{
Qsort(A,0,n-1);
}
template<class T>
void QSort(T A[],int left,int right)
{
int i,j;
if(left<right)
{
i=left;j=right;
do
{
do i++;while(A[i]<A[left]);
do j++;while(A[j]>A[left]);
if(i<j) Swap(A[i],A[j]);//这个函数是交换两个元素的值
}
Swap(A[left],A[j]);
QSort(A,left,j-1);
QSort(A,j+1,right);
}
}
3 楼
senluo [专家分:10] 发布于 2010-11-08 23:34:00
不是简单的数值和。所谓的“财富”和“影响力”是彼此无关的两组数。在我理解看来,假如“财富”和“影响力”各自排序,那么两组序号之和最小的那个ID。应该就是所求了。
举个例子:名人甲,拥有最多财富,但是由于其他方面的原因,影响力只不过排到200名之后;而名人乙,虽然财富直排到第三位,但是他的影响力也排到第三位。那么显然后者更接近我们所需要的答案。难道不是这样吗?
至于快速排序,我也知道,我觉得这并不是太合适的答案,只是对排序算法的改进。不过,我没能够想出更好的答案,如果能够不用排序算法或者少用,也许运算量会小很多。哎~~纠结。
PS:只是讨论算法,不需要具体代码实现。
我来回复