c - C 程序重新排列检查器

Question

我试图看看我是否可以将这个名为将检查器移动到 C 程序中的数学难题编码。假设我们有 4 个空白点，以及 6 个黑白棋交替的棋子，例如 0,0,0,0,b,w,b,w,b,w

现在您只能成对移动跳棋。一次 2 个，将它们滑到空位，您不能打扰它们的顺序。这本书展示了这一点，分三个步骤完成，如下所示。

0,0,0,0,b,w,b,w,b,w 开始

0,0,w,b,b,0,0,w,b,w 第一次通过

0,0,w,b,b,b,w,w,0,0 秒通过

w,w,w,b,b,b,0,0,0,0 第三遍

我研究过诸如归并排序和冒泡排序之类的算法。但他们似乎并不适合我编写代码来解决这个问题。

我已经将它放入一个数组中。从 4-9 运行 for 循环，因为这些不是空的。比较左右，然后有逻辑移动它。但是我对如何在 C 代码中实现这一点感到困惑。for 循环和比较不是问题。这是移动它们的逻辑，直到我一开始就得到三个白色块。

标签： csortingmathpuzzle

Answer 1

一个评论是对的，没有通用的排序算法，稍后你会发现问题是缺少严格的顺序。因此，让我们尝试从头开始设计一个。这个答案并不完整，只是关于如何解决此类问题的想法。

由于您的代码片段是一种已知方法的实现，它不会有太大帮助。所以让我们开始吧：您的第一种方法不应该介意运行时的复杂性，而是要获得正确的对象。我们试图概括。已经评论说双元素交换是关键。因此，拥有 9(n) 个元素使其成为 n-1 对。这些是您拥有的字母的有序对。这些是00 0w 0b w0 ww wb b0 bw bb，给它们起新名称可能会有所帮助，例如 A B C D E F G H I 数学它们与第二个版本的一些限制相同：A 只能跟随 B 和 C 等等。你可以只写两种方法来翻译它们。所有交换和检查操作都将在此版本上完成。

这里是缺失顺序的问题：就像没有答案对于例如 D 和 G 哪个更大/更小，并且对于排序算法的问题没有任何价值。也许以后有。

交换：一个必须是A=00，另一个必须距离该索引超过 1 个索引。这使得识别交换索引的一侧变得容易（冷的最多 2 个元素）（或在均衡分布层（n/3）上）交换后相邻元素会改变它们的值！

我们想去哪里：我们需要某个序列www意味着一个必须是 E 和一个额外的 w，所以我们需要寻找BE, ED, EF, HE ,generalizedBE..E, E..ED, E..EF, HE..E

所以对于核心算法：一次思考一步，这意味着有点递归。从中我们可以检查机会树*。当不再有（没有地方可以交换）时，我们处于死胡同，A所以我们停止递归，或者www如果我们只寻找一个解决方案，我们找到了一个解决方案，否则将该树中的路径附加到解决方案列表，直到你有足够的. 所以迭代所有A的 s 然后剩下的索引离它一个索引。每个迭代都将具有 A (a) 的参数 swap-index、另一个 swap-index (i) 和您的 Array T

通常，您现在会在递归树中寻找模式和机会：

第一：交换永远不会破坏 A，所以总会有机会继续，但是：新的交换对不能是旧的交换对（它只会回到树中）。遍历不会结束（因为总是有一个 A），所以没有直接的递归调用，或者至少没有递归深度的中断条件。可以通过必须检查的树创建一个任务列表，每个元素包含一个(a,i,T)或一个序列[(a0,i0),...,(an,in)]，并且您的递归调用被该元素的追加替换到列表中。

第二：不断变化的邻居中的模式：如果一个人想创建Es ，有一些方法可以接近它们（只需检查哪些方法组合到ww），这些是交换的主要候选者，并且它们越接近，它们应该越被首选。由于这些方式是有限的，它们会不时重复。使用这种模式，交换的选项会大大减少。然后，这些模式也可以被您的新字母序列替换。因此，您会寻找三连音，例如“BAH”和“CDC”，它们在交换内部字母时会变为新的三连音。这可以制成表格，然后可以对该表进行评级、排序，并且在检查时需要应用该顺序。

由于您直接要求以数学或算法方式处理此类问题，因此这应该是一种看待事物的方式。一般来说：花时间给你的结构命名。或者说到编程，我想是 Stroustrup 曾经说过：如果你能想到，就让它成为一门课！

*对于所有喜欢评论的人：蛮力...指数复杂度yadda yadda，我完全意识到这一点，这是设计步骤！