转载

记一道笔试题

题目

4=1 + 1 + 1 + 1

=1 + 1 + 2

=1 + 3

=2 + 2

比如数字 4 可以被拆解成为如上的四种情况。那么现在给你一个vector< vector<int> > 把所有的结果全部的保存到这个 vector< vector<int> > 中。

函数的函数体，应该是这个样子的: vector< vector<int> > & fun(int n){ //函数体 }

分析

从题目的意思是将整数拆分为多个整数的和。有几个注意点：

1. 不做差。也就是不出现 4 = 5 - 1（或 -1 + 5）。

2. 1 为最小可加数。也就是不出现 1 = 1 + 0。

3. 加法交换率。1 + 3 和 3 + 1 是一样的。

4. 结果保存在集合当中。如：[[1,1,1,1],[1,1,2],[1,3],[2,2]]

根据题目可以推断出如下结果：

0 = 0

1 = 1

2 = 1 + 1

3 = 2 + 1

3 = 1 + 1 + 1

4 = 3 + 1

4 = 2 + 2

4 = 2 + 1 + 1

4 = 1 + 1 + 1 + 1

5 = 4 + 1

5 = 3 + 2

5 = 3 + 1 + 1

5 = 2 + 2 + 1

5 = 2 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

......

仔细观察上面过程，对于数字i，红色字体部分就是 i - 1 的结果。所以用递归算法就可以实现。

实现

题目用的是c++，这里用c#实现，也欢迎大家提出更好的方法。效果：

记一道笔试题

源代码

class Program {  static void Main(string[] args)  {   int num = -4;   Console.WriteLine("数字" + num.ToString() + "的结果是：");   List<List<int>> result = BreakNumber(num);   foreach (var numbers in result)   {    for (int i = 0, length = numbers.Count; i < length; i++)    {     Console.Write(numbers[i]);     if (i + 1 < length)     {      if (num > 0)      {       Console.Write("+");      }     }    }    Console.WriteLine();   }  }  static List<List<int>> BreakNumber(int num)  {   if (num == 0 || num == 1 || num == -1)   {    return new List<List<int>>() { new List<int>() { num } };   }   return RecurBreak(num);  }  static List<List<int>> RecurBreak(int num)  {   List<List<int>> result = new List<List<int>>();   if (num == 2)   {    result.Add(new List<int>() { 1, 1 });   }   else if (num == -2)   {    result.Add(new List<int>() { -1, -1 });   }   else   {    double dNum = Convert.ToDouble(num);    dNum = num > 0 ? Math.Ceiling(dNum / 2) : Math.Floor(dNum / 2);    int harfAdd = Convert.ToInt32(dNum);    if (num > 0)    {     while (harfAdd < num)     {      result.Add(new List<int>() { harfAdd, num - harfAdd });      harfAdd++;     }    }    else    {     while (harfAdd > num)     {      result.Add(new List<int>() { harfAdd, num - harfAdd });      harfAdd--;     }    }    int last = num > 0 ? 1 : -1;    List<List<int>> preResult = RecurBreak(harfAdd - last);    foreach (var pr in preResult)    {     pr.Add(last);    }    result.AddRange(preResult);   }   return result;  } }

正文到此结束