編程題一

問題分析

題目要求使用 n 根小木棒，按照特定的方式排列，形成一個數字。具體規則如下：

1. 每個數字由小木棒組成，例如：
   • 1 需要 2 根小木棒。
   • 0 需要 6 根小木棒。
   • 其他數字（如 2, 3, 4, 5, 6, 7, 8, 9）需要的木棒數分別為 5, 5, 5, 4, 5, 3, 7, 2。
2. 要求生成的數字中，0 不能位于最前端。
3. 在滿足上述條件的情況下，找到使用 n 根小木棒能夠形成的最小數字。

解題思路

為了生成最小的數字，我們需要遵循以下原則：

1. 優先使用較少木棒的數字：例如，1 只需要 2 根木棒，是所有數字中使用木棒最少的，因此應該盡量多用 1。
2. 避免在最前端使用 0：如果剩余木棒不足以構成其他數字，可以考慮使用 0，但不能放在最前端。
3. 貪心策略：從高位到低位依次選擇能夠使用的最小數字，直到用完所有的木棒。

實現步驟

1. 定義每個數字所需的木棒數：創建一個數組或映射，存儲每個數字對應的木棒數。
2. 貪心構造數字：
   • 從高位到低位，優先選擇能夠使用的最小數字。
   • 如果當前位無法使用 0（因為它是首位），則選擇次小的數字。
   • 如果剩余木棒不足以構成任何數字，則結束構造。
3. 輸出結果：將構造好的數字輸出。

C++ 代碼實現

以下是完整的 C++ 代碼實現：

#include <iostream>
#include <vector>
#include <string>
using namespace std;// 定義每個數字所需的木棒數
const vector<int> sticks = {6, 2, 5, 5, 4, 5, 6, 3, 7, 2};int main() {int n;cin >> n; // 輸入木棒總數string result; // 存儲最終結果// 構造數字while (n > 0) {bool found = false; // 標記是否找到合適的數字for (int digit = 0; digit <= 9; ++digit) {if (sticks[digit] <= n) {// 如果是第一位，不能使用 '0'if (result.empty() && digit == 0) continue;// 使用該數字result += ('0' + digit);n -= sticks[digit];found = true;break;}}// 如果找不到合適的數字，退出循環if (!found) break;}// 輸出結果if (result.empty()) {cout << "-1" << endl; // 如果無法構造數字，輸出 -1} else {cout << result << endl;}return 0;
}

代碼解釋

1. 輸入處理：

   • 讀取用戶輸入的木棒總數 n。

2. 貪心構造數字：

   • 使用一個字符串 result 來存儲構造的數字。
   • 從高位到低位，依次嘗試使用數字 0 到 9。
   • 如果當前位是第一位，不能使用 0，因此跳過。
   • 如果某個數字的木棒需求不超過剩余木棒數，則將其加入結果，并更新剩余木棒數。
   • 如果遍歷完所有數字都無法找到合適的數字，則退出循環。

3. 輸出結果：

   • 如果成功構造了數字，則輸出結果。
   • 如果無法構造數字（例如木棒數不足），輸出 -1。

示例運行

輸入：

10

輸出：

1111

輸入：

6

輸出：

0

輸入：

7

輸出：

11

復雜度分析

1. 時間復雜度：

   • 每次嘗試構造數字時，最多需要遍歷 10 個數字（0 到 9），因此每次操作的時間復雜度為 (O(1))。
   • 總共需要進行 (O(n)) 次操作，其中 (n) 是木棒總數。
   • 因此，總時間復雜度為 (O(n))。

2. 空間復雜度：

   • 主要空間用于存儲結果字符串和常量數組 sticks，空間復雜度為 (O(n))。

結論

該代碼通過貪心策略，優先選擇使用較少木棒的數字，并確保 0 不出現在最前端，從而構造出最小的數字。對于給定的木棒數 n，能夠高效地計算出對應的最小數字。

編程題二

問題分析

題目要求根據整數 n 對 7 的余數，構造一個特定的數字 m。具體規則如下：

1. 如果 n 是 7 的倍數，則 m 等于 n / 7 個 8。
2. 如果 n 除以 7 的余數為 1，則 m 是由若干個 8 組成的數字，前面加上 10。
3. 如果 n 除以 7 的余數為 2，則 m 是由若干個 8 組成的數字，前面加上 18。
4. 如果 n 除以 7 的余數為 3，則 m 是由若干個 8 組成的數字，前面加上 20。
5. 如果 n 除以 7 的余數為 4，則 m 是由若干個 8 組成的數字，前面加上 48。
6. 如果 n 除以 7 的余數為 5，則 m 是由若干個 8 組成的數字，前面加上 28。
7. 如果 n 除以 7 的余數為 6，則 m 是由若干個 8 組成的數字，前面加上 102。

解題思路

1. 計算 n 對 7 的余數：使用取模運算符 % 計算 n % 7。
2. 根據余數構造數字：
   • 如果余數為 0，直接構造 n / 7 個 8。
   • 如果余數不為 0，先根據余數確定前綴（如 10, 18, 20, 等），然后在后面追加 (n / 7) 個 8。
3. 輸出結果：將構造好的數字輸出。

C++ 代碼實現

以下是完整的 C++ 代碼實現：

#include <iostream>
#include <string>
using namespace std;int main() {int n;cin >> n; // 輸入整數 n// 計算 n 對 7 的余數int remainder = n % 7;// 構造數字 mstring prefix; // 前綴string suffix; // 后綴（由若干個 '8' 組成）// 根據余數確定前綴switch (remainder) {case 0:prefix = ""; // 如果是 7 的倍數，不需要前綴break;case 1:prefix = "10";break;case 2:prefix = "18";break;case 3:prefix = "20";break;case 4:prefix = "48";break;case 5:prefix = "28";break;case 6:prefix = "102";break;}// 計算后綴中 '8' 的數量int num_eights = n / 7;// 構造后綴for (int i = 0; i < num_eights; ++i) {suffix += '8';}// 拼接前綴和后綴string result = prefix + suffix;// 輸出結果cout << result << endl;return 0;
}

代碼解釋

1. 輸入處理：

   • 讀取用戶輸入的整數 n。

2. 計算余數：

   • 使用 n % 7 計算 n 對 7 的余數，并存儲在變量 remainder 中。

3. 根據余數確定前綴：

   • 使用 switch 語句根據余數選擇對應的前綴字符串（如 "10", "18", "20" 等）。
   • 如果余數為 0，說明 n 是 7 的倍數，此時前綴為空字符串。

4. 構造后綴：

   • 后綴由若干個 '8' 組成，其數量為 n / 7。
   • 使用一個循環，將 '8' 追加到字符串 suffix 中。

5. 拼接前綴和后綴：

   • 將前綴和后綴拼接起來，形成最終的數字字符串 result。

6. 輸出結果：

   • 將構造好的數字字符串 result 輸出。

示例運行

輸入：

21

輸出：

888

輸入：

22

輸出：

10888

輸入：

28

輸出：

8888

輸入：

30

輸出：

20888

復雜度分析

1. 時間復雜度：

   • 構造后綴時，需要遍歷 n / 7 次，因此時間復雜度為 (O(n / 7))，可以簡化為 (O(n))。

2. 空間復雜度：

   • 主要空間用于存儲前綴和后綴字符串，空間復雜度為 (O(n))。

結論

該代碼通過簡單的數學運算和字符串操作，高效地實現了根據 n 的余數構造數字 m 的功能。對于給定的輸入 n，能夠正確輸出對應的數字 m。