10

初学者的一些定义：flip(n) 是七段显示字体编号的 180 度旋转，因此七段字体中的 2 将被翻转为 2。0、1、2、5、8 将映射到自己. 6 -> 9, 9 -> 6 和 3,4,7 未定义。因此，任何包含 3、4、7 的数字都不能翻转。更多示例：翻转（112）= 211，翻转（168）= 891，翻转（3112）=未定义。

（顺便说一句，我很确定翻转（1）应该是未定义的，但是作业说翻转（168）= 891所以关于这个任务翻转（1）是定义的）

最初的挑战：找到一个满足以下三个条件的整数 n > 0：

  1. 定义了翻转（n）并且翻转（n）= n
  2. 翻转(n*n) 被定义
  3. n 可被 2011 整除 -> n % 2011 == 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;
}
4

3 回答 3

4

启发式地（公认的实验最少并且主要依靠直觉），如果不从数学上优化搜索技术，您不太可能找到解决方案（例如，采用构造方法来构建一个不包含 3,4 的完美正方形， 7 并且是可翻转对称的。与优化计算相反，这不会显着改变复杂性）：

我将从满足 2 个标准的所有数字的列表开始（数字和它的翻转相同，即翻转对称，并且它是 2011 的倍数），小于 10^11：

192555261 611000119 862956298 988659886 2091001602 2220550222 2589226852 6510550159 8585115858 10282828201 12102220121 18065559081 18551215581 19299066261 20866099802 22582528522 25288188252 25510001552 25862529852 28018181082 28568189582 28806090882 50669869905 51905850615 52218581225 55666299955 58609860985 59226192265 60912021609 68651515989 68828282889 69018081069 69568089569 85065859058 85551515558 89285158268 91081118016 92529862526 92852225826 95189068156 95625052956 96056895096 96592826596 98661119986 98882128886 98986298686

那里有 46 个数字，根据 10^11 的定义和 2011 的倍数，所有数字都可以翻转对称。看似满足这个条件的 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。

因此，随着搜索数量的增加，回文数的数量会减少，并且任何找到的回文数的正方形可翻转的概率也会降低 - 一个双刃剑。

剩下的就是找到某种密度比，并据此了解找到解决方案的可能性有多大……尽管直观地很清楚，从概率上讲，找到解决方案的可能性要小得多（这绝不排除一个或什至一个大存在解决方案的数量（可能是无限的？））。

祝你好运！我希望有人解决这个问题。与许多问题一样，解决方案通常不像在更快的机器上运行算法或以更多的并行性或更长的时间或诸如此类简单，而是使用更先进的技术或更创造性的方法来解决问题，自己更进一步的领域。答案，一个数字，（通常）比用于推导它的方法少得多。

于 2011-04-25T17:53:33.950 回答
2

您正在搜索所有可被 2011 整除的数字，然后检查它们是否是它们自己的翻转。但是在你达到 7 位数字之后，它自身翻转的条件比它在 2011 年可整除的条件更具限制性。所以我建议你改为遍历所有可以在没有的情况下构造的数字数字 3、4、7，然后构造自身翻转的数字，如果中间数字是 11、22、55 或 88，则可能挤压中间数字。然后到 2011 年测试可分性，然后测试是否n*n是可翻转的。

非常非常清楚n*n会遇到整数溢出的可能性。当你达到一个 5 位数的基础号码时，你的号码n将是 9 或 10 位数，并且n*n将是 18-21 位数。

于 2011-04-25T17:06:07.507 回答
-1

不一定是完整的解决方案，更像是可以帮助您的思维过程。

  1. n = flip(n) => n 是回文数（在 flip() 中旋转 180°），n 仅包含在 flip() 中映射到自身的数字，即：0、1、2、5、8
  2. 定义了翻转(n*n)。因此 n*n 可能不包含 3, 4, 7
  3. n % 2011 = 0。
  4. n > 0。
于 2011-04-25T16:43:23.977 回答