专栏首页cwl_JavaC++经典算法题-得分排行

C++经典算法题-得分排行

32.Algorithm Gossip: 得分排行

说明

假设有一教师依学生座号输入考试分数,现希望在输入完毕后自动显示学生分数的排行,当然学生的分数可能相同。

解法

这个问题基本上要解不难,只要使用额外的一个排行阵列走访分数阵列就可以了,直接使用下面的程式片段作说明:

        for (i = 0; i < count; i++) {
            juni[i] = 1;
            for (j = 0; j < count; j++) {
                if (score[j] > score[i])
                    juni[i]++;
            }
        }
        printf("得分\t排行\n");
        for (i = 0; i < count; i++) printf("%d\t%d\n", score[i], juni[i]);

上面这个方法虽然简单,但是反覆计算的次数是n^2,如果n值变大,那么运算的时间就会拖长; 改变juni阵列的长度为n+2,并将初始值设定为0,如下所示:

接下来走访分数阵列,并在分数所对应的排行阵列索引元素上加1,如下所示:

将排行阵列最右边的元素设定为1,然后依序将右边的元素值加至左边一个元素,最后排行阵列中的「分数+1」」就是得该分数的排行,如下所示:

这样的方式看起来复杂,其实不过在计算某分数之前排行的人数,假设89分之前的排行人数为x 人,则89分自然就是x+1了,这也是为什么排行阵列最右边要设定为1的原因;如果89分有y人, 则88分自然就是x+y+1,整个阵列右边元素向左加的原因正是如此。

如果分数有负分的情况,由于C/C++或Java等程式语言无法处理负的索引,所以必须加上一个偏移值,将所有的分数先往右偏移一个范围即可,最后显示的时候记得减回偏移值就可以了。

代码示例

#include <stdio.h> 
#include <stdlib.h>
#define MAX 100
#define MIN 0

    int main(void) {
        int score[MAX+1] = {0}; int juni[MAX+2] = {0}; int count = 0, i;

        do {
            printf("输入分数,-1结束:"); scanf("%d", &score[count++]);
        } while(score[count-1] != -1); count--;

        for(i = 0; i < count; i++) juni[score[i]]++;
        juni[MAX+1] = 1;

        for(i = MAX; i >= MIN; i--)
            juni[i] = juni[i] + juni[i+1]; printf("得分\t排行\n");
        for(i = 0; i < count; i++)
            printf("%d\t%d\n", score[i], juni[score[i]+1]);

        return 0;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大数据-Hive分区表

    在大数据中,最常用的一种思想就是分治,我们可以把大的文件切割划分成一个个的小的文件,这样每次操作一个小的 文件就会很容易了,同样的道理,在hive当中也是支持这...

    cwl_java
  • 快速学习Oracle-Rownum与分页查询

    但是我们不能取到中间几行,因为rownum不支持大于号,只支持小于号,如果想 实现我们的需求怎么办呢?答案是使用子查询,也正是oracle分页的做法。

    cwl_java
  • 3分钟速读原著《Java并发编程的艺术》(三)

    cwl_java
  • 深入volatile关键字

    在Java多线程中,有一个特殊的关键字volatile,这个通常成为一个“轻量级锁”,下面我们就来深入的了解这个关键的作用和原理。

    付威
  • SAP最佳业务实践:生产订单拆分-按库存生产(248)-3生产订单处理1

    image.png 生产订单处理 MD04创建生产订单 创建不含外部处理工序的生产订单。 已生成装配成品 (F248-1) 的生产订单。 后勤®生产 ®物料需...

    SAP最佳业务实践
  • Jmeter阶梯压测聚合报告分阶梯汇总显示

    jmeter技术研究
  • java语音聊天室原形的实现

            原本以为从 麦克风 上获得音频输入很复杂,原来javaSound已经封装的很简单了。         可以使用AudioCapture来完成。

    田春峰-JCJC错别字检测
  • “西瓜书”——第二章_模型评估与选择

    习题 注: 其中: 真正例(TP)【好的西瓜,模型认为是好瓜】 假正例(FP)【坏的西瓜,模型认为是好瓜】 假反例(FN)【好的西瓜,模型认为是坏瓜】 真...

    YingJoy_
  • python与zmq系列(2)

    本系列的内容,参考了电子工业出版社出版的《ZeroMQ云时代极速消息通信库》这本书的内容编排,如果你想阅读书籍,我只告诉你原价108元。

    py3study
  • Java并发编程的艺术(五)——中断

    什么是中断? 在Java中没有办法立即停止一条线程,然而停止线程却显得尤为重要,如取消一个耗时操作。因此,Java提供了一种用于停止线程的机制——中断。 中断...

    大闲人柴毛毛

扫码关注云+社区

领取腾讯云代金券