一点一点前进...

0%

隐藏的平方数 | 欧拉项目 | 206题

发表于 分类于 ， Disqus：

欧拉项目的第206题描述如下：
找出唯一一个符合如下条件的数字：它的平方是具有1_2_3_4_5_6_7_8_9_0形式的数。每个_都代表了单个数字。

首先，我们对题目给出的形式做一个分析。
平方数最后一个数字是零，那么我们要找的数字（假设是A）最后一位是零。A最后一位是零，那么平方之后的数字末尾有两个零。
所以，问题可以转化为找到一个数字（假设是B），平方具有1_2_3_4_5_6_7_8_9的形式。这里的B = A / 10。
现在，我们构造一个验证一个数的平方是否满足题意的正则表达式： 

1
return Regex.IsMatch((i * i).ToString(), @"1\d2\d3\d4\d5\d6\d7\d8\d9");

然后，构造一个循环去找这个数。
其实呢，题目中说了，一定存在这样一个数，那么我们从最小可能满足题意的数100000003开始计算就好了，不用管循环的上限。 

1
for (long i = 100000003; ; )

再进一步考虑，既然肯定有满足题意的数字，那么平方后第一位肯定是1，不用我们自己去做判断了。于是，我改写了判定的做法： 

1
2
string s = (i * i).ToString();
return s[2] == '2' && s[4] == '3' && s[6] == '4' && s[8] == '5' && s[10] == '6' && s[12] == '7' && s[14] == '8';

一切就绪，让程序跑起来了，大概过了十几秒，结果出来了。
但是程序还能进一步优化。
考虑平方数最后一位是9，只有尾数是3或者7的数字满足题意。那么，添加一个判断让循环更快： 

1
2
3
4
5
6
7
8
if (i % 10 == 3)
{
    i += 4;
}
else
{
    i += 6;
}

答案几乎一瞬间就出来。

欧拉项目中的部分题目，由于数字不是很大，用最原始最暴力的算法，也能很快（小于1分钟）得到结果。但是，如果愿意进一步分析下，提高一下效率，总能在几秒（甚至是小于1秒）这个量级得到结果。