使用2個數字求和的方法數量

我需要使用數字1和2來查找求和（例如1000000）的數量。順序很重要。我做了使用組合的解決方案：使用2個數字求和的方法數量

enter image description here

哪裏n是的總和。

實施例：

n=7對於有21方式。

1111111，111112，111121，111211，112111，121111，211111，11122 .... 1222，2122，2212，2221

的數量可能非常大，我必須找到它的一些模大素數。（是的，它是在線編碼競賽的一個小問題）。我需要一個更加電腦友好的配方..任何幫助嗎？或者，也許可以通過創建一個循環和矩陣求冪來完成？

來源

2013-02-03 Bruce

如果這是一個在線編碼競賽，如何讓別人來解決這個問題將展示您的編碼能力？對不起，這裏沒有幫助。 – Mogsdad

這裏有一個提示：要得到'n'的總和，你可以選擇一個'1'並得到'n-1'的總和，或者選擇一個'2'並得到'n-2'的總和。這種遞歸是否會讓你想起任何事情？ – rici

另一個提示：計算'n = 1'到'n = 6'的值。注意任何可疑的東西？ – DSM

這樣做的方式數量等於第n個斐波那契數F（n），容易計算。

歸納證明。假設n爲真。考慮一個長度爲n + 1的序列。這可以通過將總數爲n或2的序列加1來形成，其總數爲n-1。這是獨特的，代表了所有的可能性。

所以F（N + 1）= F（N）+ F（N-1） F（1）= 1

整齊，是嗎？

來源

2013-02-03 05:13:02

這就是我想出了：

def onesAndTwos(num): 
    if num <= 0: 
     return set() 
    elif num == 1: 
     return set([(1, 0)]) 
    elif num == 2: 
     return set([(2,0), (0, 1)]) 
    else: 
     setA = set([(1 + x[0], x[1]) for x in onesAndTwos(num-1)]) 
     setB = set([(x[0], 1 + x[1]) for x in onesAndTwos(num-2)]) 
     setA.update(setB); 
     return setA 

print onesAndTwos(10) 
print len(onesAndTwos(10))

它使用一個元組的第一個元素是一的數量和三三兩兩的第二數目。所以可以用set[(3,0), (1,1)]來產生3的總和。要查找有多少種組合，您可以統計集合中的元組。 10輸出：

set([(8, 1), (6, 2), (0, 5), (4, 3), (10, 0), (2, 4)]) 
6

這是一個有點動態規劃方法，我們有一組重複的子問題和相似的結構貫穿始終，使我們能夠建立在以前的解決方案。這不是最優的，因爲你不會重複使用兩個分支中的先前計算的值（第一次拿走1，第二次拿走2），所以我認爲這是一個天真的解決方案。

來源

2013-02-03 03:25:48

public class Fibonacci { 
    public static int magic(int input) { 
     if (input == 1) { 
      return 1; 
     } else if (input == 2) { 
      return 2; 
     } else { 
      return magic(input-1) + magic(input-2); 
     } 
    } 

    public static void main(String args[]) { 
     int input = 7; 
     int numberOfCombinations = magic(input); 
     System.out.println("The total number of combinations for the given integer "+input+" is "+numberOfCombinations); 
    } 
}

完整且可正常使用的Java代碼。隨意使用它爲您的競爭。我希望代碼能夠說明底層算法。祝你好運！

來源

2013-02-03 05:02:38

您嘗試查找的數字是第n個斐波那契數。最好的方法（因爲你說n可以真的很大）是實現這個遞歸O(log n)公式（這些是2x2矩陣，抱歉的醜陋格式）。

[F(n+2)] = [1 1] [F(k+1)] 
[F(n+1)] [1 0] [F (k) ]

也許明確的形式會更適合你，而不是遞歸一個：

[1 1]^n = [F(k+1) F(k) ] 
[1 0]  [ F(k) F(k-1)]

這是最快的方法知道我計算Fibonacci數。請記住輸出增長非常快，因此您無法緩存大n的結果。

來源

2013-02-03 10:44:09 Denis

使用2個數字求和的方法數量

回答

相關問題