陣列應用題

一、基本資料結構 ─ 陣列

在許多典型的比賽題目中,題目會要求先輸入一串背景資料,然後再一行一行輸入測試資料,並印出結果。這樣的題目,我們需要用到資料結構來儲存這一串的背景資料,常用的資料結構有陣列(Array)、堆疊(Stack)、佇列(Queue)、鏈結串列(Linked List)等,其中最簡單的就是陣列

在使用陣列上,我們先會評估資料的最大筆數以及資料的型態(字串、整數或浮點數),然後以類似以下的寫法宣告之(以外部變數的方式宣告):

#define MAX 100

int X[MAX];

int n=0;

上面我們多加了一個整數變數 n 來記錄目前已經記錄了幾筆資料。接下來,我們看到輸入幾個整數後,陣列 X 以及整數 n 的變化:

首先我們加入一個整數 10:

N=0

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

?

?

?

?

?

?

?

?

?

?

N=0

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

10

?

?

?

?

?

?

?

?

?

N=1

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

10

?

?

?

?

?

?

?

?

?

上面的過程中,我們先把 10 放進陣列 X 的第 0 個元素中,接下來再把 N 加 1。這個過程可以寫成:

X[0]=10;

n++;

接下來我們再加入一個整數 20:

N=1

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

10

?

?

?

?

?

?

?

?

?

N=1

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

10

20

?

?

?

?

?

?

?

?

N=2

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

X[8]

X[9]

10

20

?

?

?

?

?

?

?

?

上面的過程中,可以寫成:

X[1]=20;

n++;

看了這兩段程式,我們發現, X[編號] 中間的元素編號,剛好就是還沒加 1 之前的 n 的值,所以我們可以把加進一個元素的程式改寫成:

X[n]=數值;

n++;

至於其他不是整數的例子,做法也是類似的,請各位同學自己修改。

 

二、#476 ─ Points in Figures: Rectangles

題目:按這裡

說明:輸入一連串(最多 10 個)矩形的左上及右下座標,然後輸入數個點的座標,印出該點落在那幾個矩形裡面。

我們使用陣列來記錄這最多 10 個矩形的座標,利用前一段的方法,我們宣告成下面的型式:

#define MAX 10

float X1[MAX], Y1[MAX], X2[MAX], Y2[MAX];

int n=0;

接下來可以用:

X1[n]=座標1的X;

Y1[n]=座標1的Y;

X2[n]=座標2的X;

Y2[n]=座標2的Y;

n++;

的方式來增多一個矩形座標的記錄。

這一題分成兩個步驟,先輸入一串矩形座標,再逐一輸入要測試的點的座標,所以我們用兩個迴圈分別完成之。輸入矩形座標的部分,由於要整行輸入,我們先用 gets() 函數讀取一整行,然後用 s[0] 的方式檢查第一個字元,之後用 sscanf(s+1,...) 再把字串 s 的第二個以後的部分取出我們要的部分。整個程式如下:

#include <stdio.h>

#define MAX 10

 

float X1[MAX], Y1[MAX], X2[MAX], Y2[MAX];

int n=0;

 

int main()

{

 char s[80];

 float x, y;

 int i=1, j, k;

 while(1) {

   gets(s);

   if(s[0]=='*') break;

   sscanf(s+1, "%f %f %f %f", &X1[n], &Y1[n], &X2[n], &Y2[n]);

   n++;

 }

 while(1) {

   scanf("%f %f", &x, &y);

   if( (x>=9999.9) && (y>=9999.9) ) break;

   for(j=0, k=0; j<n; j++)

     if( (x>X1[j]) && (x<X2[j]) && (y<Y1[j]) && (y>Y2[j]) ) {

       printf("Point %d is contained in figure %d\n", i, j+1);

       k=1;

     }

   if(k==0) printf("Point %d is not contained in any figure\n", i);

   i++;

 }

 return 0;

}

 

三、#477 ─ Points in Figures: Rectangles and Circles

題目:按這裡

說明:輸入一連串(最多 10 個)矩形座標與圓形的圓心及半徑,然後輸入數個點的座標,印出該點落在那幾個矩形或圓形裡面。

這一題是上一題的延申,而且這一題的程式拿到上一題一樣可以使用。這一題就由各位同學自行解決。(如果真的想不出來,再參考老師的程式)

 

上一頁

首頁

下一頁