2014
02-24

# Generate random numbers

John von Neumann suggested in 1946 a method to create a sequence of pseudo-random numbers. His idea is known as the "middle-square"-method and works as follows: We choose an initial value a0, which has a decimal representation of length at most n. We then multiply the value a0 by itself, add leading zeros until we get a decimal representation of length 2 × n and take the middle n digits to form ai. This process is repeated for each ai with i>0. In this problem we use n = 4.

Example 1: a0=5555, a02=30858025, a1=8580,…

Example 2: a0=1111, a02=01234321, a1=2343,…

Unfortunately, this random number generator is not very good. When started with an initial value it does not produce all other numbers with the same number of digits.

Your task is to check for a given initial value a0 how many different numbers are produced.

The input contains several test cases. Each test case consists of one line containing a0 (0 < a0 < 10000). Numbers are possibly padded with leading zeros such that each number consists of exactly 4 digits. The input is terminated with a line containing the value 0.

The input contains several test cases. Each test case consists of one line containing a0 (0 < a0 < 10000). Numbers are possibly padded with leading zeros such that each number consists of exactly 4 digits. The input is terminated with a line containing the value 0.

5555
0815
6239
0

32
17
111

Hint
Note that the third test case has the maximum number of different values among all possible inputs.


#include <stdio.h>
#include <math.h>
#include <string.h>
const int MAXN=10030;
int a[MAXN];
int main(int argc, char *argv[])
{
long n;
while(scanf("%ld",&n) && n)
{
int count=1;
memset(a,0,sizeof(a));
a[n]=1;//这里没写wa一次，初始的n忘记存储了
while(1)
{
long t=n*n/100;
n=t%10000;
a[n]++;
if(a[n]==2) break;
count++;
}
printf("%d\n",count);
}
return 0;
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？