语源科技BlogJava-外包工

程式設計(19)--作业6：堆疊操作模擬程式

外包工 — Sat, 23 Oct 2010 01:53:00 GMT

問題敘述

請你設計一個堆疊操作模擬程式，可提供插入(push)、取出(pop)、查詢(retrieve)、

檢查堆疊是否為滿(isfull)、檢查堆疊是否為空(isempty)等操作。

你的程式應該利用陣列來實作堆疊，並將各項功能寫成函數。

--------
條件限制

1.堆疊最多能儲存10筆資料。
2.當堆疊的內容改變時，請將堆疊的內容顯示出來。
3.當插入或取出、查詢資料時，須考慮堆疊為滿(isfull)或空(isempty)的情形。
4.請提供選單說明供使用者操作
eg.
****** 選單 ********
1. 插入資料
2. 取出資料
3. 查詢資料
4. 顯示堆疊內所有資料
5. 檢查堆疊是否為滿
6. 檢查堆疊是否為空
7. 離開
********************
輸入選項=>

--------------
輸入格式

無檔案輸入,由鍵盤輸入資料。

--------------
輸出格式

無檔案輸出,由營幕輸出資料。

---------------
輸入範例

略
----------
輸出範例

略

void push(int stack [],int &top,int value){
    stack[top]=value;
    top++;
}

int pop(int stack[],int &top){
//put your code here...
}

int retrieve(int stack[],int top){
    return stack[top-1];
}

int isfull(int stack[],int size,int top){
//put your code here....
}

int isempty(int stack[],int top){
    if(top==0)
        return 1;
    else
        return 0;
}

int main(){
const int SIZE 10;
int stack[SIZE],top=0;
/*

put your code here....

*/
}

外包工 2010-10-23 09:53 发表评论

程式設計(18)--作业5：通訊錄

外包工 — Sat, 23 Oct 2010 01:52:00 GMT

問題敘述

請你設計一個通訊錄軟體，可提供新增、刪除、修改、顯示單筆通訊錄之功能。
通訊錄應包括姓名、性別、年齡、電話、地址、郵遞區號....等資料。
你的程式應利用結構(struct)的方式來實作。

--------
條件限制

1.通訊錄最多可儲存20筆資料。
2.請提供選單說明供使用者操作
eg.
****** 選單 ********
1. 新增通訊錄
2. 刪除通訊錄
3. 修改通訊錄
4. 顯示通訊錄
5. 離開
********************
輸入選項=>

--------------
輸入格式

無檔案輸入,由鍵盤輸入資料。

--------------
輸出格式

無檔案輸出,由營幕輸出資料。

---------------
輸入範例

略
----------
輸出範例

略

外包工 2010-10-23 09:52 发表评论

程式設計(17)--作业4：成績處理系統

外包工 — Sat, 23 Oct 2010 01:50:00 GMT

問題敘述

本次段考過後,X老師希望你設計一個程式能幫他統計同學們的成績。
他希望的功能如下:
1.可以輸入全班的N筆學生資料(1<=N<=50),每位學生有三科分數(國、英、數)。
2.可以統計出每位同學的平均成績
3.可以統計出每科成績的全班平均
4.找出每科成績最好的同學
現在請程式功力高強的你幫忙X老師解決他的問題吧!

--------
條件限制

1.1<=N<=50
2.請提供選單說明供使用者操作
eg.
****** Menu ********
1. Input score.
2. Print each student's average.
3. Print the subjects average of the whole class.
4. Print the Top 1 of each subject.
5. Exit
********************
your choice=>

--------------
輸入格式

無檔案輸入,由鍵盤輸入資料。

--------------
輸出格式

無檔案輸出,由營幕輸出資料。

---------------
輸入範例

Please input how many students do you have(1<=N<=50):
3

Please input the score one by one(Chinese,English,Math):
50 60 40
60 70 80
90 80 70

----------
輸出範例

Print each student's average:
No. Chinese English Math Average
1 50 60 40 50
2 60 70 80 70
3 90 80 70 80

Print the subjects average of the whole class:
Chinese English Math Average
66.7 70 63.3 66.7

Print the Top 1 of each subject:
Top 1 of Chinese: No. 3,Score 90
Top 1 of English: No. 3,Score 80
Top 1 of Math: No. 2,Score 80

每個人的分數可用二維陣列 int score[50][3] 來儲存
平均成績可儲存在 float avg[50]
科目平均可儲存在 float subject_avg[3]

例:
//先將所有陣列初始值設為0,否則會有不可預期的後果
for(int i=0;i<50;i++)
    for(int j=0;j<3;j++)
       score[i][j]=0;

for(int k=0;k<50;k++)
    avg[k]=0;

for(int l=0;l<3;l++)
   subject_avg[l]=0;

//讀入n筆學生分數
for(int i=0 ; i < n ; i=i+1 )
scanf("%d%d%d", &score[i][0], &score[i][1], &score[i][2]);

//計算每個人的平均
for(int i=0 ; i < n ; i++ )
avg[i]=(score[i][0]+score[i][1]+score[i][2])/3;

//計算科目平均
for(int i=0 ; i < 3 ; i++ ){
   for(for int j=0 ; j< n ; j++)
      subject_avg[i]+=score[i][j];
   subject_avg[i]=subject_avg[i]/n;
}

外包工 2010-10-23 09:50 发表评论

程式設計(16)--作业3：河內塔(遞迴函數)

外包工 — Sat, 23 Oct 2010 01:49:00 GMT

請你設計一程式﹐利用遞迴函數的技巧﹐計算出般運N個圓環之河內塔所需要的全部移動次數。
--------
條件限制
1.使用者輸入一個正整數N(N<64)
2.輸出移動N個圓環所需要的全部移動次數。
--------
輸入格式
無檔案輸入,由鍵盤輸入資料(正整數N,N<=64)。
--------
輸出格式
無檔案輸出,由營幕輸出資料(移動次數)。
--------
輸入範例
Please input positive integerN(N<=64)
N=3
--------
輸出範例
N=3,Total moves=7
----------

/*

1.簡單的想法

將N個環分成上面的[N-1個]及[最下面的環],假設柱子編號為A,B,C

將所有環由A移到C。

1.1 先將[N-1個環]由 A 暫移到 B
1.2 再將[最下面的環]由 A 移到 C
1.3 最後再將[N-1個環]由 B 移到 C

假設移動N個環所需的次數為F(N),則由1.1~1.3可知:

F(N)=F(N-1)+1+F(N-1)=2*F(N-1)+1

*/

int hanoi-total-moves(int n){
if(n==1)
return 1;
else
return 2*hanoi-total-moves(n-1)+1;
}

/*

2.進階問題

如果要把移動的過程順便顯示出來,則需要改寫以上的函數:

*/

/* N個環,由 from柱移到 to柱, 中間透過 tmp柱 */

void hanoi-moving-steps(int n,char from,char to,char tmp){
// 移動前 N-1 個環,由 from 到 tmp,透過 to
        if(n==1)
          printf("move ring %d from pillar %c to pillar %c\n",n,from,to);
        else{
hanoi-moving-steps(n-1,from,tmp,to);
// 移動第 N 個環
printf("move ring %d from pillar %c to pillar %c",n,from,to);
// 移動前 N-1 個環,由 tmp 到 to,透過 from
hanoi-moving-steps(n-1,tmp,to,from);
        }
}

/* 呼叫函數例: 移動三個環,由A柱到C柱,中間透過B柱*/

hanoi-moving-steps(3,'A','C','B')

外包工 2010-10-23 09:49 发表评论

程式設計(15)--作业2：猜數字(?A?B)

外包工 — Sat, 23 Oct 2010 01:47:00 GMT

問題敘述

猜數字遊戲(?A?B)是一種兩人玩的小游戲,其規則如下所述。
假設兩人玩此遊戲,兩人先各在心中默想一組四位數(數字不重複)
數字,然後兩人互猜對方所想數字,若數字正確且位置正確,則為
1A,若數正確但位置不對,則為1B,被猜的人需將猜的結果告訴
對方,以讓對方修正後再猜。

例:假設甲乙互猜對方數字,其過程如下:

甲默想數字為 2345
乙默想數字為 7623

甲猜:1234
乙答:0A2B
乙猜:6789
甲答:0A0B
甲猜:5678
乙答:1A0B
乙猜:1234
甲答:0A3B

直到某人猜到對方數字為止

現在請你設計一個程式,讓它能夠預先默想一組四位數數字,然後
使用者能與其互動來猜電腦所想的數字。電腦必須能夠正確的回
答所猜的結果(以?A?B的格式),直到使用者猜到電腦所想的數字為止。
--------
條件限制

1.電腦會以亂數產生一組四位數的數字(數字從0~9不重複)
2.使用者需輸入四位數數字來猜
3.電腦需依使用者輸入的輸出回應?A?B
4.答對時顯示訊息,並結束程式。

--------
輸入格式

無檔案輸入
--------
輸出格式

無檔案輸出
--------
輸入範例

無檔案輸入
--------
輸出範例

無檔案輸出
----------

外包工 2010-10-23 09:47 发表评论

程式設計(14)--作业1：猜數字(二分逼近法)

外包工 — Sat, 23 Oct 2010 01:46:00 GMT

問題敘述
猜數字遊戲(二分逼近法)是一種兩人玩的小游戲,其規則如下所述。
假設兩人玩此遊戲,兩人先各在心中默想個數字(介於1~100間)
數字,然後兩人互猜對方所想數字,若數字正確則結束遊戲,
若不正確,需告訴對方答案為比較大或較小。然後兩人輪留猜
直到某人猜對為止。
例:使用者默想一數字27
電腦猜:50(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:2
電腦猜:25(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:1
電腦猜:37(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:2
電腦猜:31(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:2
電腦猜:28(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:2
電腦猜:26(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:2
電腦猜:27(答案較大請輸入1,答案較小請輸入2,猜對請輸入3)
使用者回答:3
Bingo!猜對了,共猜了7次.
遊戲結束.
--------
條件限制
1.使用者在心中默想一個數(1~100)
2.電腦以二分逼近的方式來猜使用者所想的數字,
使用者需告訴電腦所猜數字是否正確,若不正確,
需告訴電腦答案為較大或較小(可用1,2,3代碼表示大小或猜對)。
3.猜中後結束程式,並顯示所猜次數.
--------
輸出格式
無檔案輸入
--------
輸出格式
無檔案輸出
--------
輸入範例
無檔案輸入
--------
輸出範例
無檔案輸出
----------

/*
low:下限
high:上限
guess: 電腦猜的數字
result: 電腦猜的結果(該調大或調小)
可用數字代表:
例: 1=>大,2=>小,3=>猜對

下列提示之問號請自行將程式碼補上
*/

int guess,result;
int low=0,high=100;

//當結果不為猜對時,迴圈重複執行
while(result!=?)
{
//所猜的數字=上限加下限除以2;
guess=(low+high);
//印出所猜的數字
printf("%d",guess);
//讀取結果
scanf("%d",&result);

//如果要調大
if(result==?)
// 將下限調大
low=?
//如果調小
else if(result==?)
// 將上限調小
high=?
//猜對了
else if(result==)
// 印出猜對訊息
printf?
}

外包工 2010-10-23 09:46 发表评论

程式設計(13)--堆疊與佇列 stack&queue II

外包工 — Sat, 23 Oct 2010 01:42:00 GMT

1.堆疊應用:計算後序式(postfix)之四則運算

當我們在計算四則運算時,所用的式子稱為中序式(infix)。中序式,是因為運算符號
被夾在兩個運算數字的中間(如 1+2 或 3*4),但是當多筆數字及運算符號在同一個式
子時,便會有運算符號優先順序的問題。請看下面兩個算式:

1*2+3*4=14,答案是對的(依照先加減後乘除的順序計算)
1*2+3*4=24,若依照先加減後乘除的順序,則答案是錯的,但反之則是對的。

為了避免這種運算符號優先順序不同造成的困擾，當我們在計算時有時會加上括號
明確的表明運算順序。(例: 1*(2+3)*4 )

若利用程?茬B理四則運算的話,中序式雖然容易被人類判讀,但對程?茖市o會造
成上述的困擾與麻煩,而用後序?茬B理則不必考慮運算符號順序的問題。

後序式的規則是將兩運算數字排在前,運算符號排在最後。例:

前序式 => 後序式
1*2         12*
1*2+3*4     12*34*+
1*(2+3)*4   123+*4*
1+2*3+4     123*+4+

利用堆疊來計算四則運算:

(1)先將中序式:a*b+c*d 轉換成後序式:ab*cd*+
(2)
      由左至右掃描整個後序式,若遇到數字則放入堆疊;若遇到運算符號,則從堆疊內取
      出兩個數字作運算,再將結果放入堆疊。重覆處理到式子結束。

(3)取出堆疊內的最後筆資料,即為結果。

處理流程:

postfix:        stack:         op:      comment:

ab*cd*+                                 原始算式
b*cd*+          a                       放入a至堆疊
*cd*+           ab                      放入b
cd*+            (a*b)           *       運算*,取出b,a 並將(a*b)結果放入堆疊
d*+             (a*b)c                  放入c
*+              (a*b)cd                 放入d
+               (a*b)(c*d)      *       運算*,取出d,c 並將(c*d)結果放入堆疊
                  (a*b)+(c*d)     +       運算+,取出(c*d),(a*b)並將(a*b)+(c*d)放入堆疊

故以程式計算四則運算的流程如後:

中序式=>後序式=>運算處理

(中序式轉換為後序式的作法因為需要較多篇幅,在此先省略。)

2.佇列應用:走迷宮

走迷宮是一種考驗計憶力的遊戲。(not yet!)

外包工 2010-10-23 09:42 发表评论

程式設計(12)--堆疊與佇列 stack&queue I

外包工 — Sat, 23 Oct 2010 01:41:00 GMT

1.堆疊處理資料的方式都是在同一邊進行，也就是由一端插入，也由同一端刪除,

因此，堆疊處理資料的順序為後進先出(Last In First Out,LIFO)；平日生活中,也有

資些堆疊的例子，如堆積木、蓋房子...等，都是一層一層的堆上去，如果要拆下來

的話，也只能從最上面卸下來。

堆疊範例:

放入1 放入2 2 放入3 2 取出3 2 取出2 取出1

=> 1 => 1 => 1 => 1 => 1 =>

2.佇列和堆疊處理資料方式是不大一樣的，佇列是屬於先進先出（First In First

Out,FIFO）的觀念，在平日生活中可以看到很多屬於佇列的例子，如排隊上公車、

排隊買電影票或是超市排隊付賬等，皆是先到達的先處理、後到的後處理。

佇列範例:

放入1 放入2 2 放入3 2 取出1 3 取出2 取出3

=> 1 => 1 => 1 => 2 => 3 =>

3.堆疊與佇列的實作可以陣列或串列的方?荍@。其基本操作的部份可分為放入

(push）、取出（pop）、查詢（retrieve）、檢查是否滿溢（isfull）、

檢查是否為空（isempy）

外包工 2010-10-23 09:41 发表评论

程式設計(11)--排序sort

外包工 — Sat, 23 Oct 2010 01:40:00 GMT

摘要: 1 汽泡排序法（Bubble Sort）︰如同汽泡由下逐漸往上升，越大的汽泡上升越快。說明：假設現有資料如下，欲將其由小排列至大。(若有N筆資料,則共需N-1回合) 小 => => => 排序方向 =&... 阅读全文

外包工 2010-10-23 09:40 发表评论

程式設計(10)--搜尋與排序search & sort

外包工 — Sat, 23 Oct 2010 01:38:00 GMT

1 搜尋︰

1.1 循序搜尋（線性搜尋）︰

將資料重頭到尾檢查過一遍，即為循序搜尋。

eg.假設有以下十筆資料,欲找數字7

1 2 3 4 5 6 7 8 9 10

=> 由左至右，共需比對7次。

若考慮一般情形的話，循序搜尋N筆資料所須比對的次數最大為N，最小為1，故平均起來需要比對(1+N)/2次。

範例程式

int data[10]={1,2,3,4,5,6,7,8,9,10};

//target為要找的資料

int target=7;

//found=0為預設值,若找到則將其設為1

int found=0;

for(int i=0;i<10;i++)

if(target==data[i]){

found=1;

printf("found!at %d position\n",i);

//break可以中斷for迴圈

break;

}

if(found==0)

printf("not found!\n");

1.2 二元搜尋 (Binary Search)

二元搜尋法所使用的時機是當資料以經排好順序後，我們先從中間值開始找起。若目標值比中位數來的小，則往小的另一半繼續找；反之則往大的另一邊找。如此尋找的次數便可有效地降低，最多不會超過log2(N)+1次。

eg. 假設有以下10筆資料，欲找數字7，共需比對4次!

1	2	3	4	5	6	7	8	9	10	=>一開始先找中間值5(亦可先找6)，未找到。
					6	7	8	9	10	=>將範圍縮小成右半邊，再找其中間值8，未找到。
					6	7				=>將範圍縮小成左半邊，再找其中間值6，未找到。
						7				=>將範圍縮小成右半邊，只剩下7，Bingo找到了!

範例程式

int data[10]={1,2,3,4,5,6,7,8,9,10};

//target為要找的資料，found=0為尚未找到，found=1為找到。

int target=7,found=0;

//low為左邊界索引值，high為右邊界索引值，mid為中間值索引值

int low=0,high=9,mid;

//當左邊界小於或等於右邊界及尚未找到資料時，重覆執行

while(low <= high && found==0){

mid=(low+high)/2;

if(target==data[mid]){

found=1;

printf("found!at %d position\n",mid);

}

else if(target > data[mid])

low=mid+1;//重設左邊界

else if(target < data[mid])

high=mid-1;//重設右邊界

}

if(found==0)

printf("not found!\n");

3 想想看

3.1 若將以上二分搜尋法的程式碼while(low<=high&&found==0)中的low<=high移除，請問執行結果會有何影響?(提示：可分為找到資料與找不到資料兩種狀況來討論)

3.2 請修改以上範例程式碼，使其可以將比對次數印出來。

3.3 想想看：請寫一程式，比較當處理不同的資料數量時(10、100、10000)，線性搜尋與二元搜尋法執行的效率。並請將效率量化。

外包工 2010-10-23 09:38 发表评论