递归方分区

我有理解递归麻烦，我无法解决以下问题。递归方分区

输入：一个对象（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

回答

相关问题