資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：找出給定序列中的不同元素
假設我們得到三個整數n、x、y和z。我們必須根據給定的整數建立一個序列，其中序列的第一個專案是(x模231)。除了第一個元素外，序列中的其他元素ai = (a(i-1) * y + z) 模 231，其中1 ≤ i ≤ n - 1。我們必須找出我們建立的序列中不同整數的數量。
因此，如果輸入類似於n = 5，x = 1，y = 2，z = 1，則輸出將為5。
唯一的值是{1, 3, 7, 15, 31}。所以答案是5。
為了解決這個問題，我們將遵循以下步驟：
- MOD := 2^31
- 定義一個數組temp
- 將陣列temp的大小調整為MOD的值
- p := x mod MOD
- temp[p] := true
- ans := 1
- 對於初始化i := 1，當i < n時，更新（i增加1），執行：
- p := ((p * y) + z) mod MOD
- 如果temp[p]為true，則：
- 退出迴圈
- ans加1
- temp[p] := true
- 返回ans
示例
讓我們看看下面的實現，以便更好地理解：
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD = 2147483648;
int solve(int n, long long x, long long y, long long z) {
vector<bool> temp;
temp.resize(MOD);
long long p = x % MOD;
temp[p] = true;
int ans = 1;
for (int i = 1; i < n; ++i) {
p = ((p * y) + z) % MOD;
if (temp[p])
break;
++ans;
temp[p] = true;
}
return ans;
}
int main() {
cout<< solve(5, 1, 2, 1) <<endl;
return 0;
}輸入
5, 1, 2, 1
輸出
5
更新於：2021年10月20日
314 次瀏覽
廣告