首页 > ACM题库 > HDU-杭电 > HDU 1324 Pseudo-Random Numbers[解题报告] C++
2013
12-09

HDU 1324 Pseudo-Random Numbers[解题报告] C++

Pseudo-Random Numbers

问题描述 :

Computers normally cannot generate really random numbers, but frequently are used to generate sequences of pseudo-random numbers. These are generated by some algorithm, but appear for all practical purposes to be really random. Random numbers are used in many applications, including simulation.
A common pseudo-random number generation technique is called the linear congruential method. If the last pseudo-random number generated was L, then the next number is generated by evaluating ( Z x L + I ) mod M, where Z is a constant multiplier, I is a constant increment, and M is a constant modulus. For example, suppose Z is 7, I is 5, and M is 12. If the first random number (usually called the seed) is 4, then we can determine the next few pseudo-random numbers are follows:

As you can see, the sequence of pseudo-random numbers generated by this technique repeats after six numbers. It should be clear that the longest sequence that can be generated using this technique is limited by the modulus, M.

In this problem you will be given sets of values for Z, I, M, and the seed, L. Each of these will have no more than four digits. For each such set of values you are to determine the length of the cycle of pseudo-random numbers that will be generated. But be careful: the cycle might not begin with the seed!

输入:

Each input line will contain four integer values, in order, for Z, I, M, and L. The last line will contain four zeroes, and marks the end of the input data. L will be less than M.

输出:

For each input line, display the case number (they are sequentially numbered, starting with 1) and the length of the sequence of pseudo-random numbers before the sequence is repeated.

样例输入:

7 5 12 4
5173 3849 3279 1511
9111 5309 6000 1234
1079 2136 9999 1237
0 0 0 0

样例输出:

Case 1: 6
Case 2: 546
Case 3: 500
Case 4: 220

题目链接:点击打开链接

题意:给出四个数Z,I,M,L,L=(Z*L+I)%M,直到得到一个原来出现过的L,该运算便开始循环,求出L的循环周期。

#include<iostream>
using namespace std;
int j[1000000];
int main()
{
  int ans,z,i,m,l,t,x,k,y;
   t=1;
  while(~scanf("%d %d %d %d",&z,&i,&m,&l))
  {
    if(z==0&&i==0&&m==0&l==0)
        break;
 x=0;
    for(ans=0;;ans++)
    {
      j[ans]=l;
      l=(z*l+i)%m;
       for(k=0;k<=ans;k++)
          if(l==j[k])
          {
              y=k;
              x=1;
              break;
          }
          if(x==1)
              break;
    }
    printf("Case %d: %d\n",t++,ans-y+1);
  }
  return 0;
}

 

解题报告转自:http://blog.csdn.net/hncu1106401/article/details/8557786


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3