数据结构
网络
关系数据库管理系统(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 次浏览
广告