找出所有加起来为 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 = 1

• 2 = 2

• 3 = 2

• 4 = 3

• 5 = 3

• 6 = 4

• 7 = 4

• 8 = 5

O(1)您可以在时间和O(1)空间上解决这个问题，如下所示 -

public static int Combos(int n){
    return n / 2 + 1;
    }

注意＃1：如果您还需要值，那么将需要更多的努力，但是对于您的代码，您似乎只想找到不。的方式。

注意＃2：如果您注意到，找到实际值也不会花费太多精力。您根本不需要记住以前的结果。

Answer 2

优化的排列数：

static void Main(string[] args)

{

   var result = Combos(1200);

}

static Dictionary<long, long> cache = new Dictionary<long, long>();

public static long Combos(long n)

{           

   if (n < 3)

   {

      return n;

   }

   else

   {

      if (!cache.TryGetValue(n - 1, out long combos1))

      {

          combos1 = Combos(n - 1);

          cache.Add(n - 1, combos1);

      }

      if (!cache.TryGetValue(n - 2, out long combos2))

      {

          combos2 = Combos(n - 2);

          cache.Add(n - 2, combos2);

      }

      return combos1 + combos2;

   }

}

如果您需要组合，那么您需要提出单独的问题来优化以下代码（来自以下来源）：

static void Main(string[] args)

        {

            FindCombinations(20);

            Console.ReadKey();

        }

        //IEnumerable<IEnumerable<int>>

        static void FindCombinationsUtil(int[] arr, int index,

                                 int num, int reducedNum)

        {

            // Base condition 

            if (reducedNum < 0)

                return;

            // If combination is  

            // found, print it 

            if (reducedNum == 0)

            {

                for (int i = 0; i < index; i++)

                    Console.Write(arr[i] + " ");

                Console.WriteLine();

                return;

                //yield return arr;                                

            }

            // Find the previous number  

            // stored in arr[]. It helps  

            // in maintaining increasing  

            // order 

            int prev = (index == 0) ?

                                  1 : arr[index - 1];

            // note loop starts from  

            // previous number i.e. at 

            // array location index - 1 

            for (int k = prev; k <= num; k++)

            {

                // next element of 

                // array is k 

                arr[index] = k;

                // call recursively with 

                // reduced number 

                FindCombinationsUtil(arr, index + 1, num,

                                         reducedNum - k);

            }

        }

        /* Function to find out all  

        combinations of positive  

        numbers that add upto given 

        number. It uses findCombinationsUtil() */

        static void FindCombinations(int n)

        {

            // array to store the combinations 

            // It can contain max n elements 

            int[] array = new int[n];

            // find all combinations 

            FindCombinationsUtil(array, 0, 2, n);            

        }  

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)

{

    if (n < 3)

        return n;

    int previous = 2;

    int previous2 = 1;

    for (int i = 3; i <= n; i++)

    {

        int newValue = previous + previous2;

        previous2 = previous;

        previous = newValue;

    }

    return previous;

}