Random numbers are often used in programming games and scientific researches, but also they could be useful even in business applications (to generate unique user keys, passwords etc.). We are going to learn how they are generated and have a practice with some simple of simpler methods.
Here is one of the earliest methods for producing sequence of seemingly independed (i.e. pseudorandom) numbers:
- Choose some initial value with 4 digits (i.e. in range
0000 ... 9999). - Multiply it by itself (i.e. raise to power 2) to get value consisting of 8 digits (add leading zeroes if necessary).
- Truncate two first and two last digits in decimal representation of this result.
- New value will contain 4 digits and it is the next value of a sequence.
- To get more values, repeat from step 2.
Example:
5761 - let it be the first number
5761 * 5761 = 33189121 - raised to power 2
33(1891)21 => 1891 - truncate to get the middle
1891 - it is the second number in the sequence
1891 * 1891 = 3575881 - raised to power 2 (add leading zero to get 8 digits)
03(5758)81 => 5758 - truncate to get the middle
5758 - it is the third number in the sequence (and so on...)
It is obvious that sooner or later each sequence will come to a kind of loop, for example:
0001 -> 0000 -> 0000 - came to loop after 2 iterations
4100 -> 8100 -> 6100 -> 2100 -> 4100 - came to loop after 4 iterations
You will be given initial numbers for several sequences. For each of them report the number of iterations needed to come to repetition.
Input data will contain amount of initial values in the first line. Second line contains initial values themselves, separated by spaces.
Answer should contain number of iterations for sequences with such initial values to come to the loop.
Example:
input data:
3
0001 4100 5761
answer
2 4 88
这个问题无非是迭代，当发现数字重新出现时，看看用了多少步。
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
int neumann(int x);
int middle4(int x);
using namespace std;
int main() {
ifstream infile("data/id24.txt");
string line;
getline(infile, line);
int n;
stringstream ss(line);
ss >> n;
int NUM;
getline(infile, line);
stringstream ssv(line);
for (int i=0; i<n; i++) {
ssv >> NUM;
cout << neumann(NUM) << " ";
}
cout << endl;
return 0;
}
int neumann(int x) {
int n = 1;
set<int> mySet;
mySet.insert(x);
while(true) {
x = middle4(x);
if (mySet.find(x) != mySet.end()) {
break;
}
mySet.insert(x);
n++;
}
return n;
}
int middle4(int x) {
return (x * x / 100) % 10000 ;
}
main主要是在读数字，内容是：
12
5929 8397 6694 3779 3544 278 746 3234 7581 6173 8781 1451
而主要的代码在neumann，就是不断迭代而已，但这里需要缓存中间的结果，用于判断新的数字是否在前面有出现过，初学者容易想到动态数组，但效率不同，我这里用了set，用内置的find，二叉树搜索。
而迭代取中间4位数在middle4函数中，因为如果不够8位用0去填，所以不用去前两位，直接整除100去掉后两位，再取模拿后四位就行。
既然给了代码和数据，那么有必要贴一下答案，及运行时间（C++嘛总要显摆一下）。
time ./a.out
104 106 99 99 109 108 106 99 104 103 103 102
./a.out 0.00s user 0.00s system 95% cpu 0.004 total