Ch2 解題指引

找出最小的完全平方數

解題思路

以下想法有其中兩種是可行的，一種會超時（TLE），猜猜看是哪一個！

想法一

• 使用for迴圈，從
  $k$ 位數的第一個數，檢查到
  $k$ 位數的最後一個數。
• 每檢查到一個數，就看看他是否符合「各位數字皆為偶數」且「為完全平方數」。若同時滿足兩個條件，即為所求。

想法二

• 設
  $m$ 為起始數字，由
  $m=2$ 開始，檢查
  $m^2$ 是不是
  $k$ 位數，又是否符合「各位數字皆為偶數」這個條件。
• 每次m += 2，若
  $m^2$ 為第一個符合條件的
  $k$ 位數字，則記錄下來，此即所求。

想法三

• 找出
  $k$ 位數中最小的偶數
  $e$。
• 由
  $\lceil \sqrt{e}\rceil$ 開始，一個一個數字檢查，檢查其平方數是否符合「各位數字皆為偶數」，符合的話即為所求。
• 另外可使用加速條件：偶數的平方數尾數必為0, 4, 6。

引導問題

Q. 是哪個想法會超時呢？

A. 答案是想法一！因為a、b之間的數字，在位數k較大的時候，檢查了太多不必要的數字。
已知位數限制為

$0<k\le 10$，在最極端的狀況：

$k=10$，需要檢查的數字個數，量級到了

${10}^9$ ~

${10}^{10}$ 之間，顯然會超過時間限制。
相較之下，想法二、三只檢查了「完全平方數」，平方後不超過 10 位數的數字，最大不超過

${10}^5$。

Q. 如何判斷一個數是否為 k 位數？

A. 有兩種方法。

• [法一] 使用while迴圈處理整數變數

  宣告一個總和變數，只要除以 10 不為 0 就 +1。迴圈總共執行幾次，就是幾位數。

• [法二] string的size()

  可以使用 C++ 11 中的stoi函式。先將一個數字轉換成字串（string），再用字串長度判斷位數。若你是使用code::blocks撰寫程式，需要手動調整使用的編譯器版本，具體作法可參考這裏。

Q. 如何判斷一個數的各位數字都是偶數？

A. 承上，使用迴圈檢查每一個位數，確認都能被 2 整除即可。具體如何實作呢？你可以宣告一個布林變數is_all_even，初始值為true，只要有一個位數的數字為奇數，就把is_all_even設為false，然後結束迴圈，不用再繼續檢查下去。

bool is_all_even = true;  // 意義：各位數字是否都是偶數
    while(...){   // 使用迴圈檢查每一位數字
        if(...){  // 只要發現有一個位數是奇數
            is_all_even = false; 
            break;
        }
        ...
    }

若要將其改寫為自訂函式，回傳資料型態可以設為布林值，代表「是否各位數字皆為偶數」：

bool is_all_even(int n){
    while(...){   // 使用迴圈檢查每一位數字
        if(...){  // 只要發現有一個位數是奇數
            return false;
        }
        ...
    }
    return true;    // 前面都沒有return false，表示各位數字皆為偶數
}

Q. 我使用int來做題目，為什麼會拿到 WA(15%)？

A. 因為題目有說到，最多為 10 位數字，int型態的數字無法容納所有 10 位數字，可能會出現 溢位（overflow） 狀況，進而計算錯誤的結果。幸好數字也沒有太大，請嘗試使用長整數（long long）這個資料型別，其可容納的數字範圍可上網查詢。

一起回家的日子

這題楷宗老師有特別說明最小公倍數的解法，請參考函式實作示例。以下將延續課堂講解的解題邏輯進行說明。

解題思路

• 宣告所需自訂函式：最小公因數、最大公因數、閏年判斷。
• 處理輸入：作法與「計算時間差」這題相似，處理特定日期格式輸入。
• 計算天數：根據輸入的人數與天數，求最小公倍數，代表下次一起回家所需天數。
• 推算日期：扣除所需天數，跨月、跨年，直到下次一起回家的日期。
• 處理輸出：作法與「計算時間差」這題相似，輸出特定日期格式。

引導問題

Q. 怎麼判斷一個數是否為閏年？

A. 網路上有很多種解法，歡迎同學們去查查看，觀察每種解法的思路。最常看到的寫法為：

• 被 4 整除的數字，如果不是 100 的倍數，即為閏年。
• 如果是 400 的倍數，必為閏年。
  以上兩式寫成邏輯運算式，||起來就是閏年判斷的條件式。

大部分人應該都學過閏年判斷，不妨嘗試寫成自訂函式，在主程式呼叫使用。

Q. 具體如何針對跨月、跨年，往前推進到一起回家的日子？

A. 做法有非常多，順著加、倒著扣都有對應的寫法。而課堂範例的思路大概是這樣的：

• 先將現在的日期加上下次回家所需天數備用。
• 只要所需天數大於該月份天數，就扣掉這些天數，開心度過這個月。
• 到下一個月。注意若 12 月過完，要回到 1 月，並進入新的一年。
• 重複以上步驟。當可扣掉的天數未滿該月份總天數，該月份、剩餘天數即為一起回家的日子。

Q. 我該如何把閏年納入考量？

A. 閏年的影響視在特定年份的 2 月多 1 天。基本判斷準則如下：

• 該年是否為閏年？
• 如果是閏年，剩餘天數加上去後，是否需要跨過該年的 2/29？

同時符合以上條件，才需要多加一天。

Q. 要一個一個月份判斷有幾天超級麻煩，有沒有簡化程式碼的方法？

A. 宣告一個陣列，存放每個月的天數：

int month_day[] = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

另外，也可以宣告 13 個整數的陣列，在陣列最前面多放一個數字 0 ，如此一來，就可以接以月份為陣列索引值，取用每個月對應的天數。

Q. 不知道哪裡寫錯了，我的想法很對啊QQ 可以怎麼檢查呢？

A. 建議出幾筆測資給自己測試。例如，我喜歡拿 1 個人、1 天後回家，來測試閏年/非閏年跨天、跨月、跨年的各種可能性：

1
1
2024/02/29

發想各種例外情況，避免無端被扣分，是賽後測評機制的重要能力。這題是很好的練習機會，大家試試看吧！

賓果遊戲

（待補）