0

考虑以下整数分区代码：

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) 后会发生什么？

4

1 回答 1

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 = 4and 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)and 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
于 2016-01-17T14:28:13.000 回答