面试问题，递归+回溯

Question

面试问题，递归+回溯

14

这个问题是关于递归/回溯的面试题，涉及IT技术。假设我们有两个布尔数组：bool* source 和 bool* target，它们都有相同的长度n（source/target/n作为参数给出）。问题的目标是使用操作 switch将source转换为target。

如果有多个变换：请给出其中任何一个。
如果没有解决方案：请断言没有解决方案。

定义：操作switch(int i, bool* arr) 翻转 arr[i] 、arr[i-1] 和 arr[i+1] 的值（如果这些索引在范围0...n-1内）。

换句话说，switch 操作通常会翻转三个位（i及其邻居），但仅在两端翻转两个位。

例如：

switch(0,arr) 将只切换arr[0]和arr[1]的值。
switch(n-1,arr) 将只切换arr[n-1]和arr[n-2]的值。

感谢您提前对算法的建议。

- YAKOVM

听起来你是在说switch(n)会翻转位于n的比特和两侧的比特，但只有在这些位置上有数据时才会翻转；换句话说，它通常会翻转三个比特，但在两端只会翻转两个。目标是将source中的比特模式转换为target中的比特模式。所有这一切都类似于一个经典游戏，只不过这是在一维而不是二维中进行的。我理解得对吗？这个问题听起来很熟悉，我想我以前在某个地方见过它。 - Tom Zych

@Tom Zych - 你理解得很正确！这是哪个游戏？你能给我参考吗？ - YAKOVM

@Mu Qiao - 我已经更新了问题。请看Tom Zych的解释 - 它很明确。 - YAKOVM

1

@Tom Zych - 当 source = {1,0} 或 source = {0,1} 且 target = {1,1} 时，无法解决。 - YAKOVM

3

这是“灭灯游戏”（Lights Out）的一维版本。https://secure.wikimedia.org/wikipedia/en/wiki/Lights_Out_(game) - Svante

显示剩余4条评论

3个回答

4

据我所了解，问题的主要观察是我们从不需要在任何位置执行多次交换。这是因为两次交换等于不交换，所以所有偶数次交换相当于0次交换，所有奇数次交换与1次交换一样。

另一个问题是交换顺序不重要。交换第i个和i+1个元素等同于先交换i+1个元素再交换第i个元素。最终得到的模式是相同的。

利用这两个观察，我们可以简单地尝试应用交换到n长度数组的所有可能方式。这可以通过递归(即在索引i处进行交换/不在索引i处进行交换，然后尝试i+1)或枚举所有2 ** n n位位掩码并使用它们来应用交换，直到其中一个创建目标值。

以下是我的解决方案。我将数组打包成整数，并将它们用作位掩码以简化操作。这将打印出需要交换的索引以获取目标数组，并在无法获得目标时打印“Impossible”。

#include <cstdio>

int flip(int mask, int bit){
    return mask^(1<<bit);
}

int switch_(int mask, int index, int n){
    for(int i=-1;i<=+1;i++){
        if ((index+i)>=0 && (index+i)<n) mask=flip(mask,index+i);
    }
    return mask;
}

int apply(int source, int flips, int n){
    int result=source;
    for(int i=0;i<n;i++){
        if (flips&(1<<i)) result=switch_(result,i,n);
    }
    return result;
}

void solve(int source, int target, int n){
    bool found=false;
    int current=0;
    int flips=0;
    for(flips=0;flips<(1<<n) && !found;flips++){
        current=apply(source,flips,n);
        found=(current==target);
    }
    if (found){
        flips--;
        for(int i=0;i<n;i++){
            if (flips&(1<<i)) printf("%d ",n-i-1); //prints the indices in descending order
        }
        printf("\n");
    }
    else{
        printf("Impossible\n");
    }
}

int array2int(int* arr, int n){
    int ret=0;
    for(int i=0;i<n;i++){
        ret<<=1;
        if (arr[i]==1) ret++;
    }
    return ret;
}
int main(){
    int source[]={0,0,0,0};
    int target[]={1,1,1,1};
    int n=4;
    solve(array2int(source,n),array2int(target,n),n);
    return 0;
}

- MAK

是的，但那需要指数时间。希望我们能做得更好。我现在正在编码我的想法，看看它的工作效果如何。 - Tom Zych

2

+1：虽然这种方法效率低下，而且我自己也对多项式解法很感兴趣，但这正是OP所要求的。 - IVlad

没时间去理解这段代码，但它似乎是错误的。使用 source[]={0,0,0,0,0,0,0,0}; 和 target[]={1,0,0,0,0,0,1,1}; 时，它打印了 0 1 3，显然是错误的，因为它不会翻转最后的位。（这些数字是我的程序没有找到解决方案的数字 - 我试图检查一下。） - Tom Zych

@Tom Zych：你改变了n的值吗？ - MAK

糟糕！忽略了那个。那个可行。然而，它仍然在这里失败：source[]={1,1,1,0,0,0,1,1};和target[]={0,1,1,0,1,1,1,1};，其解决方案为1 2 4和0 2 3 6 7。它打印出3 5 6。 - Tom Zych

@Tom Zych：发现得好！我打印索引的方式有一个错误。我正在更新我的代码。谢谢。 - MAK

1

回溯不是必要的。

很容易看出，对于N=3k和N=3k+1（k>0），我们可以翻转每个单独的位，因此对于这些大小，总是存在解决方案。我们可以很容易地想出一个解决方案，将需要翻转的每个位的解决方案相加即可。

对于3k+2个元素，只能单独翻转一些位，其他位则需要成对翻转。也就是说，我们可以单独翻转第2、5、8...位，或同时翻转0、1、3、4、6...位置中的任意两个位。因此，仅当0、1、3、4、6、8...位置上必须翻转的位数为偶数时，才存在解决方案。同样，我们可以很容易地想出每个位或位对的算法，并将它们相加以获得解决方案。

- n. m.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Luka Rahne · Accepted Answer

使用回溯法可以得到O(n)的解决方案。为什么呢？

1.在单个索引处，你最多只会有一个开关。

2.在索引处交换只会改变自身和两个相邻的开关。

从左向右开始并回溯是最好的方法。

任何时候，你最多只需要后退两步。例如，如果你在索引n处，你只能更改索引n-1，但不能更改索引n-2, 并且当你到达索引n+2时，你只需要检查索引n。

你最多可能会有两个解决方案。 python代码如下：

def light(arr,n):
    for i in range(max([0,n-1]),min([len(arr),n+2])):
        arr[i] = not arr[i]
    return arr

goal = [True]*500
def trackback(arr,index,moves):
    if index == len(arr):
        if arr == goal:
            print(moves)
        return

    if index > 1:
        if arr[index-2] != goal[index-2]:
            return
    #print(arr,index,moves)
    #do not make switch
    trackback(arr,index+1,moves)
    #make switch
    moves=moves+[index]
    arr=light(arr,index)
    trackback(arr,index+1,moves)
    arr=light(arr,index) #undo move


arr=[False]*500
trackback(arr,0,[])

输出

[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139, 142, 145, 148, 151, 154, 157, 160, 163, 166, 169, 172, 175, 178, 181, 184, 187, 190, 193, 196, 199, 202, 205, 208, 211, 214, 217, 220, 223, 226, 229, 232, 235, 238, 241, 244, 247, 250, 253, 256, 259, 262, 265, 268, 271, 274, 277, 280, 283, 286, 289, 292, 295, 298, 301, 304, 307, 310, 313, 316, 319, 322, 325, 328, 331, 334, 337, 340, 343, 346, 349, 352, 355, 358, 361, 364, 367, 370, 373, 376, 379, 382, 385, 388, 391, 394, 397, 400, 403, 406, 409, 412, 415, 418, 421, 424, 427, 430, 433, 436, 439, 442, 445, 448, 451, 454, 457, 460, 463, 466, 469, 472, 475, 478, 481, 484, 487, 490, 493, 496, 499]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204, 207, 210, 213, 216, 219, 222, 225, 228, 231, 234, 237, 240, 243, 246, 249, 252, 255, 258, 261, 264, 267, 270, 273, 276, 279, 282, 285, 288, 291, 294, 297, 300, 303, 306, 309, 312, 315, 318, 321, 324, 327, 330, 333, 336, 339, 342, 345, 348, 351, 354, 357, 360, 363, 366, 369, 372, 375, 378, 381, 384, 387, 390, 393, 396, 399, 402, 405, 408, 411, 414, 417, 420, 423, 426, 429, 432, 435, 438, 441, 444, 447, 450, 453, 456, 459, 462, 465, 468, 471, 474, 477, 480, 483, 486, 489, 492, 495, 498]

您可以看到，最简单的解决方案就是运行两个for循环。第一个解决方案设置第一个灯/开关，第二个解决方案不设置。然后决定所有剩余的开关。

#do not switch first light
for i in range(1,len(goal)+1):
    if goal[n-1] != arr[n-1]:
        light(arr,n)
check_solution()

#switch first light
switch(arr,n)
for i in range(1,len(goal)+1):
    if goal[n-1] != arr[n-1]:
        light(arr,n)
check_solution()