1

我在理解递归方面遇到了麻烦，我无法解决以下问题。

输入：一个对象（fe 字段）和整数 n

所需输出：具有 n 个字段的列表

我写了一个方法，将一个简单的对象分成两部分，效果很好。但我无法处理递归。

createFields(field, 5) 的最小示例：

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

你能帮我解决这个问题吗？

谢谢！

4

3 回答 3

0

算法的高级描述是：

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将输入精确地分成两半，该算法始终满足前提条件。

该算法使用递归呈现，因为这是问题中的标签之一。这使用尾递归，许多编译器/解释器会将其转换为常规循环，作为尾调用优化的特例。

上面的算法使用了贪婪的方法。下面是一种使用分而治之方法的替代算法。

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-14T22:04:40.503 回答
0

您应该能够迭代地使用您当前的功能。您从 1 个字段开始并调用您的函数，它会为您提供 2 个字段的列表。将它们添加到临时列表中。现在只需在这些字段上调用您的拆分函数。一旦用完一定大小的字段，您就可以从拆分较小的字段开始。

下面的代码应该为您提供大小为 x 和 x/2 的 n 个字段（存储在fields和中fields2）。

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-14T22:07:59.193 回答
0

根据我的一条评论，这里是一个非递归解决方案的提议（在伪代码中）：

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-14T22:19:55.233 回答