上一次接触 project euler 还是2011年的事情，做了前三道题，后来被第四题卡住了，前面几题的代码也没有保留下来。
今天试着暴力破解了一下，代码如下：
（我大概是第 172,719 个解出这道题的人）
program 4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.
using System; public class PlindromeNumber
{
static void Main()
{
long total;
long max = ;
int pre = ;
int post = ;
for(int i = ; i > ; i--)
{
for(int j = ; j > ; j--)
{
total = i*j;
if(CheckPlindromeNumber(total))
{
if(max < total)
{
max = total;
pre = i;
post = j;
}
}
}
}
Console.WriteLine("Max Plindrome Number is : " + max + " = " + pre + " * " + post);
} static bool CheckPlindromeNumber(long number)
{
bool result = false;
if(number/ == )
{
return false;
}
if( (number/ == number%) && (number/% == number/%) && (number/% == number/%) )
{
result = true;
}
return result;
}
}
试着使用 Vim 写了这样一段代码，后来又花了不少时间去配置 Vim。
作为一个 Vim 的新手，花费了不少时间，安装了 pathogen.vim 插件，然后装了 vim-csharp 插件，初步试用没有感觉有什么大的帮助。
题目做对之后，又看了一下别人的解题思路，其实之前也隐约想到过以下的两种办法，不过去没有最终分析出一个可行的办法。
解法一来自于 euler 论坛的 etatsui，就是假设这个 palindrome 是 abccba 的形式，那么：
palindrome = a * 100000 + b * 10000 + c * 1000 + c * 100 + b * 10 + a * 1
palindrome = 100001a + 10010b + 1100c
palindrome = 11(9091a + 910b + 100c) = m * n
其中 a, b, c 是 1 位数， m, n 是 3 位数
假设，11*10 < m < 11*99
（这个假设是一个比较有意思的地方，从上面的算式可以知道，palindrome 有一个因子是 11，那么我们可以假设 m 是包括这个因子的，又因为有 m 是 3 位数这样的限制，所以可以这样假设）
etatsui 提供的代码中有一个小的 bug，改正之后的代码如下：
using System; class Palindrome_etatsui
{
static void Main()
{
long num;
long result = ;
for(int a=; a>=; a--)
{
for(int b=; b>=; b--)
{
for(int c=; c>=; c--)
{
num = * a + * b + * c;
// Console.WriteLine(num);
for(int divider=; divider>=; divider--)
{
// look for divider that can divide
// and also doesn't make n > 999
if ((num%divider) == )
{
if ((num/divider) > )
{
break;
}
else
{
result = num * ; // found it
Console.WriteLine("Palindrom(etatsui) is : " + result);
return;
}
}
else
{
continue;
}
}
}
}
}
}
}
在 euler 的论坛上，还看到了 Begoner 有一个用笔来解答的方案，不过似乎有一点小瑕疵。
假设 palindrame 的两个因子为 abc 和 def，那么
abc * def = (100a + 10b + c)*(100d + 10e + f)
乘法运算得
100cd + 10ce + cf
1000bd + 100be + 10bf
10000ad + 1000ae + 100af
这个时候，Begoner 假设 palindrone 的第一个数字为 9 （我觉的这里有点问题），然后 cf 的末尾数一定是 9，而乘积为 9 的数，末尾只有三种可能：1 和 9，3 和 3，7 和 7。
所以，这两个因子应该以 9 开头，而以 1，3，4，9 结尾，并且其中一个一定能被 11 整除（关于被 11 整除的原因和上面的一个方法一样）。
而 900 到 1000 之间，能被 11 整除的，只有：902，913， 924， 935，946，957，968， 979， 990 这 9 个数。
从而满足以上两个条件的只有：913，957，979
这样就有：
(900 + 10 + 3)(900 + 10x + 3)
(900 + 50 + 7)(900 + 10x + 7)
(900 + 70 + 9)(900 + 10x + 1)
整理之后：
824439 + 9130x
867999 + 9570x
882079 + 9790x
然后可以让 x 从 9 到 0 开始检测。（Begoner 在这里只选取了第一个式子，然后得出 x 一定等于9，否则就不能满足让 palindrame 的第一位是 9，有点看不明白）
这个方法似乎没有办法用程序来表达，另外有比较明显的拼凑的痕迹，不推荐只是记录一下 Begoner 的思路。
参考链接：