地特三等申論題
109年
[資訊處理] 程式設計
第 四 題
請使用 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)
📝 此題為申論題
思路引導 VIP
首先設計嚴謹的輸入驗證機制（如使用正規表達式驗證正整數格式與處理溢位異常），接著構思核心演算法。為展現高級開發者的效能思維，應避免從 1 盲目窮舉到 M，而是透過數學推導找出 Generator 的下界（即 M 減去「9 × M的位數」），將時間複雜度由 O(M) 大幅降至接近 O(1)，並以物件導向架構（如 Java）進行模組化封裝。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】利用數學特性推導搜尋下界以最佳化效能，並結合正規表達式進行嚴格的邊界與防呆驗證。 【解析】 一、演算法最佳化設計
▼ 還有更多解析內容