博弈論
題目描述
運行代碼
#include<iostream>
#include<vector>
using namespace std;
int main(){int n;cin >> n;vector<int> d(n,0);for(int i = 0;i < n;i++){cin >> d[i];}vector<int> in(1000,0);for(int k = 1;k<=3;k++){for(int i=0;i<=n-k;i++){int t = 0;for(int j=i;j<i+k;j++){t = 10*t+d[j];}in[t] = 1;}}for(int i = 0;i < 1000;i++)if(in[i] == 0){cout << i << endl;return 0;}return 0;
}代碼思路
-
輸入處理:
- 首先，程序接收一個整數
n，表示數字序列的長度。 - 然后，程序讀取接下來的
n個整數并存儲在一個名為d的vector（動態數組）中。
- 首先，程序接收一個整數
-
初始化標記數組:創建一個大小為1000的
vector?in，并將其所有元素初始化為0。這個數組用來標記長度為1至3位的整數是否在給定序列中出現過。由于最大的3位數是999，因此1000的大小足夠覆蓋所有可能的情況。 -
檢查數字序列:對于長度為1、2、3的子序列，程序遍歷所有可能的起始位置
i：計算從位置i開始，長度為k（當前循環的長度）的子序列對應的整數t。這是通過將子序列中的每個數字乘以相應位值（10的冪）并求和得到的。將計算出的整數t在in數組中標記為1，表示這個數值已經在輸入序列中出現過了。 -
尋找未出現的最小整數:
- 遍歷
in數組，找到第一個值為0的元素的索引，這代表了未在輸入序列中出現過的最小正整數。 - 一旦找到這樣的索引，立即輸出該索引（即對應的整數），并結束程序。
- 遍歷
-
返回:如果遍歷完整個
in數組都沒有找到未出現的整數（理論上這種情況不應該發生，但代碼邏輯沒有直接處理這種特殊情況），程序會正常結束。
改進思路
-
減少內存使用：目前使用了一個大小為1000的
vector來標記數字是否出現，其實最大只需要到n的長度變化的所有組合即可，特別是當n遠小于3時。可以通過動態調整in的大小或者使用更高效的數據結構如set或unordered_set來改進。 -
優化尋找未出現數字的步驟：當前實現是線性查找
in數組中值為0的第一個元素，若大多數數字都已出現，則效率較低。可以在遍歷過程中直接記錄第一個未出現的數字，減少后續查找步驟。 -
增加對極端情況的處理：例如，當輸入序列為空或全為0時，原始代碼可能表現得不夠直觀或正確。
改進代碼
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;int main() {int n;cin >> n;vector<int> d(n, 0);// 輸入數字序列for (int i = 0; i < n; ++i) {cin >> d[i];}// 使用unordered_set存儲已出現的數字，自動去重且查找效率高unordered_set<int> appeared;// 檢查數字序列，添加長度為1到3的數字到集合中for (int k = 1; k <= min(3, n); ++k) { // 添加邊界條件避免n<k時的無效迭代for (int i = 0; i <= n - k; ++i) {int t = 0;for (int j = i; j < i + k; ++j) {t = 10 * t + d[j];}appeared.insert(t);}}// 尋找未出現的最小正整數int i = 1;while (appeared.find(i) != appeared.end()) {++i;}cout << i << endl;return 0;
}- 通過使用
unordered_set來存儲已出現的數字，提高了查找未出現數字的效率。 - 通過直接在遍歷過程中尋找未出現的最小整數，避免了最后單獨的查找循環，使得代碼更加簡潔。
- 增加了對輸入序列長度的邊界檢查，確保了代碼的健壯性。
注意點：
改進代碼為AI生成，并且這個代碼的數據通過率97%，無法通過所有測試數據
)
