找出所有加起来为 N 的 1 和 2 的组合

Question

假设我有这样的功能。我需要知道将加起来为 N 的 1 和 2 的所有组合。有没有更好的方法来编写这个对于 N = 1200 或 12000 等大整数表现更好的方法？

public static int Combos(int n)

{

    if (n < 3)

    {

        return n;

    }

    else

    {

        return Combos(n - 1) + Combos(n - 2);

    }

}

Answer 1

找出所有加起来为 N 的 1 和 2 的组合所以，你需要combinations而不是 permutations。让我们看一些例子——1 = {1}2 = {1,1}, {2}3 = {1,1,1}, {1,2} （或 {2,1} ，两者相同）。4 = {1,1,1,1}, {1,2,1}, {2,2}5 = {1,1,1,1,1}, {1,2,1,1}, {2,2,1}6 = {1,1,1,1,1,1}, { 1,2,1,1,1} , {2,2,1,1} , {2,2,2}7 = {1,1,1,1,1,1,1}, { 1,2,1,1,1,1} , {2,2,1,1,1} , {2,2,2,1}如果你观察，它看起来像这样——1 = 12 = 23 = 24 = 35 = 36 = 47 = 48 = 5O(1)您可以在时间和O(1)空间上解决这个问题，如下所示 -public&nbsp;static&nbsp;int&nbsp;Combos(int&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;n&nbsp;/&nbsp;2&nbsp;+&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;}注意＃1：如果您还需要值，那么将需要更多的努力，但是对于您的代码，您似乎只想找到不。的方式。注意＃2：如果您注意到，找到实际值也不会花费太多精力。您根本不需要记住以前的结果。

Answer 2

优化的排列数：static void Main(string[] args){&nbsp; &nbsp;var result = Combos(1200);}static Dictionary<long, long> cache = new Dictionary<long, long>();public static long Combos(long n){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp;if (n < 3)&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; return n;&nbsp; &nbsp;}&nbsp; &nbsp;else&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; if (!cache.TryGetValue(n - 1, out long combos1))&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combos1 = Combos(n - 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cache.Add(n - 1, combos1);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; if (!cache.TryGetValue(n - 2, out long combos2))&nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; combos2 = Combos(n - 2);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cache.Add(n - 2, combos2);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; return combos1 + combos2;&nbsp; &nbsp;}}如果您需要组合，那么您需要提出单独的问题来优化以下代码（来自以下来源）：static void Main(string[] args)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; FindCombinations(20);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Console.ReadKey();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; //IEnumerable<IEnumerable<int>>&nbsp; &nbsp; &nbsp; &nbsp; static void FindCombinationsUtil(int[] arr, int index,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;int num, int reducedNum)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Base condition&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (reducedNum < 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // If combination is&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // found, print it&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (reducedNum == 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < index; i++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Console.Write(arr[i] + " ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Console.WriteLine();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //yield return arr;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Find the previous number&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // stored in arr[]. It helps&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // in maintaining increasing&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // order&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int prev = (index == 0) ?&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1 : arr[index - 1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // note loop starts from&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // previous number i.e. at&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // array location index - 1&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int k = prev; k <= num; k++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // next element of&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // array is k&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[index] = k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // call recursively with&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // reduced number&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; FindCombinationsUtil(arr, index + 1, num,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;reducedNum - k);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; /* Function to find out all&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; combinations of positive&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; numbers that add upto given&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; number. It uses findCombinationsUtil() */&nbsp; &nbsp; &nbsp; &nbsp; static void FindCombinations(int n)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // array to store the combinations&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // It can contain max n elements&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] array = new int[n];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // find all combinations&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; FindCombinationsUtil(array, 0, 2, n);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp;

Answer 3

示例中的算法计算 1 和 2 的排列数，而不是组合数，加起来为 N，所以我会回答一种方法来更快地找到答案。首先，让我们尝试运行它的前几个数字> Enumerable.Range(1, 20).Select(Combos).ToList()List<int>(20) { 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946 }这个数列其实是一个众所周知的数列，就是斐波那契数列！您发布的代码是计算斐波那契数的朴素递归实现的典型示例，并且是在教授动态编程时经常使用的示例。网上有很多关于如何实现更快方法的资源，但其中一种方法是自下而上而不是自上而下地构建价值，如下所示：int Combos(int n){&nbsp; &nbsp; if (n < 3)&nbsp; &nbsp; &nbsp; &nbsp; return n;&nbsp; &nbsp; int previous = 2;&nbsp; &nbsp; int previous2 = 1;&nbsp; &nbsp; for (int i = 3; i <= n; i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int newValue = previous + previous2;&nbsp; &nbsp; &nbsp; &nbsp; previous2 = previous;&nbsp; &nbsp; &nbsp; &nbsp; previous = newValue;&nbsp; &nbsp; }&nbsp; &nbsp; return previous;}