你的位置:首页 > ASP.net教程

[ASP.net教程]记一道笔试题


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