2014-11-24 61 views
2

我想拿出一個遞歸函數,其中輸入一個非負整數n,併產生所有自然數從0到n,然後再降到0的列表如何在一個遞歸函數中向下計數?

例如,如果函數被命名爲

ArrayList<Integer> f(int x) 

;當X = 4它給

{0,1,2,3,4,3,2,1,0}列表contaning


如何實現這一目標?能這可以在一個函數中完成,而不需要輔助函數,如countup和countdown。
邏輯通緝!
幫助讚賞!

+0

假設你有一個函數產生自然數列表,從1到n,然後到1試。你如何使用這個函數來產生一個開始和結束於0的列表? – ajb 2014-11-24 20:04:43

+0

這是功課嗎? – Becojo 2014-11-24 20:05:02

+0

@Becojo不是一個功課人 – Yvainovski 2014-11-24 20:05:53

回答

2

這是我的解決方案:

public ArrayList<Integer> f(int x) { 
    ArrayList<Integer> arr; 
    if (x == 1) { 
     arr = new ArrayList<Integer>(); 
     arr.add(0); 
     arr.add(1); 
     arr.add(0); 

    } else { 
     arr = f(x-1); 
     int pos = (int) (arr.size()/2)+1; 
     arr.add(pos, x); 
     arr.add(pos + 1, x-1); 

    } 
    return arr; 
} 

在該算法中我設置x的基值是1,其產生的數字應該是[0,1,0]。

如果x大於1,則遞歸生成x-1的列表,然後在返回列表的適當位置插入兩個值x和x-1,該列表基本上位於中等價值。

例如

如果x等於2; 獲得值1 - 這將是[0,1,0]
然後在第三位置插入2和1(中間位置後),以獲得[0,1,2,1,0]

如果x等於3; 獲得2的值 - 這將是[0,1,2,1,0]
然後在第四個位置插入3和2以獲得[0,1,2,3,2,1,0]

等...

+0

將分配推送到邊緣案例 – Elazar 2014-11-25 10:02:49

+0

編輯:推送分配arr =新ArrayList ()到邊緣案例。 – 2014-11-28 07:35:18

0

recArray是遞歸函數,以遞歸方式返回爲arraylist。

int x=10; 
List<Integer> result=null; 
result=recArray(x,result); 

如果您遍歷結果數組列表,它會具有數字如你所說

public List<Integer> recArray(Integer x, List<Integer> result) { 
    if (result == null) { 
     result = new ArrayList<Integer>(); 
     for (int i = 0; i < 2 * x + 1; i++) { 
      result.add(0); 
     } 
     result.set(x, x); 
    } 
    int pos = result.size()/2; 

    result.set(pos - x, pos - x); 
    result.set(pos + x, pos - x); 
    if (x == 0) { 
     return result; 
    } 

    return recArray(x - 1, result); 

} 

感謝, Arumugarani

0

你可以做這樣的事情:

ArrayList<Integer> f(int x) { 
    if (x==0) { 
     ArrayList<Integer> res = new ArrayList<>(); 
     res.add(0); 
     return res; 
    } 
    ArrayList<Integer> t = f(x-1); 
    t.add(t.size()/2, x-1); 
    t.add(t.size()/2, x);  
    return t; 
}