j057 - 11634 - Generate random numbers

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作 von Neumann 的中間平方法偽隨機數生成器，並計算給定初始值 a0 產生多少個不同的數字，直到產生重複的數字為止。初始值 a0 為四位數，生成過程包含平方、補零至八位數，以及取中間四位數。

解題思路

這題的核心在於模擬中間平方法生成隨機數的過程，並記錄生成的數字，直到出現重複的數字。使用 set 資料結構來儲存已生成的數字，因為 set 可以自動去除重複的元素，並且提供快速的查找操作。

1. 讀取初始值 a0。
2. 如果 a0 為 0，則結束程式。
3. 建立一個 set 來儲存已生成的數字。
4. 將 a0 加入 set。
5. 重複以下步驟，直到生成的數字已存在於 set 中：
   • 計算 a0 的平方。
   • 將平方後的結果補零至八位數。
   • 提取中間四位數作為新的 a0。
   • 將新的 a0 加入 set。
6. 輸出 set 的大小，即不同的數字個數。

複雜度分析

• 時間複雜度: O(k)，其中 k 是產生重複數字前的迭代次數。在最壞情況下，k 可能很大，但由於數字的範圍有限，通常 k 不會太大。
• 空間複雜度: O(k)，因為 set 儲存了 k 個不同的數字。

程式碼

#include <iostream>
#include <set>
using namespace std;
int n;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> n){
		if(n==0)break;
		set <int> st;
		while(!st.count(n)){
			st.insert(n);
			n*=n;
			n=n%1000000;
			n/=100;
		}
		cout << st.size() << "\n";
	}
}