題目
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#實作,也歡迎大家提出更好的方法。效果:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iNxkjM5MTM1AjMtgDMzMDN3EDNxAzM5ATNxAjMtADM4gTO38CX5ATNxAjMvwFMwgDO5czLcd2bsJ2Lc12bj5ycn9Gbi52YuUTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
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;
}
}