陣列應用題二

一、#10107 ─ What is the Median?

題目：按這裡。

說明：連續輸入一連串(最多 10000 個)整數，每輸入一個數字，即輸出到目前為止的中位數。

要求中位數，必須先將整個輸入的數列排序，再取最中間的一個數或兩個數的平均，我們設計兩個函數 Add() 及 Print()，分別處理輸入數字並排序以及印出中位數的工作，整個主程式的部分如下(黃色底線的部分請自行思考)：

#include <stdio.h>

#define MAX 10000

int X[MAX];

int n=0;

int main()

{

 int a;

 while(1) {

   if(______) break;

   Add(a);

   Print();

 }

 return 0;

}

關於 Add() 函數，我們要把一個整數加到一個整數陣列裡並將之排序，雖然我們可以把它加到後面去，再利用之前學過的排序法把它整個重新排序，不過這樣很浪費時間。因為我們之前的陣列已經排序好了，所以我們只要從頭尋找適當的插入點，把那個數字插進去就行了，這樣會有三個步驟：

1. 從頭尋找適點的插入點
2. 將該插入點以後的數字往後移一格
3. 將該數字插入該點

我們用例子來解說：

原來的陣列

N=7

插入一個整數 8

N=7、插入點 i=4

將 i=4 以後的格子往後移一格

N=8

將整數 8 插入 X[4]

N=8

上面的過程中可以寫成：

void Add(int a)

{

 int i, j;

 for(i=0; i<__; i++)

   if(X[i]>__) break;

 for(j=__; j>=__; j--)

   X[__]=X[__];

 X[__]=a;

 ____;

}

至於 Print() 函數的部分，當 N 是偶數的時候，最中間的那一個數就是中位數。而當 N 是奇數的時候，最中間的兩個數的平均才是中位數，所以我們可以寫成：

void Print()

{

 if( (n%2)==1 )

   printf("%d\n", X[__]);

 else

   printf("%d\n", (X[__]+X[__])/2);

}

二、#484 ─ The Department of Redundancy Department

題目：按這裡。

說明：輸入一連串整數，計算每個數字出現的次數後輸出。

這一題我們需要用兩個陣列，一個記錄出現的數字( Num[] )，另一個記錄出現的次數( Time[] )。每輸入一個數字，便尋找該數字是不是已經記錄在該陣列中，如果是，則將次數加一，如果不是，則在該陣列的最後加上這個數字，例如：

原來的陣列，已經有 3 個 7，4 個 5、1 個 2。

N=3

加入一個 5

N=3

再加入一個 3

N=4

至於印出來的部分，只要一個 for 迴圈就解決了，接下來我們看到整個程式：

#include <stdio.h>

#define MAX 8000

int Num[MAX];

int Time[MAX];

int n=0;

int main()

{

 int a, i;

 while(1) {

   if(scanf("%d", &a)<1) break;

   for(i=0; i<n; i++)

     if(______) break;

   if(i<n) ______;

   else {

     ______;

     ______;

     ______;

   }

 }

 for(____; ____; ____)

   printf("______\n", ____, ____);

}