SPOJ PPATH，将给定的 4 位素数转换为另一个 4 位素数
SPOJ PPATH, Converting a given 4 digit prime to another 4 digit prime
在 SPOJ 问题 PPATH 中，我们得到了两个四位数的质数，我们必须通过一次改变一位数，以最少的步骤将第一个质数转换为第二个质数在每一步中，数字都应该是素数。如果素数不能以上述方式转换，我们必须输出 'IMPOSSIBLE'。
然而，甚至不考虑不可能情况的问题的解决方案已被接受，这导致人们猜想每个四位素数都可以按指定方式转换为任何其他四位素数。我无法证明这一点。是真的吗？我们如何正式证明它？还有，n位素数有没有一般结果？
那么你有一个无向图，它的顶点是一个 4 位素数，边连接两个相差 1 位的数。要求您找到从一个顶点到另一个顶点的最近路径。如果您找不到这样的路径，将产生不可能的结果。这意味着该图具有不止一个连通分量。如果你证明这个图有一个连通分量，它就保证了路径的存在。
我不知道如何以正式的方式证明它，但很容易检查上述图是否只有一个连通分量。您可以编写一个算法，其结果可以解释为 4 位图的特定情况的证明。
对于四位数字，这可以通过程序详尽地验证，但对于 n 位数字，我们必须从理论上证明它。
在 SPOJ 问题 PPATH 中，我们得到了两个四位数的质数，我们必须通过一次改变一位数，以最少的步骤将第一个质数转换为第二个质数在每一步中，数字都应该是素数。如果素数不能以上述方式转换，我们必须输出 'IMPOSSIBLE'。
然而，甚至不考虑不可能情况的问题的解决方案已被接受，这导致人们猜想每个四位素数都可以按指定方式转换为任何其他四位素数。我无法证明这一点。是真的吗？我们如何正式证明它？还有，n位素数有没有一般结果？
那么你有一个无向图，它的顶点是一个 4 位素数，边连接两个相差 1 位的数。要求您找到从一个顶点到另一个顶点的最近路径。如果您找不到这样的路径，将产生不可能的结果。这意味着该图具有不止一个连通分量。如果你证明这个图有一个连通分量，它就保证了路径的存在。
我不知道如何以正式的方式证明它，但很容易检查上述图是否只有一个连通分量。您可以编写一个算法，其结果可以解释为 4 位图的特定情况的证明。
对于四位数字，这可以通过程序详尽地验证，但对于 n 位数字，我们必须从理论上证明它。