3

我试图通过键入键 0-9 来找到一种“破坏保险箱”的算法。代码长度为 4 位。保险箱将打开，它将代码标识为输入的子字符串。意思是，如果密码是“3456”，那么下一次输入将打开保险箱：“123456”。（这只是意味着保险箱不会每输入 4 个键就重新启动一次）。

是否有一种算法，每次在序列中添加一个数字时，它都会创建新的 4 位数字（序列\字符串的最后 4 位数字的新组合）？

谢谢，公里。

编辑（我在几年前发布）：问题是如何确保每次我将输入（一位数字）设置到保险箱时，我都会生成一个以前没有生成的新的 4 位数字代码。例如，如果保险箱获得 3 位长的二进制代码，那么这应该是我的输入序列：

0001011100

因为对于每个输入，我都会得到一个以前没有生成的新代码（3 位长）：

000 -> 000
1 -> 001
0 -> 010
1 -> 101
1 -> 011
1 -> 111
0 -> 110
0 -> 100
4

3 回答 3

2

我发现您的问题有所减少：

让我们用以下方式定义有向图 G = (V,E)：

V = {所有可能的代码组合}。

E = {< u,v > | v 可以从 u 中通过添加 1 个数字（在末尾）得到，并删除第一个数字}。

|V| = 10^4。

每个顶点的 Din 和 Dout 等于 10 => |E| = 10^5。

您需要证明 G 中存在汉密尔顿循环 - 如果这样做，您可以证明存在解。

编辑1：

算法：

  1. 如上所述构造有向图 G。

  2. 计算哈密顿循环 - {v1,v2,..,vn-1,v1}。

  3. 按 v1 中的每个数字。

  4. X <- v1。

  5. 保险箱未打开时：

    5.1 X <- X 之后 Hamilton 路径中的下一个顶点。

    5.2 按 X 中的最后一个数字。

我们可以看到，因为我们使用了 Hamilton 循环，所以我们从不重复相同的子串。（最后 4 次按下）。

编辑2：

当然，汉密尔顿路径就足够了。

于 2012-07-03T19:59:58.663 回答
1

总而言之，我认为您正在尝试解决的问题以及对我如何解决该问题的一些解释。http://www.cs.swan.ac.uk/~charold/cpp/SPAEcpp.pdf

但是，您必须做一些技巧才能使其适合中国邮递员问题...想象一下解决二进制数字，三位数字字符串的问题。假设你有前两位数，然后问问你自己我有哪些选择？（关于下一个两位数的字符串？）你留下了一个有向图。

 /-\
/   V    
\-  00 ----> 01
      ^  /   ^|
       \/    ||
       /\    ||
      V  \   |V
 /-- 11 ---> 10 
 \   ^         
  \-/

解决中国邮递员，你将拥有所有组合并形成一个字符串现在的问题是，中国邮递员是否可以解决？有一些算法可以确定天气或 DAG 对于 CPP 是否可以解决，但我不知道这个特定的图表是否一定可以仅根据问题来解决。这将是一件好事来确定。但是，您确实知道您可以通过算法找出它是可以解决的，如果可以的话，您可以使用该论文（我认为）和在线提供的算法来解决它。

这里的每个顶点都有 2 条传入边和 2 条传出边。有 4 (2^2) 个顶点。

在全尺寸问题中有19683( 3 ^ 9 )顶点，每个顶点都有512 ( 2 ^ 9 )输出和输入顶点。总共会有

19683( 3 ^ 9 ) x 512 (2 ^ 9) = 10077696 edges in your graph.

解决方法：

1.) Create list of all 3 digit numbers 000 to 999.
2.) Create edges for all numbers such that last two digits of first number match first
two digits of next number. 

ie 123 -> 238 (valid edge) 123 -> 128 (invalid edge)

3.) use Chinese Postman solving algorithmic approaches to discover if solvable and
solve
于 2012-07-03T20:39:52.663 回答
0

我将创建一个子序列数组，在插入新数字时需要对其进行更新。因此，在您的示例中，它将开始为：

array = {1}

然后

array = {1,2,12}

然后

array = {1,2,12,3,13,23,123}

然后

array = {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234}

并且当您有一个已经在 length=4 的序列时，您不需要继续连接，只需删除序列的第一个数字并在末尾插入新数字，例如，使用最后一个 item 1234，当我们添加5它会变成2345如下：

array = {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234,5,15,25,125,35,135,235,1235,45,145,245,1245,345,1345,2345,2345}

我相信这不是遍历给定序列的所有子序列的非常复杂的方法。

于 2012-07-03T20:24:08.760 回答