陣列應用題二

一、#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

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

1

3

5

7

9

11

13

?

?

?

插入一個整數 8

N=7、插入點 i=4

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

1

3

5

7

9

11

13

?

?

?

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

N=8

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

1

3

5

7

?

9

11

13

?

?

將整數 8 插入 X[4]

N=8

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

1

3

5

7

8

9

11

13

?

?

上面的過程中可以寫成:

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

編號

0

1

2

3

4

5

6

7

8

9

Num

7

5

2

?

?

?

?

?

?

?

Time

3

4

1

?

?

?

?

?

?

?

加入一個 5

N=3

編號

0

1

2

3

4

5

6

7

8

9

Num

7

5

2

?

?

?

?

?

?

?

Time

3

5

1

?

?

?

?

?

?

?

再加入一個 3

N=4

編號

0

1

2

3

4

5

6

7

8

9

Num

7

5

2

3

?

?

?

?

?

?

Time

3

5

1

1

?

?

?

?

?

?

至於印出來的部分,只要一個 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", ____, ____);

}

 

上一頁

首頁

下一頁