设数组A[0..n-1]存放着A班n个学生的成绩，试编写一个算法some_score(A)，求n个学生当中取得相同成绩的人数最多的分数?

[汪军]

大家来研究下这个题目,如何实现最好.
从思路到具体代码实现.应该实现什么样的步骤,大家积极参与,互相交流吧,呵呵.

[xue hang]

赫赫，谢谢啦，又出问题了~~~
     我设想用数组a[i]存放成绩中不同的元素 ，b[i]对应a[i]中不同元素的个数。
     比如；A[ ]={a,a,a,a,a,b,b,b,c,c,c,d,d,e,f,f,f};
               a[i]:  a   b   c   d   e   f
               b[i]:  5   3   3   2   1   3
     然后做 b[ ]的排序同时交换a[ ] 中对应a[i]，最后输出{  a[i],b[i]  }  ，
          {  a[i+1],b[i+a]  }   (若b[i]==b[i+1] ) .....

     程序写的有问题，我会及时补上(其实有点繁)(今天作业太多).
    
     最后谢谢 汪军 ，希望你能看到。
     

在06-12-7， 汪军 <hyd...@gmail.com> 写道：

大家来研究下这个题目,如何实现最好.
从思路到具体代码实现.应该实现什么样的步骤,大家积极参与,互相交流吧,呵呵.

[汪军]

我想的办法：b[i]中的0<=i<=100,既计算1分到100分的个数。（更精简的办法：将其中的i的值换成a[i]）然后对b[i]排序，输出最大的b[i]的i值就是分数了。

大家看哪种方法好些

[mady]

如果成绩的种类表较少的话，比如1-100，那么：
定义sc[]，存储某一成绩的计数，下标为这一成绩
定义mc，存储最大的计数值
定义ms[]，存储拥有最大计数值的分值（即sc的下标）列表
定义msp，存储ms[]中已占用空间的偏移量。

sc[]={0,...,0};
mc=0;
ms=[-1,...,-1];
for(i=0;i<n;i++){
sc[A[i]]++;
if(sc[A[i]]>mc){
mc=sc[A[i]];
msp=0;
ms[msp] = A[i];
}else if(sc[A[i]]==mc){
msp++;
ms[msp] = A[i];
}
}

for(i=0;i<=msp;i++){
print(ms[msp]);
}

这样的话，循环一次就够了，也不用排序。

On 12月7日, 下午2时42分, "汪军" <hydi...@gmail.com> wrote:
> 大家来研究下这个题目,如何实现最好.
> 从思路到具体代码实现.应该实现什么样的步骤,大家积极参与,互相交流吧,呵呵.

[xue hang]

 

 

能不能加上注释，或是可执行的源代码 mady?

无上感激。

 

在06-12-8，mady <mad...@hotmail.com> 写道：

[来来去去]

直接用std::map就可以了哈

[mady]

/*
没有C的环境，就用JScript吧，反正算法不变
*/

var msg = "";
var scores = new Array(50);
// 初始化成绩
for(var i=0; i<scores.length; i++)
scores[i] = parseInt(Math.random() * 100);

maxCountScores(scores, output);
msg = scores.toString() + "\n" + msg;

WScript.Echo(msg);

/*
参数：
scores 成绩数组
fnOutput 输出函数
*/

function maxCountScores(scores, fnOutput){
var scoreCount = new Array(); //
各种成绩的计数数组。在C中需要初始化
var maxCount = 0; // 计数的最大值
var maxScores = new Array(); // 计数最大的成绩数组
var offset = -1; //
技术最大的成绩的个数-1，即maxScores的使用空间的最大下标

// 没有检查参数的合法性
var n = scores.length;

for(var i=0;i<n;i++){
/*
在C中不需要if块，可直接写
scoreCount[scores[i]]++;
*/
if(scoreCount[scores[i]])
scoreCount[scores[i]]++;
else
scoreCount[scores[i]] = 1;

/*
如果当前分数的计数值大于"计数的最大值"，则置"计数的最大值"为当前计数值，并且将offset复位
如果当前分数的计数值等于"计数的最大值"，则将offset后移
*/
if(scoreCount[scores[i]]>maxCount){
maxCount = scoreCount[scores[i]];
maxScores[offset=0] = scores[i];
}else if(scoreCount[scores[i]]==maxCount){
maxScores[++offset] = scores[i];
}
}

// 输出结果
output(maxCount);
for(var i=0; i<=offset; i++){
output(maxScores[i]);
}
}

function output(d){
msg += ("\n" + d.toString());
}

On 12月8日, 下午8时58分, "xue hang" <xuerolla...@gmail.com>
wrote:
> 能不能加上注释，或是可执行的源代码 mady?
> 无上感激。
>
> 在06-12-8，mady <mady...@hotmail.com> 写道：

[航]

用c试着写了一个,有不足的地方大家提出来啊,: )
int A[N]；

fn(A[])
{     int a[],b[];
      int i,j,k;
      int mem,count;
     
/*把A[i]中相同的元素放到a[k]，对应的个数放于b[k]*/
      for(i=0,k=0;i!=N-1;k++)
      {   mem=A[i];               /*mem暂时存放A[i]中的元素*/
          A[i]=-1;
          a[k]=mem;                      /*k用来记录A[]种不同元素的个数*/
          for(j=i+1;j<=N-1;j++)
          {   if(a[j]==mem)
              {   count++;
                  a[j]=-1;                /*相同元素置-1*/
              }
          }
          b[k]=count;
          count=1;
          while(a[i]==1) i++;     
      }
   
 /*寻找a[]中最大元素*/
    for(i=0,men=a[0];i<=k-1;i++)
     {   if(men<a[i+1]) 
         {   men=a[i+1];
             j=i+1;
         }
      }
   
 /*输出结果*/
   printf("/tthe max one is %d,sum is %d",a[j],b[j]);
      getch();
}
果然看起来麻烦~~赫赫。对了，这样对原数组A[]，是有破坏性的，是不是要把数据拷贝出来呢？



     

[LegolasKiss]

> 这样的话，循环一次就够了，也不用排序。
>
> On 12月7日, 下午2时42分, "汪军" <hydi...@gmail.com> wrote:
> > 大家来研究下这个题目,如何实现最好.
> > 从思路到具体代码实现.应该实现什么样的步骤,大家积极参与,互相交流吧,呵呵.

可是我觉得应该是计数只关注计数，而排序只关注排序这样的时间复杂度才会低吧，当然没有理论论证。
按照这样的算法，在排序上花的时间是n(如果有n个学生)，如果统计出全部的分数的个数，只需要对100个(假设分数从0－100)数进行排序，可能要快一些。

K.I.S.S~~

[Zheng-Yu]

可以用Hash Table的思想
开个0..MaxStore的Array
然后从头扫一遍成绩 将其对应下表的数组加+1
最后找个最大值，输入下标即可

[chao wang]

在07-1-21，Zheng-Yu <hell...@gmail.com> 写道：