打印使用遞歸

號的所有序列所以我有這樣的任務在我的計算機算法類：寫遞歸算法，給定一個正整數n> = 1，打印數字的所有序列 K> = 1和1 < = i1 < i2 < ... < ik < = n。例如：如果n = 3，則輸出將是打印使用遞歸

1,2-

1,2,3

1,3-

2,3

我正在嘗試在Java中爲此任務編寫遞歸代碼，但我不知道如何解決此問題。我理解遞歸的基礎知識，但我自己寫遞歸代碼時遇到困難。

這就是我現在所擁有的：

public class question4 
{ 
    public static void main(String arg[]){ 
     int x = 10; 
     printSequence(x); 
    } 
    public static int printSequence(int n){ 
     if (n == 1){ 
      System.out.println(n); 
      return n; 
     } 
     else{ 
      int result = printSequence(n-1) + 1; 
      System.out.println(result); 
      return result; 
     } 
    } 

}

它只打印1,2,3,4,5,6,7,8,9,10

請幫幫我！

預先感謝您！

來源

2014-09-29 user2826974

請向我們展示您到目前爲止獲得的代碼。 – NPE 2014-09-29 19:08:34

我認爲你的老師/教授/助教將是一個更好的人去幫助這個 – ControlAltDel 2014-09-29 19:09:34

附註，良好做法：類名稱應該是CamelCase。 – Demplo 2014-09-29 20:19:36

從最右邊的元素開始，繼續向左，直到達到1（遞歸的基本情況）。在基本情況下，返回「1」。現在開始自下而上構建組合。函數foo返回字符串的數組列表。遞歸中的每個級別都有三個部分。 Part1是先前調用foo返回的數組列表; part2，將n附加到之前調用foo返回的所有元素;最後在part3，將n附加到數組列表中。

import java.util.*; 
class Sequence 
{ 
    public static ArrayList<String> foo(int n) 
    { 
     if(n==1) 
     { 
      ArrayList<String> a = new ArrayList<String>(); 
      a.add("1"); 
      return a; 
     } 
     ArrayList<String> withOutN = foo(n-1); 
     ArrayList<String> out = new ArrayList<String>(); 

     Iterator<String> it = withOutN.iterator(); 
     Integer i = new Integer(n); 
     while(it.hasNext()) 
     { 
      String s = it.next(); 
      out.add(s); 
      s = s.concat("," + i.toString()); 
      out.add(s); 
     } 
     out.add(i.toString()); 
     return out; 
    } 

    public static void main(String[] args) 
    { 
     int n=4; 
     ArrayList<String> out = new ArrayList<String>(); 

     out = (ArrayList<String>) foo(n); 

     Iterator<String> it = out.iterator(); 
     while(it.hasNext()) 
     { 
      System.out.println((it.next())); 
     } 
    } 
}

來源

2014-09-29 21:56:21 arunmoezhi

基本上，有n = 5爲例，你應該打印兩種間隔

1   | full interval 
1 2  | 
1 2 3  | 
1 2 3 4 | 
1 2 3 4 5 | 

1 _ 3 4 5 | concatenation of full interval (1 -> i) with (i+1 -> n) 
1 2 _ 4 5 | 
1 2 3 _ 5 | 

1 _ _ 4 5 | concatenation of full interval (1 -> i) with (i+2 -> n) 
1 2 _ _ 5 | 

1 _ _ _ 5 | concatenation of full interval (1 -> i) with (i+3 -> n) 
--------------------- 
    2  | full interval 
    2 3  | 
    2 3 4 | 
    2 3 4 5 | 

    2 _ 4 5 | concatenation of full interval (1 -> i) with (i+1 -> n) 
    2 3 _ 5 | 

    2 _ _ 5 | concatenation of full interval (1 -> i) with (i+2 -> n) 
--------------------- 
    3  | full interval 
    3 4 | 
    3 4 5 | 

    3 _ 5 | concatenation of full interval (1 -> i) with (i+1 -> n) 
--------------------- 
     4 | full interval 
     4 5 | 

     5 | concatenation of full interval (breaks here)

然後，你必須做的是：

1打印全間隔from = 1和to = n
2 - 迭代連接兩個帶「負」部分的區間
3-再次調用傳遞的遞歸方法(from++, to)

希望它可以幫助

來源

2014-09-29 20:40:12 elias

有幾種情況正在被遺漏，即我所知道的1,2,4,5。這就是事情變得混亂的地方。 – Compass 2014-09-29 20:44:41

謝謝！這是一個好開始！ – user2826974 2014-09-29 20:47:31

@Compass你是對的！間隔中忽略的數字大小也需要考慮。固定！ – elias 2014-09-29 21:28:17

從一組{a, b, c, ...}，你想{a}和{}加入了與設定的，所有的子集的{b, c, ...}遞歸。

來源

2014-09-29 20:52:21 MattPutnam

打印使用遞歸

回答

相關問題