Wagering

四、打賭遊戲
三個箱子中有一個放了巨額獎金，另兩個是空的。參賽者選擇一個箱子後，莊家打開一個空的箱子，問參賽者要不要改變選擇換到另一個箱子。此時參賽者有三種可能的策略：

1.維持原來之選擇
2. 換到另一個箱子
3. 隨機（random）決定要不要換

最後莊家公佈答案，決定勝負。請寫一程式完成這個遊戲，並統計猜中的機率。

提示：遊戲開始前必須輸入要玩的次數，並顯示三種策略之代號（參考Sample Output）。程式必先隨機決定巨額獎金放置之箱子，但尚不能公佈，參賽者此時決定其選擇之箱子，接著莊家打開一個空的箱子之後，詢問參賽者決定採用何種策略（參考Sample Output），此時顯示參賽者最後選擇之箱子，然後公佈答案及猜中與否。遊戲結束後公佈猜中之機率。

　
Sample Output：
請輸入要玩之次數： 10
策略代號：
1. 維持原來之選擇
2. 換到另一個箱子
3. 隨機決定要不要換
***************************
請輸入所選擇之箱子號碼： 1
莊家打開2號箱
請輸入策略代號： 1
最後選擇1號箱
* 巨額獎金在3號箱
>> 失敗
***************************
請輸入所選擇之箱子號碼： 3
莊家打開1號箱
請輸入策略代號： 2
最後選擇2號箱
* 巨額獎金在3號箱
>> 失敗
***************************
請輸入所選擇之箱子號碼： 2
莊家打開3號箱
請輸入策略代號： 3
最後選擇2號箱
* 巨額獎金在2號箱
>> 成功
***************************
：
：
：
***************************
遊戲結束，成功率0.45　

困難度：*
時間複雜度：O(n)
程式語言：C++
預估時間：1 小時

解題原理：
1. 先取得使用者輸入玩的次數
2. 隨機產生巨額寶箱號碼
3. 莊家隨機打開非使用者且非巨額寶箱號碼
4. 處理策略代號，如果選擇換到另一個寶箱，演算法為 1+2+3 - 莊家打開寶箱號碼 - 使用者原先選擇寶箱號碼
5. 完成

程式下載

原碼下載

參考來源：中山大學八十九學年度電腦程式設計競賽 試題 四

Tower of Hanoi

三、河內塔遊戲（Tower of Hanoi）
河內塔遊戲中有三根支架A、B、C，每根支架最多可放n個大小不同、中心挖孔的圓盤，大圓盤不得放在小圓盤上面。起先n個圓盤均置於支架A上（如圖一所示，以n=3為例）。今欲將這n個圓盤從支架A搬到支架C，每次只能搬一個盤子，支架B當作暫存處，請問共須搬動多少次的盤子才能完成？

請寫一個非遞迴（non-recursive）程式來處理這個問題。為簡單起見，這n個圓盤以數字1到n來表示，大數字代表大盤子，圓盤置於支架之情形用橫式表示，請參考Sample
Output。程式開始時需讀入圓盤之個數n（3≦n≦8），然後顯示支架A、B、C上圓盤放置情形（參考Sample
Output，以n=3為例），當搬動之次數為5之倍數（5,
10、15、…）時，需顯示A、B、C支架上圓盤放置之情形，並印出已經搬動盤子的次數。螢幕印滿後暫停，按任何鍵再繼續執行，直到完成後，顯示此n個盤子已搬至支架C上，並印出搬動之總次數。

Sample Output：
請輸入圓盤數目： 3
*************************
起始狀態：
支架A： 3 2 1
支架B：
支架C：
*************************
搬了5次之後
支架A： 1
支架B： 2
支架C： 3
*************************
：
：
：
*************************
共搬了7次才完成
支架A：
支架B：
支架C： 3 2 1
　

困難度：**
時間複雜度：O(n)
程式語言：C++
預估時間：1 小時

解題原理：
1. 根據 Glenn C. Rhoads 提出對河內塔非遞迴解方式，以二進位方式進行操作，得到驚人的結果。其原理是假設有3個支架分別為0~2，一開始第一個支架為0，如果目前要移動的盤子是偶數，則要移動到第1個支架，否則移動到第2個支架
2. 計算螢幕中印出的行數，進行處理
3. 使用向量儲存目前支架的集合，每五次印出
4. 完成

程式下載

原碼下載

參考來源：中山大學八十九學年度電腦程式設計競賽 試題 三

Manage Business Card

二、Write a program that allows user to manage his business card collection.

C:\>cardfile cardfile.dat

Your program should be able to support the following function by a single linked list structure:
1. Add or delete a card to or from the data file.
2. Find a card based on name search.
3. Edit an existing card (change the phone number or company)
4. List the contents of the file (in alphabetical order)
5. Quit (save changes)

The business card (card structure) should include the following information:
Name (30 characters)
Phone (15 characters)
Company (40 characters)

<Example of command line>:Add name、phone number and company line by line:
Chris Lee
5252000
Dept. of EE、NSYSU
<Example of command line>: Find Chris Lee
<Example of command line>: Edit Chris Lee
<Example of command line>: List Chris Lee
<Example of command line>: List All

Your program should give user the necessary messages、such as usage of your program and some necessary error messages.

<hint>

The format of the data file is one line per card record with a tab as a field separator. The data is read in a line at a time by the fgets() function、the newline character is removed、and the data fields
extracted by successive calls to the strtok()、which copies tokens from a data stream.

困難度：*
時間複雜度：O(n)
程式語言：C++
預估時間：3 小時

解題原理：
1. 透過終端機介面判斷欲選擇的功能
2. 使用單向鏈結串列進行資料的新增、修改、刪除、尋找和排序
3. 根據使用者選擇的指令在終端機介面上顯示
4. 完成

程式下載

原碼下載

參考來源：中山大學八十九學年度電腦程式設計競賽 試題 二

Sorting

一、Write a program that can read an array of integers and sort the array of integers into ascending order or descending order. Your program must be able to
(1) Read the elements of the array from the keyboard.
(2) Use command-line arguments to pass either –a for ascending order or –d for descending order.
(3) Print the values of the array on the screen after ascending or descending.
(4) Reallocate the memory for the array to 1/N of the current number of elements、where N is any positive integer. Use command-line argument to pass N from the keyboard. Print the values remaining in the array.

<Examples of Input and Output>
Input: 5 4 8 3 20 11 –a Output: 3 4 5 8 11 20
Input: N = 2 Output: 3 4 5
Input: N = 3 Output: 3 4

Input: 5 4 8 3 20 11 –d Output: 20 11 8 5 4 3
Input: N = 2 Output: 20 11 8
Input: N = 3 Output: 20 11

困難度：*
時間複雜度：O(n^2)
程式語言：C++
預估時間：1 小時

解題原理：
1. 以字串讀入內容，一次處理一行
2. 判斷是遞增或遞減排序
3. 取得輸入的整數內容進行排序
4. 完成

程式下載

原碼下載

參考來源：中山大學八十九學年度電腦程式設計競賽 試題 一

The Prefix Evaluator

The Prefix Evaluator

Let P be a prefix expression which is composed of the characters in the set {『1』、『3』、『5』、『7』、『9』、『$』、『%』} where each of the operands in P is a digit and the length of P is not greater than 30 characters. The symbols 『$』 and 『%』 are binary operators in P and defined as follows: x $ y = (x + y)/2 and x % y = (x - y)/2 where x、y I {1、3、5、7、9}. Please write a program to evaluate P.

Input Format:
A prefix expression P I {『1』、『3』、『5』、『7』、『9』、『$』、『%』}⁺ where 1 ￡ P ￡ 30.

Output Format:
The value of P. Note that the data type of the output must be 「float」.

Sample Input:
1. $39
2. %57
3. $$39%57
4. %%%1357

Sample Output:
1. 6.000000
2. -1.000000
3. 3.500000
4.-5.000000

困難度：*
時間複雜度：O(n^2)
程式語言：C++
預估時間：1 小時

解題原理：
1. 以字串讀入內容，一次處理一行
2. 將每個字元以浮點數的觀點進行處理
3. 如果字元是運算子則設為很大的數
4. 從右往左看，找到第一個運算子後進行運算，若%39，則3%9
5. 重複步驟4，直到沒有運算子即完成

程式下載

原碼下載

參考來源：中山大學 九十三學年度電腦程式設計競賽 試題 Problem D

The Postfix Converter

The Postfix Converter

Let W be an infix expression which is composed of the characters in the set {『a』、『b』、『c』、『d』、『e』、『#』、『@』、『(』、『)』} where the length of W is not greater than 30 characters. The alphabets 『a』、『b』、『c』、『d』、and 『e』 are the operands in W. The symbols 『#』 and 『@』 are binary operators in W where the priority of # is less than that of 『@』、i.e.、「a # b @ c」 is equivalent to 「a # (b @ c)」 and 「a @ b # c」 is equivalent to 「(a @ b) # c」. The operator 『#』 is with left associativity、i.e.、「a # b # c」 is equivalent to 「(a # b) # c」、while the operator 『@』 is with right associativity、i.e.、「a @ b @ c」 is equivalent to 「a @ (b @ c)」. Please write a program to convert W into a postfix expression.

Input Format:
An infix expression W I {『a』、『b』、『c』、『d』、『e』、『#』、『@』、『(』、『)』}⁺ with 1 ￡ W ￡ 30.

Output Format:
The postfix form of W.

Sample Input:
1. a # b @ c @ d # e
2. a @ (b # c) @ d
3. a # b @ ((c # d) @ (e # a))

Sample Output:
1. abcd@@#e#
2. abc#d@@
3. abcd#ea#@@#

困難度：**
時間複雜度：O(n)
程式語言：C++
預估時間：5 小時

解題原理：
1. 以字串讀入內容，一次處理一行
2. 先去除空白
3. 將每個字元以字串容器的觀點進行處理
4. 設定每種不同字元的優先權
5. 每次從字串容器集合取出優先權最高的字元
6. 如果是最高優先權的括號則進行分進合擊遞迴演算法，先處理括號內的字元，進入步驟7，否則進入步驟8
7. 如果欲處理的內容仍包含括號，進入步驟3處理括號內的字元，否則進入步驟8
8. 此時處理的字元為1個運算子和2個運算元，進行後序轉換，若a@b，則ab@
9. 重複步驟3-8，直到沒有運算子即完成

程式下載

原碼下載

參考來源：中山大學 九十三學年度電腦程式設計競賽 試題 Problem C

Windows Mobile 5.0 for Pocket PC – CHT 手寫辨識技術檔案

Windows Mobile 5.0 for Pocket PC – CHT 手寫辨識技術檔案

大綱
背景
簡介
手寫辨識函式庫
自訂手寫辨識區域
自訂截取手寫辨識文字
結語

背景
此技術文章是對微軟行動裝置開發平台Windows Mobile 5.0 for Pocket PC – CHT部署熟悉的讀者，且具備對於Visual Studio .NET圖形視窗設計和C# 程式語言的技術。

簡介
行動裝置無論是Smartphone或是Pocket PC，近年在通訊電子產業大放異彩，當然軟體巨擘 Microsoft 微軟公司也相當致力於行動裝置的領域，從 Pocket PC 2002、Pocket 2003、Smartphone 2003、Windows CE 5.0到Windows Mobile 5.0，在在顯示出微軟公司對於行動裝置的成就，其中在軟體整合部分也在 Microsoft Visual Studio .NET 系列的程式開發工具開始支援SmartDevice的軟體開發，整合 .NET Framework 和 .NET Compact Framework 於開發工具中，使得程式開發人員在操作上可以使用相同的開發模式、熟悉的工具介面、一致性的 .NET 函式庫進行操作，大大提升了微軟在行動裝置軟體發展的競爭力。

行動裝置與一般手提電腦或是個人電腦不同的功能即是手寫辨識，透過觸控筆的劃記和點選進行裝置介面的操作和文字輸入，一般來說，行動裝置皆內建了手寫辨識的功能，在中文版的Windows Mobile 5.0 for Pocket PC – CHT行動裝置而言，無論是中文、英文或是數字的手寫辨識率已是相當精準且成熟的技術，而手寫區域分為兩種，一種是全螢幕輸入和一種是在螢幕下方區域輸入；對於程式開發人員而言，若是要自行處理辨識的文字、手寫的區域位置或是候選字的排列優先順序等，並無法直接變更內建的手寫辨識軟體的設定。

手寫辨識函式庫
在相容於Windows Mobile 5.0 for Pocket PC – CHT的行動裝置中，作業系統提供了一系列的函式庫讓程式設計人員使用，目前提供的版本只提供 eVC++ 直接呼叫，並不能直接從 .NET 的程式呼叫，因此須透過DllImport 的方式進行函式原型宣告。
詳細範例程式碼請參考原文下載。

自訂手寫辨識區域
1. 建立 Microsoft Visual Studio .NET 2005中的SmartDevice 專案
2. 在Designer視窗建立一個Panel，此Panel為手寫辨識的區域，可放置在任何視窗的位置和大小
3. 對 Panel取得MouseMove、MouseDown、MouseUp和Paint事件
4. 紀錄滑鼠（觸控筆）的移動軌跡座標
5. 同步繪製筆跡在Panel元件上
詳細範例程式碼請參考原文下載。

自訂截取手寫辨識文字
1. 初始化手寫辨識函式庫
2. 開始執行手寫辨識
3. 持續加入滑鼠（觸控筆）座標軌跡
4. 進行手寫辨識
詳細範例程式碼請參考原文下載。


結語




















透過操作Windows Mobile 5.0 for Pocket PC – CHT
提供的手寫辨識函式庫，程式開發人員可以自訂手寫辨識區域和處理手寫辨識文字，本文示範了這些過程的片段完整功能的程式碼，對於函式庫的功能和操作可查詢MSDN，這裡就不各別作說明。

原文下載

全文完