dream.in.java

能以不变应万变是聪明人做事的准则。万事从小事做起,积累小成功,问鼎大成功,是成功者的秘诀。

得分排列

背景:
假設有一教師依學生座號輸入考試分數,現希望在輸入完畢後自動顯示學生分數的排行,當然學生的分數可能相同。

实现思路:
這個問題基本上要解不難,只要使用額外的一個排行陣列走訪分數陣列就可以了,直接使用下面的程式片段作說明:
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等程式語言無法處理負的索引,所以必須加上一個偏移值,將所有的分數先往右偏移一個範圍即可,最後顯示的時候記得減回偏移值就可以了。


实现算法:
 1 package 算法.得分排序;
 2 
 3 import java.io.*;
 4 
 5 public class 得分排序 {
 6     public static void main(String[] args) throws NumberFormatException,
 7             IOException {
 8         final int MAX = 5;
 9         final int MIN = 0;
10         int[] score = new int[MAX + 1];
11         int[] juni = new int[MAX + 2];
12         System.out.println();
13         BufferedReader reader = new BufferedReader(new InputStreamReader(
14                 System.in));
15         int count = 0;
16         do {
17             System.out.print("輸入分數,-1結束:");
18             score[count++= Integer.parseInt(reader.readLine());
19         } while ((score[count - 1!= -1));
20         count--;
21         for(int i = 0; i< count; i++)
22             juni[score[i]]++;//将分数的排行列阵置为1
23         juni[MAX + 1= 1;//将元素下标为MAX+1的位置置为1,也即是第一名,之后不会再改变了
24         for (int i = MAX; i >= MIN; i--)
25             juni[i] = juni[i] + juni[i + 1];//排名阵列元素向左加
26         System.out.println("得分\t排行");
27         for (int i = 0; i < count; i++) {
28             //score[i]的排名对应是juni[score[i] + 1]的值
29             System.out.println(score[i] + "\t" + juni[score[i] + 1]);
30         }
31         /*
32         for (int i = 0; i < count; i++) {
33             System.out.print("score[" + i + "] = " + score[i] +"  "  );
34         }
35         System.out.println();
36         for (int i = 0; i < count; i++) {
37             System.out.print("jnui[" + i + "] = " + juni[i] +"  "  );
38             
39         }
40         System.out.println(juni[5]+"  "+ juni[6]);
41         */
42     }
43 }
44 

posted on 2009-04-12 15:45 YXY 阅读(99) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。


网站导航: