陣列遞歸

Question

我有一個任務，我想不通，任何指針會大加讚賞，它會像這樣：

有表示爲真/假，有一個陣列中的一系列的燈泡通過點擊每個燈泡的開關，您可以將其切換爲2個相鄰的燈泡（左起1個&右起第1個;如果點擊開關的燈泡邊緣 - 當然只有1個開關的燈泡）。

需要完成的是一種方法，接受一系列打開/關閉燈泡的陣列，另一個代表的另一個狀態在點擊某些開關後的第一個陣列。 所以遞歸必須用來找出是否有將改變陣列1陣列2

這裏開關點擊的組合年代方法的簽名：

public static boolean disco(boolean[] init, boolean[] target) 

將返回true，如果陣列的init可以轉換爲目標，否則返回false。 方法必須是靜態的，而不是使用環 &任何其他靜態和全局變量，只有本地。

實施例：

boolean[] init = {true, false, true, false, true, false}; 
boolean[] target = {false, true, false, true, false, true}; 

對於上面2個陣列，迪斯科（INIT，目標）將返回真，因爲切換的第一和第四燈泡將產生目標狀態（記得相鄰燈泡被切換以及）。

Answer 1

新版本

public static boolean disco(boolean[] init, boolean[] target) 
{ 
    return recurse(init,boolean,0); 
} 

public static boolean recurse(boolean[] init, boolean[] target, int min) 
{ 
    if (min == init.length) 
    if (init == target) 
     return true; 
    else 
     return false; 
    boolean[] temp = "init with a change at min"; 
    boolean a = recurse(init, target, min+1); 
    boolean b = recurse(temp, target, min+1); 
    return a||b; 
} 

新新版本

我打破它歸結爲三種情況：

案例1：長度％3 = 0
通過更換第一個燈泡和第二個燈泡，您只能在第三個燈泡上進行更改。 然後，更改爲4和5將使第6個唯一更改。我們看到我們可以改變每個燈泡的索引可以被3整除。
反向工作（從最後開始）我們可以做同樣的事情，但這次它向我們展示了我們可以用可被3整除的索引（i + 1）來更換燈泡。
結合這兩者，我們看到如果我們想改變一個指數0,1模3我們可以。但是，然後改變一個2，我們只需要改變一個相鄰的0,1對，然後在中間改變一個。所有這些都是可以解決的。

案例2：長度％3 = 1
就像第一種情況，但我們可以在0,2 MOD 3影響單一的變化，並且因此擠壓1個模3的情況。

案例3：長度％3 = 2
工作向前和向後僅產生箱子0 MOD 3.剩下的唯一移動我們進行兩處更改燈泡（因爲我們可以忽略於位置0的任何變化） 。改變1或2將顛倒兩個0所圍繞的位置，而改變0將交換在它們之間具有0的相鄰1,2個塊的奇偶校驗（如果繪製它，則更容易）。但是我迄今爲止所展示的是，0都可以被糾正，並且在任何相鄰的1,2中，如果他們錯了而不改變其他任何東西，你可以解決這兩個問題。如果有一個錯誤，那麼你將一個變化傳播給一個相鄰的1,2。如有必要，可以移動此更改。這意味着1,2個位置的任何偶數個錯誤都可以被固定，但是奇數不能。位置0的所有錯誤都可以修復。

public static boolean disco(boolean[] init, boolean[] target) 
{ 
    if (init.length%3 == 0 || init.length%3 == 1) 
    return true; 
    return recurse(init,target,0, true); 
} 

public static boolean recurse(boolean[] init, boolean[] target, int index, boolean even) 
{ 
    if (index = init.length) 
    return even; 
    if (init[index] != target[index] && index%3 != 0) 
    even = !even; 
    return recurse(init, target, index+1, even); 
} 

Answer 2

因此，這裏的文字我會怎麼做：

如果仍有隻是小於或等於3的燈泡，它很容易檢查它們是否可以切換，以便它是正確的。

如果有三個以上的燈泡，請執行下列操作：

檢查，如果第一個球是正確的。如果是這樣，用第二個燈泡開始的子陣列遞歸地繼續。

如果第一個燈泡不正確，切換第二個燈泡（切換第一個燈泡不會工作，因爲之前的燈泡切換回來）。現在，第一個燈泡是正確的。繼續從第二個燈泡開始的子陣列。

Answer 3

提示：讓A1，A2，...，AK，...，一個是輸入和B1，B2，...，BK，...，BN是所需的輸出。

您可以遞歸測試左側和右側，然後合併結果。棘手的部分是結合結果。

從左側開始。

1. 測試a1，a2，...，ak，真正的b1，b2，...，bk，真。
   1. 如果爲真，則測試a1，a2，...，ak到b1，b2，...，bk。
      1. 如果真，那麼從A1方案，A2，...，ak至B1，B2，...，BK不能包括撥動開關第k個
      2. 如果爲假，則來自A1的解決方案，A2， ...，ak到b1，b2，...，！bk必須包括切換第k個開關
   2. 如果爲假，則測試a1，a2，...，ak到b1，b2，... ，BK
      1. 如果真，那麼從A1方案，A2，...，ak至B1，B2，...，BK必須包括撥動開關第k個
      2. 如果爲false，那麼從A1 soluation，A2，...，ak至B1，B2，...！BK不能包括撥動開關第k個

經過兩次測試在左側，您可以在右側執行類似的測試。你將能夠結合測試的值，因爲你會知道第k個開關是否被切換。

Answer 4

感謝所有您的幫助，這是我想出了：

public static boolean disco(boolean[] init, boolean[] target) 
{ 
    if (java.util.Arrays.equals(init, target)) { 
     return true; 
    } else { 
     return disco(init, target, 0); 
    } 
} 

private static boolean disco(boolean[] init, boolean[] target, int i) 
{ 
    if (i > init.length-1) { 
     return false; 
    } 

    disco(init, target, i+1); 
    boolean t = false; 

    if (init[i] != target[i]) { 
     switchBulb(init, target, i); 
    } 

    if (java.util.Arrays.equals(init, target)) { 
     t = true; 
    } 

    return t; 
} 

private static void switchBulb(boolean[] init, boolean[] target, int i) 
{ 
    if ((i > 1) && (init[i-1] != target[i-1]) && (init[i-2] != target[i-2])) { 
     // If there's a series of 3 opposite-to-target bulbs, switch the middle one & from both sides 
     init[i-1] = !init[i-1]; 
     init[i] = !init[i]; 
     init[i-2] = !init[i-2]; 
    } else if (i > 0 && i < init.length-1) { 
     // There's only 1 bulb or 2 adjacent bulbs that are opposite of target. 
     if (i == 1 && (init[0] != target[0])) { 
      // First 2 bulbs are opposite of target's, so switch the 1st one. 
      init[i-1] = !init[i-1]; 
      init[i] = !init[i]; 
     } else if ((i == init.length-2) && (init[i+1] != target[i+1])) { 
      init[i+1] = !init[i+1]; 
      init[i] = !init[i]; 
     } else { 
      init[i] = !init[i]; 
      init[i-1] = !init[i-1]; 
      init[i+1] = !init[i+1]; 
     } 
    } else { 
     // First bulb or last bulb. 
     init[i] = !init[i]; 
     if (i == 0) { 
      init[i+1] = !init[i+1]; 
     } else { 
      init[i-1] = !init[i-1]; 
     } 
    } 
} 

我覺得我使用遞歸這裏是最小的，如果被正確使用遞歸可乾淨多了。 有什麼想法？ 我在談論switchBulb函數，它可以用一點點複雜的遞歸邏輯交換，或者我錯了嗎？

如同，如果您只是逐個遍歷燈泡並與目標陣列進行比較，則不需要爲燈泡的所有組合（如示例）進行正確的設置，那麼如何模擬隨機燈泡切換遞歸？或者有一種模式？必須有，如果沒有，它將如何知道何時停止？

我想我得到了解決，以後後，如果任何人的興趣......