假設(shè)我有這樣的功能。我需要知道將加起來為 N 的 1 和 2 的所有組合。有沒有更好的方法來編寫這個對于 N = 1200 或 12000 等大整數(shù)表現(xiàn)更好的方法？public static int Combos(int n){ if (n < 3) { return n; } else { return Combos(n - 1) + Combos(n - 2); }}
3 回答
白衣染霜花
TA貢獻1796條經(jīng)驗 獲得超10個贊
找出所有加起來為 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：如果您注意到，找到實際值也不會花費太多精力。您根本不需要記住以前的結(jié)果。
30秒到達戰(zhàn)場
TA貢獻1828條經(jīng)驗 獲得超6個贊
優(yōu)化的排列數(shù)：
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;
}
}
如果您需要組合，那么您需要提出單獨的問題來優(yōu)化以下代碼（來自以下來源）：
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);
}
有只小跳蛙
TA貢獻1824條經(jīng)驗 獲得超8個贊
示例中的算法計算 1 和 2 的排列數(shù)，而不是組合數(shù)，加起來為 N，所以我會回答一種方法來更快地找到答案。
首先，讓我們嘗試運行它的前幾個數(shù)字
> 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 }
這個數(shù)列其實是一個眾所周知的數(shù)列，就是斐波那契數(shù)列！
您發(fā)布的代碼是計算斐波那契數(shù)的樸素遞歸實現(xiàn)的典型示例，并且是在教授動態(tài)編程時經(jīng)常使用的示例。
網(wǎng)上有很多關(guān)于如何實現(xiàn)更快方法的資源，但其中一種方法是自下而上而不是自上而下地構(gòu)建價值，如下所示：
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;
}
- 3 回答
- 0 關(guān)注
- 255 瀏覽
添加回答
舉報
0/150
提交
取消