遞歸方分區

我有理解遞歸麻煩，我無法解決以下問題。遞歸方分區

輸入：一個對象（FE場）和整數n

所需的輸出：與n場

我寫了一個方法，它把一個簡單的對象分成兩個部分，它工作列表精細。但我無法處理遞歸。

爲createFields

小例子（場，5）：

Input: 
********************************** 
*        * 
*        * 
*        * 
********************************** 
1st iteration (after divide(field)) 
********************************** 
*    *    *     
*    *    * 
*    *    * 
********************************** 
2nd iteration 
********************************** 
*    *    *     
********************************** 
*    *    * 
********************************** 
3rd last iteration 
********************************** 
*  *  *    *     
********************************** 
*    *    * 
**********************************

你能幫我嗎？

謝謝！

來源

2013-03-14 uccie

是否有上的大小的任何限制字段？在我看來，你不想要1分半，1分，1分，8分和2分16秒。 – Origin 2013-03-14 21:54:42

問題不明確。什麼是「字段」？是否只允許在一次操作中將其分成2個相等的部分？ N可以是不同於2的冪的值嗎？ – 2013-03-14 21:55:53

是的。 5是不同於2的冪的值。字段是一組點*。我想要一個大致相等的「字段」。謝謝。 – uccie 2013-03-14 21:58:30

算法高水平的描述是：

divide_recursively (fields, n) 
args: 
    input/output fields : List of fields 
    input n : integer (number of fields) 
precondition: 
    head of list is largest available field 
body: 
    if (fields.size() == n) return 
    f = fields.front() 
    fields.pop_front() 
    fsplit[] = split_field(f) 
    fields.push_back(fsplit[0]) 
    fields.push_back(fsplit[1]) 
    divide_recursively(fields, n)

的前提始終是該算法滿意，只要split_field究竟會把輸入的一半。

的算法使用遞歸提出，因爲這是問題的標籤之一。這使用尾遞歸，許多編譯器/解釋器會將其轉換爲常規循環，作爲tail call優化的特例。

上面的算法使用貪婪的方法。以下是使用分而治之方法的另一種算法。

divide_recursively (fields, n) 
precondition: 
    fields contains exactly one element 
body: 
    if (n == 1) return 
    f = fields.front() 
    fields.pop_front() 
    fpslit[] = split_field(f) 
    subfields1 = new list + fsplit[0] 
    subfields2 = new list + fsplit[1] 
    divide_recursively(subfields1, n/2) 
    divide recursively(subfields2, n - n/2) 
    fields = subfields1 + subfields2

來源

2013-03-14 22:04:40 jxh

不錯！但是，這種尾部遞歸可以很容易地轉換成循環。在這個問題陳述中我沒有看到遞歸的要點。 – 2013-03-14 22:08:46

@EyalScheider你能舉個例子嗎？謝謝！ – uccie 2013-03-14 22:10:26

@EyalSchneider：我同意，但編譯器可以爲你做到這一點。 – jxh 2013-03-14 22:10:58

您應該能夠反覆使用當前函數。你從1字段開始，並調用你的函數，它給你一個2字段的列表。將這些添加到臨時列表中。現在只需在這些字段上調用你的分割函數。一旦你用完了一定大小的字段，你就開始分割更小的字段。

下面的代碼應該給你n個字段（存儲在fields和fields2）大小爲x和x/2。

Field startField=... 
ArrayList<Field> fields=new ArrayList<Field>(); 
ArrayList<Field> fields2=new ArrayList<Field>(); 
fields.add(startField); 
nrFields=1; 
outerlabel: 
while(nrFields<n){ 
    while((!fields.isEmpty()){ 
     Field fieldToSplit = fields.remove(0); 
     List<Field> splitFields=splitt(fieldToSplit); 
     fields2.addAll(splitFields); 
     nrFields++; 
     if(nrFields==n)break outerlabel; 
    } 
    fields=fields2; 
    fields2=new ArrayList<Field>(); 

}

來源

2013-03-14 22:07:59 Origin

繼我的意見之一，這裏是一個非遞歸解決方案的建議（以僞代碼）：

split(field, n) { 
    queue = new Queue() 
    queue.addLast(field) 
    while (queue.size() < n) { 
     f = queue.removeFirst() 
     pair = f.split() 
     queue.addLast(pair.a) 
     queue.addLast(pair.b) 
    } 
    return queue

}

來源

2013-03-14 22:19:55

回答

相關問題