如何找到整数1,2,3可以累加n的方式？ [英] How to find number of ways that the integers 1,2,3 can add up to n?

问题描述

给出一组整数1,2和3，求出它们加起来为n的方式数。 （顺序很重要，即n为5。1 + 2 + 1 + 1和2 + 1 + 1 + 1是两个不同的解决方案）

Given a set of integers 1,2, and 3, find the number of ways that these can add up to n. (The order matters, i.e. say n is 5. 1+2+1+1 and 2+1+1+1 are two distinct solutions)

我的解决方案涉及拆分n变成1的列表，因此如果n = 5，则A = [1,1,1,1,1]。通过添加相邻数字，我将从每个列表中递归地生成更多子列表。因此，A将再生成4个列表：[2,1,1,1]，[1,2,1,1]，[1,1,2,1]，[1,1,1,2]，以及每个这些列表中的所有列表将生成更多子列表，直到达到[3,2]或[2,3]之类的终止情况为止。

My solution involves splitting n into a list of 1s so if n = 5, A = [1,1,1,1,1]. And I will generate more sublists recursively from each list by adding adjacent numbers. So A will generate 4 more lists: [2,1,1,1], [1,2,1,1], [1,1,2,1],[1,1,1,2], and each of these lists will generate further sublists until it reaches a terminating case like [3,2] or [2,3]

这是我建议的解决方案（在Python中）

Here is my proposed solution (in Python)

ways = []
def check_terminating(A,n):
    # check for terminating case
    for i in range(len(A)-1):
        if A[i] + A[i+1] <= 3:
            return False # means still can compute
    return True

def count_ways(n,A=[]):
    if A in ways:
       # check if alr computed if yes then don't compute
       return True
    if A not in ways: # check for duplicates
        ways.append(A) # global ways
    if check_terminating(A,n):
        return True # end of the tree
    for i in range(len(A)-1):
        # for each index i,
        # combine with the next element and form a new list
        total = A[i] + A[i+1]
        print(total)
        if total <= 3:
            # form new list and compute
            newA = A[:i] + [total] + A[i+2:]
            count_ways(A,newA)
            # recursive call

# main            
n = 5
A = [1 for _ in range(n)]

count_ways(5,A)
print("No. of ways for n = {} is {}".format(n,len(ways)))

请问我是否处在正确的轨道上，如果可以，是否有任何方法可以使此代码更高效？

May I know if I'm on the right track, and if so, is there any way to make this code more efficient?

请注意，这不是硬币找零问题。在硬币找零中，出现的顺序并不重要。在我的问题中，1 + 2 + 1 + 1与1 + 1 + 1 + 2不同，但是在硬币找零中，两者相同。请不要发布

Please note that this is not a coin change problem. In coin change, order of occurrence is not important. In my problem, 1+2+1+1 is different from 1+1+1+2 but in coin change, both are same. Please don't post coin change solutions for this answer.

编辑：我的代码正在运行，但是我想知道是否有更好的解决方案。感谢您的所有帮助：）

My code is working but I would like to know if there are better solutions. Thank you for all your help :)

推荐答案

重复关系为F（n + 3）= F（n + 2）+ F（n + 1）+ F（ n），其中F（0）= 1，F（-1）= F（-2）= 0。这些是tribonacci数（斐波那契数的变体）：

The recurrence relation is F(n+3)=F(n+2)+F(n+1)+F(n) with F(0)=1, F(-1)=F(-2)=0. These are the tribonacci numbers (a variant of the Fibonacci numbers):

可以写一个简单的O（n）解决方案：

It's possible to write an easy O(n) solution:

def count_ways(n):
    a, b, c = 1, 0, 0
    for _ in xrange(n):
        a, b, c = a+b+c, a, b
    return a

比较困难，但是可以用较少的算术运算来计算结果：

It's harder, but possible to compute the result in relatively few arithmetic operations:

def count_ways(n):
    A = 3**(n+3)
    P = A**3-A**2-A-1
    return pow(A, n+3, P) % A

for i in xrange(20):
    print i, count_ways(i)

这篇关于如何找到整数1,2,3可以累加n的方式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！