地特三等申論題
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)
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 專屬家教
【解題關鍵】利用數學特性推導搜尋下界以最佳化效能，並結合正規表達式進行嚴格的邊界與防呆驗證。 【解析】 一、演算法最佳化設計
▼ 還有更多解析內容
整數產生器演算法實作
💡 利用數學特性優化搜尋範圍並結合輸入驗證的演算法實作。
🔗 產生器搜尋運算邏輯鏈
- 1 輸入驗證 — 使用 Regex 確保輸入為正整數，不合法則中斷
- 2 區間優化 — 由 M 扣除位數乘 9 決定搜尋起點，減少迭代次數
- 3 位數加總 — 透過 n%10 與 n/10 循環加總各個數位
- 4 條件比對 — 判斷 N + DigitSum(N) 是否等於目標值 M
↓
↓
↓
🔄 延伸學習：延伸學習：如何將此演算法處理萬進位以上的大數運算優化。
