c# - C#如何打印加到给定数字的组合?
问题描述
我正在尝试使用动态编程用 C# 实现“将 N 表示为其他数字的总和的不同方式的计数”问题。我的方法看起来像:
static int howManyWays(int n)
{
int [] safe= new int[n + 1];
// base cases
safe[0] = safe[1] = safe[2] = 1;
safe[3] = 2;
// iterate for all values from 4 to n
for (int i = 4; i <= n; i++)
safe[i] = safe[i - 1] + safe[i - 3]
+ safe[i - 4];
return safe[n];
}
例如,如果我选择n
as n = 4
,那么我的结果是:
4
我想打印出这 4 种总和组合:
1+1+1+1
1+3
3+1
4
有没有办法递归或使用动态编程来做到这一点?我的尝试是递归地获得一组组合:
static int[] Combs(int n)
{
int[] tusc = { };
if (n < 0)
yield break;
if (n == 0)
yield return tusc;
int[] X = { 1, 3, 4 };
for(int i = 0; i < X.Length; i++)
{
for(j = 0; j <= Combs(n-X[i]).Length; j++)
{
yield return X + j;
}
}
}
在python中工作的原始代码,但不知道如何翻译成C#:
def combis(n):
if n < 0:
return
if n == 0:
yield []
for x in (1, 3, 4):
for combi in combis(n-x):
yield [x] + combi
>>> list(combis(5))
[[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [1, 4], [3, 1, 1], [4, 1]]
解决方案
这是一个非常直接的翻译:
using System;
using System.Collections.Generic;
class MainClass
{
static IEnumerable<List<int>> Combs(int n)
{
if (n < 0)
{
yield break;
}
else if (n == 0)
{
yield return new List<int>();
}
foreach (int x in new List<int>() {1, 3, 4})
{
foreach (IEnumerable<int> combi in Combs(n - x))
{
var result = new List<int>() {x};
result.AddRange(combi);
yield return result;
}
}
}
public static void Main(string[] args)
{
foreach (IEnumerable<int> nums in Combs(5))
{
foreach (var i in nums)
{
Console.Write(i + ", ");
}
Console.WriteLine();
}
}
}
输出:
1, 1, 1, 1, 1,
1, 1, 3,
1, 3, 1,
1, 4,
3, 1, 1,
4, 1,
评论:
- 由于您使用的是
yield
,因此请将标头更改Combs
为返回IEnumerable<int>
而不是int[]
。 - 使用列表而不是固定长度的数组,并从 Python
List.AddRange
转换列表连接操作。+
- 翻译有些混乱
X
。在 Python 版本中,x
它只是选项列表中的一个元素,{1, 3, 4}
但在 C# 版本中,它是整个数组。 Combs(n-X[i]).Length
没有意义——它调用Combs
,获取结果的长度,然后丢弃所有结果,所以它就像一个非常昂贵的计数器。j
为您提供一个计数器索引,而不是预期的子Combs
调用中的元素之一。foreach
是 Pythonfor .. in
循环的最准确翻译。- 该
{1, 3, 4}
列表可能应该被制成一个参数,以允许调用者控制其行为。 - 效率很差,因为要重新计算重叠的子问题。改进它作为一个练习(这可能是你的下一步)。
推荐阅读
- matlab - 从类访问工作区变量
- python - Pandas/python 在一列列表中加入/合并两个数据框
- lighthouse - Lighthouse中observedLargestContentfulPaint和largestContentfulPaint有什么区别?
- r - 在 RShiny 中使用 reactiveValues 更新SelectInput
- java - 无法使用 JMOD 打包已签名的 Java 安全提供程序
- java - 使用 NumberFormat 在 java 中打印货币值
- javascript - Firestore:如何遍历一些文档并获取子集合?
- python - Python:从不同的文件中导入实例方法是不是很奇怪?
- c++ - 定义运算符重载时擦除向量的对象元素时出错
- reactjs - 如何在 SCSS 函数中发送和正确使用 HTML 'data-' 数字属性