首页 > 数据结构 > Hash表 > HDU 2991-Generate random numbers -数论-[解题报告]HOJ
2014
02-24

HDU 2991-Generate random numbers -数论-[解题报告]HOJ

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.

这道题我读了很久不知道什么意思,最后拿数带进去一个个的算,发现算到后来会出现循环的情况,这时候再读题就明白了

题目是说,给你一个四位数,其中可以包涵前导零,然后平方,平方后的结果如果不够八位数的话就补前导零,然后再从

第三位数字开始取四位数,再次进行平方,要求你计算总共有多少个不同的数字,原先以为4位数的平方会溢出,拿计算器

算了下9999平方也才8位,看来我想多了。

分析,这道题可以用哈希表进行存储,当每一位置的数到达了2说明开始数字循环了,以后出现的数字就会是重复的了

其中取四位数,可以先整除100;然后再对10000取余,当时我想的是用个for循环依次对10取余,在除以10,这样明显

麻烦很多

#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;
}

 

解题参考:http://blog.csdn.net/tdreamge/article/details/7333056


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

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