代码之家 › 专栏 › 技术社区 › bitshift

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

algorithm c#

bitshift · 技术社区 · 8 年前

假设我有这样一个函数。我需要知道1和2加起来等于N的所有组合。有没有更好的方法来写这篇文章,可以更好地处理N=1200或12000这样的大整数?

public static int Combos(int n)
{
    if (n < 3)
    {
        return n;
    }
    else
    {
        return Combos(n - 1) + Combos(n - 2);
    }
}

3 回复 | 直到 8 年前

Access Denied 8 年前

优化的排列数:

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;
   }
}

source ):

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);            
        }

nice_dev 8 年前

所以,你需要 combinations 和 不是排列

让我们看一些例子-

1 = {1}
2 = {1,1}, {2}
5 = {1,1,1,1,1}, {1,2,1,1}, {2,2,1}
7 = {1,1,1,1,1,1,1}, { 1,2,1,1,1,1} , {2,2,1,1,1} , {2,2,2,1}

如果你观察,它看起来像这样-

3 = 2
4 = 3
5 = 3
7 = 4

O(1) 时间和像下面这样的空间-

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

注1: 如果您还需要值,那么就需要付出更多的努力,但是对于您的代码来说,似乎您只想找到一些方法。

注2: 如果你注意到的话,找到实际值也不会花费太多精力。你根本不需要记住以前的结果。

Cameron Aavik 8 年前

> 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;
}