資訊處理 109 年程式設計考古題

請使用Java、C#、C++或Python 等物件導向程式語言，建立矩陣相關 運算的系統，系統一共有三個類別，分別為抽象類別Matrix，實作類別 MatrixMultiply 及MatrixAdd，其中：（30分） ＊抽象類別Matrix 中所有的變數跟方法皆為protected，主要包含了： ．matrix1, matrix2, resultM 三個實數值二維matrices 資料 ．一個抽象的checkDimension( )方法，用來檢查matrix1跟matrix2是 否適合做所指定的運算 ．一個抽象的matrixOperation()方法，用來對matrix1跟matrix2進行運算 ．一個setMatrix()方法，可以將所傳入的兩個matrices 複製到matrix1, matrix2 ．改寫物件的toString()方法，可以顯示matrix1, matrix2及resultM 的 內容 ＊類別MatrixMultiply，繼承類別Matrix： ．實作Matrix 中的兩個抽象方法，分別可以實現父類別內matrix1及 matrix2進行乘法時的維度檢查及乘法運算，進行運算前會主動呼叫 checkDimension()，確定是否可以進行相關運算，如無法運算， resultM 會被設定為null 並回傳，否則進行運算，結果存於父類別的 resultM 並回傳 ．一個空建構子及一個可以接受兩個二維matrices 的建構子，建構子 中呼叫父類別的setMatrix()方法，設定matrix1及matrix2（空建構 子會將matrix1及matrix2設為null） ＊類別MatrixAdd，同MatrixMultiply，僅實作抽象方法時，是以matrices 加法為對象，進行維度的檢查及運算

請使用Java、C、C++、C#或Python，分別使用iterative 跟recursive 方 法，撰寫二元搜尋法，搜尋已排序的整數值數列。（20分） 註：假設數列資料是以具有array 性質的list 來存放 ＊模組程式應能接受欲搜尋的資料及已排序數列的相關資料 ＊模組程式應回傳所欲搜尋的資料是否在數列資料中

請使用Java、C、C++、C#或Python 撰寫相關程式模組，使用stack（先 進後出的線性資料結構）來完成preorder 的深度優先（Depth First Search） 樹狀圖追蹤（traversal）。（25分） 註：假設樹狀圖的節點資料可以為任意型別 註：假設樹狀圖的節點結構內含三個全域變數：資料、父節點、所有子 節點串接的linked list ＊模組程式應能接受樹狀圖的樹根 ＊模組程式應以字串數列方式，回傳樹狀圖追蹤的結果（以空白、逗號 或換行符號區隔資料字串） ＊樹狀圖中的節點需另以獨立的class 定義節點資料、相關的建構子 （Constructor）與存取子（Accessor/Mutator）

請使用Java、C、C++、C#或Python 撰寫相關模組程式，可以找出某一 整數的所有generator(s)。（25分） digit-sum：正整數N 的digit-sum 定義為「該正整數本身跟構成該整數個 別數字的總和」，如245的digit-sum 為256，因為245+2+4+5等於256 generator：正整數M 是正整數N 的digit-sum 時，則N 為M 的generator 如245是256的generator 如1979是2005的generator，因為1979+1+9+7+9等於2005 如198及207皆是216的generator，而198是216最小的generator ＊模組程式應能接受使用者由標準輸入裝置所輸入的資料 ＊模組程式中應控制使用者輸入資料的正確性與合法性，如輸入資料非 正整數，程式應顯示輸入資料不正確的訊息，然後結束程式 ＊輸入資料無誤，執行程式後，應顯示該輸入資料的所有generator(s)