考虑整数分区的以下代码:
int p (int n, int m)
{
if (n == m)
return 1 + p(n, m - 1);
if (m == 0 || n < 0)
return 0;
if (n == 0 || m == 1)
return 1;
return p(n, m - 1) + p(n - m, m);
}
如果我举个例子p(7,3),函数变成p(7,0)和p(4,3)后会发生什么?
如果你有Python,你可以试试这个:
def p(n,m):
if n == m:
return 1 + p(n,m-1)
elif m == 0 or n < 0:
return 0
elif n == 0 or m == 1:
return 1
else:
return p(n,m-1) + p(n-m,m)
def tupleFromString(s):
#converts a string like `(3,7)` to the correspoding int tuple
s = s.strip()
arguments = s[1:len(s)-1].split(',')
return tuple(int(i) for i in arguments)
def toString(t):
#converts an int-tuple to a string, without the spaces
return str(t).replace(' ','')
def expandOnce(s):
s = s.strip()
if s.startswith('p'):
n,m = tupleFromString(s[1:])
if n == m:
return '1 + p' + toString((n,m-1))
elif m == 0 or n < 0:
return '0'
elif n == 0 or m == 1:
return '1'
else:
return 'p' + toString((n,m-1)) + ' + p' + toString((n-m,m))
else:
return s
def expandLine(line):
return ' + '.join(expandOnce(term) for term in line.split('+'))
def expand(s):
firstLine = True
k = len(s)
prefix = s + ' = '
while 'p' in s:
if firstLine:
firstLine = False
else:
prefix = ' '*k + ' = '
s = expandLine(s)
print(prefix + s)
print(prefix + str(sum(int(i) for i in s.split('+'))))
p(m,n)
是函数的直接实现,expand
将步骤显示为字符串:
>>> p(4,3)
4
>>> expand('p(4,3)')
p(4,3) = p(4,2) + p(1,3)
= p(4,1) + p(2,2) + p(1,2) + p(-2,3)
= 1 + 1 + p(2,1) + p(1,1) + p(-1,2) + 0
= 1 + 1 + 1 + 1 + p(1,0) + 0 + 0
= 1 + 1 + 1 + 1 + 0 + 0 + 0
= 4
其逻辑如下。如果您想知道p(4,3)
是什么,请查阅定义。 p(4,3)
具有n = 4
和m = 3
,因此您需要使用定义的最后一个子句。这告诉你
p(4,3) = p(4,3-1) + p(4-3,3)
= p(4,2) + p(1,3)
除非您知道p(4,2)
和p(1,3)
是什么,否则这无济于事,因此您回到定义并找到p(4,2) = p(4,1) + p(2,2)
和p(1,3) = p(1,2) + p(-1,2)
。结合上述内容,您现在知道
p(4,3) = p(4,3-1) + p(4-3,3)
= p(4,2) + p(1,3)
= p(4,1) + p(2,2) + p(1,3) + p(1,2)
在每个阶段,如果有一个看起来像p(m,n)
的术语 - 你回到定义,看看它是什么意思。你最终会遇到诸如p(4,1) = 1
等基本情况。一旦评估了所有p
- 只需添加剩下的内容(只有一堆 1 和 0)。
同样地
p(7,3) = p(7,2) + p(4,3)
= p(7,1) + p(5,2) + p(4,2) + p(1,3)
= 1 + p(5,1) + p(3,2) + p(4,1) + p(2,2) + p(1,2) + p(-2,3)
= 1 + 1 + p(3,1) + p(1,2) + 1 + 1 + p(2,1) + p(1,1) + p(-1,2) + 0
= 1 + 1 + 1 + p(1,1) + p(-1,2) + 1 + 1 + 1 + 1 + p(1,0) + 0 + 0
= 1 + 1 + 1 + 1 + p(1,0) + 0 + 1 + 1 + 1 + 1 + 0 + 0 + 0
= 1 + 1 + 1 + 1 + 0 + 0 + 1 + 1 + 1 + 1 + 0 + 0 + 0
= 8