🔗 UVA-11634 Generate random numbers

tags: `模擬(Simulation)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

在 UVA 上若使用 Python 提交，這題有機率會超時，若遇到 TLE 可以多試幾次，或改成使用 C++ 提交。

題意

這是一道關於使用 中值平方法(middle-square-method) 生成偽隨機數的問題。中值平方法是一種由John von Neumann在1946年提出的產生偽隨機數的方法。其運作原理如下：

選擇一個初始值 $a_0$ ，其十進位表示的長度至多為 $n$ 位數。在本題中，使用 $n=4$ 。
將 $a_0$ 自乘，並在前面補上零直到達到 $2 \times n$ 位數，然後取中間的 $n$ 位數來形成 $a_1$ 。
對於每個 $i>0$ ，重複這個過程以生成 $a_i$ 。

例如：

初始值 $a_0=5555$ ， $a_0^2=30858025$ ，中間的4位數是 $a_1=8580$ 。
初始值 $a_0=1111$ ， $a_0^2=01234321$ ，中間的4位數是 $a_1=2343$ 。

給定初始化值 $a_0$ ，檢查能生成多少個不同的數字。

思路：模擬(Simulation)

由於在遇到重複的數字 $a_i$ 後，後續的數字都會重複，因此我們可以使用一個陣列 $\rm{visited}$ 來標記是否已經出現過該數字，當遇到重複的數字時，即可結束模擬。由於 $4$ 位數的數字最多有 $10000$ 種，因此可以使用一個長度為 $10000$ 的陣列來標記是否出現過該數字。

令 $ans$ 表示不同的數字數量，初始值為 $0$ 。當遇到一個新的數字時， $ans$ 加一，並標記該數字已經出現過。由於要取出中間的 $4$ 位數，我們可以使用 $a_{i+1} = \lfloor \frac{(a_i^2)}{100} \rfloor \mod 10000$ 來計算下一個數字。在遇到重複的數字時，即可結束模擬，並輸出不同的數字數量。

複雜度分析

時間複雜度： $\mathcal{O}(10^n)$ ，其中 $n$ 為中間的位數，本題中 $n=4$ ，最多需要遍歷 $10^n$ 個數字。
空間複雜度： $\mathcal{O}(10^n)$ ，需要一個陣列來標記是否出現過該數字。

import sys
input = sys.stdin.readline
def print(val=""):
    sys.stdout.write(str(val) + "\n")

while True:
    n = int(input())
    if n == 0:
        break
    ans = 0
    visited = [False] * 10000
    while not visited[n]:
        ans += 1
        visited[n] = True
        n = (n * n) // 100 % 10000
    print(ans)

#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
#define endl '\n'

bool visited[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    while (cin >> n && n) {
        int ans = 0;
        memset(visited, false, sizeof(visited));
        while (!visited[n]) {
            ans++;
            visited[n] = true;
            n = (n * n) / 100 % 10000;
        }
        cout << ans << endl;
    }
    return 0;
}