递归求正方形的面积
find area of a square recursively
我有一个大正方形,它是由固定大小的小square-tiles组成的。
这些小square-tiles的面积是已知的。
其中一个图块显示在左上角。
现在,
每个方格可以分解成4个子方格。每个方块都有一个标识方块的键。
big-square 中可能有很多空方块。在这些情况下,密钥不存在,该区域被视为零。
最小的图块的密钥长度为 3。
我想递归地找到给定一个键的任何正方形的面积。
这就是我正在尝试的。但它没有给我正确的解决方案。
findAreaRecursive(self, key, maxDepth=3):
if len(Key) == maxDepth:
if self.keyExists(key):
return self.getAreaValue(key)
else:
return 0
else:
keyChild0 = key + '0'
keyChild1 = key + '1'
keyChild2 = key + '2'
keyChild3 = key + '3'
if self.keyExists(keyChild0):
areaChild0 = self.findAreaRecursive(keyChild0, maxDepth)
else:
areaChild0 = 0
if self.keyExists(keyChild1):
areaChild1 = self.findAreaRecursive(keyChild1, maxDepth)
else:
areaChild1 = 0
if self.keyExists(keyChild2):
areaChild2 = self.findAreaRecursive(keyChild2, maxDepth)
else:
areaChild2 = 0
if self.keyExists(keyChild3):
areaChild3 = self.findAreaRecursive(keyChild3, maxDepth)
else:
areaChild3 = 0
return areaChild0 + areaChild1 + areaChild2 + areaChild3
我做错了什么。我是递归的新手。欢迎任何帮助。
在我看来,您的递归查找器有点过于复杂。你有点像在函数中展开递归。下面是一个可能 'purely' 递归的例子。如果我假设 keyExists() 通过在键有区域值时返回 true 来工作,它就会工作。
def findAreaRecursive(self, key, maxDepth=3):
totArea = 0
if len(key) == maxDepth:
if self.keyExists(key):
totArea += self.getAreaValue(key)
else:
for i in range(4):
newKey = key + str(i)
totArea += findAreaRecursive(self, newKey, maxDepth)
return totArea
然而……
递归可能很难理解。如果您想继续采用您的方法,可以通过
帮助澄清您的问题
放入整个代码 - 包括 getAreaValue() 和 keyExists() 函数,我们可以查看它以找出执行路径和失败的地方。例如,您我们看不到您的 keyExists() 函数的逻辑,也许这有时会给出错误的值,导致您的代码的一个分支在您不期望的时候返回零。
在递归中放入一些打印语句(好的,因为在您的情况下递归不是太深)。你会看到发生了什么。我将从打印语句开始作为函数中的第一个语句
print "Called with key",key
这将允许您跟踪正在调用哪些键,并且您可以检查它是否按照您期望的顺序发生。
编辑:
另请参阅 this answer 一个类似的问题,该问题首先很好地总结了一种思考递归的方法,因为您说您是递归的新手。
我有一个大正方形,它是由固定大小的小square-tiles组成的。
这些小square-tiles的面积是已知的。
其中一个图块显示在左上角。
现在,
每个方格可以分解成4个子方格。每个方块都有一个标识方块的键。
big-square 中可能有很多空方块。在这些情况下,密钥不存在,该区域被视为零。
最小的图块的密钥长度为 3。
我想递归地找到给定一个键的任何正方形的面积。
这就是我正在尝试的。但它没有给我正确的解决方案。
findAreaRecursive(self, key, maxDepth=3):
if len(Key) == maxDepth:
if self.keyExists(key):
return self.getAreaValue(key)
else:
return 0
else:
keyChild0 = key + '0'
keyChild1 = key + '1'
keyChild2 = key + '2'
keyChild3 = key + '3'
if self.keyExists(keyChild0):
areaChild0 = self.findAreaRecursive(keyChild0, maxDepth)
else:
areaChild0 = 0
if self.keyExists(keyChild1):
areaChild1 = self.findAreaRecursive(keyChild1, maxDepth)
else:
areaChild1 = 0
if self.keyExists(keyChild2):
areaChild2 = self.findAreaRecursive(keyChild2, maxDepth)
else:
areaChild2 = 0
if self.keyExists(keyChild3):
areaChild3 = self.findAreaRecursive(keyChild3, maxDepth)
else:
areaChild3 = 0
return areaChild0 + areaChild1 + areaChild2 + areaChild3
我做错了什么。我是递归的新手。欢迎任何帮助。
在我看来,您的递归查找器有点过于复杂。你有点像在函数中展开递归。下面是一个可能 'purely' 递归的例子。如果我假设 keyExists() 通过在键有区域值时返回 true 来工作,它就会工作。
def findAreaRecursive(self, key, maxDepth=3):
totArea = 0
if len(key) == maxDepth:
if self.keyExists(key):
totArea += self.getAreaValue(key)
else:
for i in range(4):
newKey = key + str(i)
totArea += findAreaRecursive(self, newKey, maxDepth)
return totArea
然而……
递归可能很难理解。如果您想继续采用您的方法,可以通过
帮助澄清您的问题放入整个代码 - 包括 getAreaValue() 和 keyExists() 函数,我们可以查看它以找出执行路径和失败的地方。例如,您我们看不到您的 keyExists() 函数的逻辑,也许这有时会给出错误的值,导致您的代码的一个分支在您不期望的时候返回零。
在递归中放入一些打印语句(好的,因为在您的情况下递归不是太深)。你会看到发生了什么。我将从打印语句开始作为函数中的第一个语句
print "Called with key",key
这将允许您跟踪正在调用哪些键,并且您可以检查它是否按照您期望的顺序发生。
编辑:
另请参阅 this answer 一个类似的问题,该问题首先很好地总结了一种思考递归的方法,因为您说您是递归的新手。