启动器的一些定义:flip(n)是七段显示字体编号的180度旋转,因此一个2段的七段字体将翻转为2. 0,1,2,5,8将映射到自己.6 - > 9,9 - > 6和3,4,7未定义.因此,任何包含3,4,7的数字都不会被翻转.更多示例:flip(112)= 211,flip(168)= 891,flip(3112)=未定义.
(顺便说一下,我敢肯定,翻转(1)应该是不确定的,但功课说,翻转(168)= 891所以对此分配翻转(1)定义)
原始挑战:找到一个整数n> 0,它包含以下三个条件:
我们在下面找到的解决方案似乎有效,但至少在2011年找不到答案.如果我使用1991而不是(我搜索了一些问题可以解决的"基数")我得到了一个非常快速的回答说1515151就是那个.因此,基本概念似乎有效,但不适用于作业中给定的"基础".我在这里错过了什么吗？
用伪代码编写的解决方案(我们在Small Basic中有一个实现,我用Java编写了一个多线程):
for (i = 1; i < Integer.MaxValue; i++) {
n = i * 2011;
f = flip(n, true);
if (f != null && flip(n*n, false) != null) {
print n + " is the number";
return;
}
}
flip(n, symmetry) {
l = n.length;
l2 = (symmetry) ? ceil(l/2) : l;
f = "";
for (i = 0; i < l2; i++) {
s = n.substr(i,1);
switch(s) {
case 0,1,2,5,8:
r = s; break;
case 6:
r = 9; break;
case 9:
r = 6; break;
default:
r = "";
}
if (r == "") {
print n + " is not flippable";
return -1;
} elseif (symmetry && r != n.substr(l-i-1,1)) {
print n + " is not flip(n)";
return -1;
}
f = r + f;
}
return (symmetry) ? n : f;
}
启发式地（无可否认，实验最少，主要依靠直觉），如果不以数学方式优化搜索技术，您不太可能找到解决方案（例如，采用构造方法来构建不包含 3,4、 7 并且是翻转对称的。而不是优化计算，这不会显着改变复杂性）：
我将从满足 2 个标准的所有数字列表开始（该数字和它的翻转相同，即翻转对称，并且它是 2011 的倍数），小于 10^11：
192555261 611000119 862956298 988659886 2091001602 2220550222 2589226852 6510550159 8585115858 10282828201 12102220121 1806 5559081 18551215581 19299066261 20866099802 22582528522 25288188252 25510001552 25862529852 28018181082 28568189582 288060908 82 50669869905 51905850615 52218581225 55666299955 58609860985 59226192265 60912021609 68651515989 68828282889 69018081069 69 568089569 85065859058 85551515558 89285158268 91081118016 92529862526 92852225826 95189068156 95625052956 96056895096 9659282 6596 98661119986 98882128886 98986298686
那里有 46 个数字，全部根据 2011 年的定义和倍数翻转对称，小于 10^11。看起来满足这个条件的 2011 的倍数将变得越来越稀有，因为从统计上看，随着位数的增加，回文倍数将越来越少。
即对于任何给定范围，例如 [1, 10^11]（如上所述），有 46 个。对于等宽的相邻范围：[10^11+1, 2*10^11]，我们可能会猜测找到另外46个左右。但是，当我们继续使用 10 的更高次方相同宽度的间隔时，数字的数量是相同的（因为我们分析的是等宽度的间隔），尽管回文条件现在落在更多的数字上，因为数字的数量增加了。因此，接近无穷大时，我们期望任何固定间隔上的回文数接近 0。或者，更正式地（但没有证明）对于每个正值 N，概率为 0 的给定间隔（预定宽度）将具有超过 N 的倍数2011 年的回文。
因此，随着穷举搜索的继续，我们可以找到的回文数量将会减少。根据对于任何找到的回文正方形可翻转的概率，我们假设回文正方形的均匀分布（因为我们没有分析告诉我们其他情况，也没有理由相信其他情况），然后是任何给定正方形的概率可翻转的 d 位数字长度为 (7/10)^d。
让我们从我们发现的最小的正方形开始
192555261 ^ 2 = 37077528538778121
它已经有 17 位数字长，因此它被可翻转定义的概率约为 0.002（约 1/430）。但当我们到达列表中的最后一个时：
98986298686 ^ 2 = 9798287327554005326596
其长度为 24 位，被可翻转定义的概率小于 1/5000。
因此，随着搜索继续以更高的数量进行，回文的数量会减少，并且任何找到的回文正方形可翻转的概率也会减少 - 这是一个双刃剑。
剩下的就是找到某种密度比，并相应地看看找到解决方案的可能性有多大……尽管直观上很明显，从概率上讲，找到解决方案的可能性要小得多（这绝不排除一个甚至一个大的解决方案）存在许多解决方案（可能有无限多个？））。
祝你好运！我希望有人解决这个问题。与许多问题一样，解决方案通常并不像在更快的机器上运行算法或具有更多并行性或更长的时间等等那么简单，而是采用更先进的技术或更创造性的方法来解决问题，这自己更进一步的领域。答案是一个数字，（通常）比得出它的方法更不那么有趣。