欧拉项目题目52：找到一个最小整数x，使得2x，3x，4x，5x，6x和x具有相同的数字，只是顺序不同。
因为上面的题目可以编程去解决。我就去思考如何写出高效的程序解决它。因为网站上有提示，解决欧拉项目的问题，如果算法足够好，1分钟之内就能出结果。
下面是我的解题思路：
- 3x能被三整除，那么x也能被三整除。
- 5x能被五整除，那么x肯定要含有5或0。
- x首位是1，且小于1，是若干个6，因为x和6x的位数一样多。
- x首位是1，2x的首位就是2或者3，所以x肯定要包含2或3。
- x首位是1，4x的首位是4或5或6，所有x肯定要包含4或5，或6。
- x首位是1，6x的首位大于等于6，所有x肯定要有一个数字大于等于6。
- 根据上面的2,4,6三条，x至少三位。虽然我的直觉告诉我x是6位的数字。
懒得继续分析了，我觉得上述条件很多了，计算速度足够快了，于是写了下面的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67public static int GetAnswer()
{
for (int i = 3; i < 10; i++)
{
for (int j = (int)Math.Pow(10, i) + 2; j < (int)Math.Pow(10, i + 1) / 6; j += 3)
{
if (HasTwoOrThree(j) && HasZeroOrFive(j) && HasMoreThanSix(j) && HasFourOrFiveOrSix(j))
{
if (IsSameCombination(j, j * 6)
&& IsSameCombination(j, j * 5)
&& IsSameCombination(j, j * 4)
&& IsSameCombination(j, j * 3)
&& IsSameCombination(j, j * 2))
{
return j;
}
}
}
}
return 0;
}
static bool HasSpecifiedDigit(int number, int spec)
{
return number.ToString().IndexOf(spec.ToString()) > -1;
}
static bool HasZeroOrFive(int number)
{
return HasSpecifiedDigit(number, 0) || HasSpecifiedDigit(number, 5);
}
static bool HasTwoOrThree(int number)
{
return HasSpecifiedDigit(number, 2) || HasSpecifiedDigit(number, 3);
}
static bool HasFourOrFiveOrSix(int number)
{
return HasSpecifiedDigit(number, 4) || HasSpecifiedDigit(number, 5) || HasSpecifiedDigit(number, 6);
}
static bool HasMoreThanSix(int number)
{
return HasSpecifiedDigit(number, 9)
|| HasSpecifiedDigit(number, 8)
|| HasSpecifiedDigit(number, 7)
|| HasSpecifiedDigit(number, 6)
|| HasSpecifiedDigit(number, 5);
}
static bool IsSameCombination(int n1, int n2)
{
char[] s1 = n1.ToString().ToCharArray();
char[] s2 = n2.ToString().ToCharArray();
Array.Sort(s1);
Array.Sort(s2);
for (int i = 0; i < s1.Length; i++)
{
if (s1[i] != s2[i])
{
return false;
}
}
return true;
}
里面有很多判断都重复了，但是主要是为了对应我之前的分析。j += 3对应了x能被三整除。
不到0.1秒就显示出了答案：142857。在这一瞬间，我想到了1-6除以7的小数位。
1 | 1/7 = 0.14285714... |
每个小数的循环节都是六位，是142857按照顺序的轮换。
看样子我还是很有数学素养的，一看到142857，还能想起来除以7这个有点数学美的一组式子。哈哈。