14

この質問はインタビューで尋ねられ、再帰/バックトラックを扱っています。ブール値の2つの配列があるとします：bool* sourceそしてbool* target、それぞれが同じ長さですn（source / target / nは引数として与えられます）。質問の目的は、操作スイッチを使用するように変換sourceすることです。target

  • 複数のトランスフォーンがある場合：それらのいずれかを提示します
  • 解決策がない場合：解決策がないことを主張する

定義：操作switch(int i, bool* arr)は、arr[i]とarr[i-1]およびarr[i + 1]の値を反転します（これらのインデックスが0 ... n-1の範囲にある場合）。

言い換えると、操作は通常3ビット（ iswitchとその隣接ビット）を反転しますが、最後は2ビットだけです。

例えば：

  • switch（0、arr）は、arr[0]とarr[1]の値のみを切り替えます
  • switch（n-1、arr）は、arr[n-1]とarr[n-2]の値のみを切り替えます

アルゴリズムについての提案を事前に感謝します。

4

3 に答える 3

5

バックトラッキングを使用すると、O(n) ソリューションを使用できます。なんで？

  1. 単一のインデックスでは、最悪の場合 1 つのスイッチがあります
  2. インデックスでのスイッチは、自分と 2 つの隣人のみを変更できます。

左から始めて右に移動し、後戻りするのが最善のアプローチです。

いつでも、最大で 2 ステップ戻る必要があります。たとえば、インデックス n にいる場合、インデックス n-1 のみを変更できますが、インデックス n-2 を変更することはできません。より正確には、インデックス n+2 に到達したときに、インデックス n のみを確認する必要があります。

最悪の 2 つのソリューションを持つことができます。

解決策 (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]

最も単純な解決策は、2 つの for ループを実行するだけであることがわかります。最初のソリューションは最初のライト/スイッチを設定し、2 番目は設定しません。その後、残りのすべての切り替えが決定されます

#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()
于 2011-09-03T11:20:56.843 に答える
4

私が問題を理解している限り、主な観察結果は、どの位置でも複数のスイッチを実行する必要がないということです。これは、2 回の切り替えはまったく切り替えないことと同じであるため、すべての偶数の切り替えは 0 回の切り替えと同等であり、すべての奇数回の切り替えは 1 回の切り替えと同等です。

もう 1 つのことは、スイッチの順序は重要ではないということです。i 番目と i+1 番目の要素を切り替えることは、i+1 番目と i 番目の要素を切り替えることと同じです。最終的に得られるパターンは同じです。

これら 2 つの観察結果を使用して、長さ n の配列に switch を適用するすべての可能な方法を簡単に試すことができます。これは、再帰的に行うことができます (つまり、インデックス i で切り替えを行う/インデックス i で切り替えを行わずに i+1 を試行する) か、すべての 2**nn ビットマスクを列挙し、それらのいずれかが作成されるまでそれらを使用して切り替えを適用します。目標値。

以下は、ソリューションでの私のハックです。配列を int にパックし、それらをビットマスクとして使用して操作を簡素化しました。これにより、ターゲット配列を取得するために切り替える必要があるインデックスが出力され、ターゲットが取得できない場合は「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;
}
于 2011-09-03T10:54:11.330 に答える
1

バックトラックは必要ありません。

N=3k および N=3k+1 (k>0) の場合、個々のビットを反転できることが簡単にわかります。したがって、これらのサイズの場合、解決策は常に存在します。フリップする必要がある各ビットのソリューションを追加することで、簡単に 1 つを見つけることができます。

3k+2 要素の場合、一部のビットを個別に反転し、他のビットをペアで反転することしかできません。つまり、ビット 2、5、8... を個別に反転することも、0、1、3、4、6、... のうち任意の 2 つを同時に反転することもできます。したがって、解決策は、反転する必要がある位置 0、1、3、4、6、8 ... に偶数のビットがある場合にのみ存在します。ここでも、各ビットまたはビット ペアのアルゴリズムを考え出すのは簡単です。それらを合計して解を得る。

于 2011-09-04T20:20:18.747 に答える