模式生成遞歸

Question

我正在編寫一個程序，通過用0或1替換*來生成字符串1 * 0 *的所有可能組合。該程序只給出3個值並且缺少一個值。有人能幫我找出這個代碼中的問題嗎？

對於輸入1 * 0 *，此解決方案只給出3個結果：1000,1001,1101。缺少的值是1100.謝謝。

public class TestClass{ 
 
     public static void generateComb (char[] ch, int index) { 
 
      if (index == ch.length) 
 
      { 
 
       System.out.println (ch); 
 

 
       return; 
 
      } 
 
      if (ch[index]=='*'){ 
 

 
       ch[index] = '0'; 
 
       generateComb (ch, index+1); 
 
       ch[index] = '1'; 
 

 
       generateComb (ch, index+1);       
 
      } 
 
      else { 
 
       generateComb (ch, index+1); 
 
       
 
      } 
 
     } 
 
     
 
     public static void main (String[] args) throws Exception { 
 
     
 
      char[] chtest = {'1', '*', '0', '*'}; 
 
      generateComb(chtest, 0); 
 
     } 
 
    }

Answer 1

這裏發生的事情是，當你說ch[index] = '0';你改變這種對象，和你沒有設置該字符回爲*，因此第二後*變成了1，它不再被替換。這叫做通過引用,char[] ch是對字符串的引用。例如See this question。

這應該工作：

public class TestClass{ 
 
     public static void generateComb (char[] ch, int index) { 
 
      if (index == ch.length) 
 
      { 
 
       System.out.println (ch); 
 

 
       return; 
 
      } 
 
      if (ch[index]=='*'){ 
 

 
       ch[index] = '0'; 
 
       generateComb (ch, index+1); 
 
       ch[index] = '1'; 
 
       generateComb (ch, index+1); 
 
       ch[index] = '*'; // <-------------- here 
 
      } 
 
      else { 
 
       generateComb (ch, index+1); 
 
       
 
      } 
 
     } 
 
     
 
     public static void main (String[] args) throws Exception { 
 
     
 
      char[] chtest = {'1', '*', '0', '*'}; 
 
      generateComb(chtest, 0); 
 
     } 
 
    }

在每一輪發生了什麼事情的一個例子可能會有幫助：

• CH = [1，*，0，*] ，索引== 0
• ch = [1，*，0，*]，索引== 1 ch [1]更改爲'0'
• CH = [1，0，0，*]，索引== 2
• CH = [1，0，0，*]，索引== 3 CH [3]變爲 '0'
• CH = [1，0，0，0]，索引== 4 打印：1000返回到現有呼叫和ch [3]被改變爲 '1'
• CH = [1,0 ，0,1]索引== 4 打印：1001返回調用堆棧，ch [1]更改爲'1'
• ch = [1 ，1,0,1]，索引== 2
• ch = [1,1,0,1]，索引== 3
• ch = [1,1,0,1]，索引== 4 打印：1101

使用調試器來逐步完成，這可能有助於進一步說明問題