我在理解递归方面遇到了麻烦,我无法解决以下问题。
输入:一个对象(例如字段)和整数 n
期望的输出:包含 n 个字段的列表
我写了一个方法,将一个简单的对象分成两部分,而且效果很好。但是我无法处理递归。
createFields(field, 5) 的最小示例:
Input:
**********************************
* *
* *
* *
**********************************
1st iteration (after divide(field))
**********************************
* * *
* * *
* * *
**********************************
2nd iteration
**********************************
* * *
**********************************
* * *
**********************************
3rd last iteration
**********************************
* * * *
**********************************
* * *
**********************************
你能帮我解决这个问题吗?
谢谢!
最佳答案
算法的高级描述是:
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
关于java - 递归平方分割,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15420815/