给定 N，对于从 1 到 N 的连续数字，创建一个递归 C# 方法来打印出所有可能导致 X 的“+”和“-”组合

Question

我正在处理以下作业，由于我对递归不是很熟悉，所以我很茫然。如果有更多经验的人能指出正确的方向，我将不胜感激。

作业内容如下：编写一个控制台应用程序，确定可以放在从 1 到给定 N >=2 的自然数之间的“+”和“-”运算符的所有组合，以便表达式的结果是给定的 X 数。如果没有可能的组合，应用程序将输出 'N/A'.

例如：对于输入：
6 //N
3 //X

控制台将显示：
1 + 2 + 3 - 4 - 5 + 6 = 3
1 + 2 - 3 + 4 + 5 - 6 = 3
1 - 2 - 3 - 4 + 5 + 6 = 3

鉴于作业的情况，我不能使用除 'System' 之外的任何其他指令。我发现了这个 'Coin Change' 问题的几个版本，但主要是在 C++ 或 Python 中，并且与我当前的任务也有很大不同。我不是要任何人帮我做作业，我只是在寻找一些有效的指示，这样我就知道从哪里开始了。

Answer 1

我会创建一个函数（我们称它为 f），它有 5 个参数：当前数字、结束数字 (N)、所需结果 (X)、到目前为止的公式和公式的结果远.

在函数中，您首先测试当前数字是否为结束数字。如果是，则测试公式的结果是否是所需的数字。如果是，打印公式。

如果您还没有结束，请调用函数本身两次。一次添加下一个数字，一次减去它。

函数的第一次调用是 f(1, 6, 3, "1", 1)。然后它会调用自己两次 f(2, 6, 3, "1 + 2", 3) 和 f(2, 6, 3, "1 - 2", -1) 然后它会继续这样，直到它到达公式中有 6 个数字的调用，它会检查结果是否为 3.

希望对您有所帮助。

Answer 2

此代码示例应该对您有所帮助。您可以根据需要调整此递归，因为它只计算此类组合的数量。

考虑到这种方法很慢，您可以找到一些更快的 DP 解决方案。

    private static int Search(int start, int end, int cur, int searched)
    {
        if (start > end)
        {
            return Convert.ToInt32(cur == searched);
        }

        return Search(start + 1, end, cur + start, searched) + Search(start + 1, end, cur - start, searched);
    }

    static void Main(string[] args)
    {
        int result = Search(2, 6, 1, 3);
    }

Answer 3

这个答案力求成为帮助而不是帮助艺术的巅峰之作。
这就是要求的。

所以在这里，完整的解决方案虽然有点模糊，但您可能从未听说过一种语言。但是如果你对你所看到的进行足够长时间的思考，你可能会想到如何在 C# 中解决这个问题。


data Expr = Lit Integer | Add | Sub deriving(Show)

compute :: [Expr] -> Integer -> Integer
compute [] value = value
compute (Add : Lit x : rest) value = compute rest (value + x)
compute (Sub : Lit x : rest) value = compute rest (value - x)
compute (Lit x1 : Add : Lit x2 : rest) value = compute rest (value + x1 + x2)
compute (Lit x1 : Sub : Lit x2 : rest) value = compute rest (value + x1 - x2)
compute [Lit x] _  = x


solve :: Integer -> [Integer] -> [Expr] -> [[Expr]] -> [[Expr]]
solve goal [] current found
    | goal == compute current 0 = current : found
    | otherwise = found
solve goal (n:ns) current found =
    solve goal ns (current ++ [Add, Lit n]) [] 
        ++  solve goal ns (current ++ [Sub, Lit n]) []

prettyFormula :: [Expr] -> String
prettyFormula f =
    concat $ fmap (\xp -> case xp of 
                            Lit n -> show n
                            Add -> "+"
                            Sub -> "-") f

在 REPL 中加载 fmap prettyFormula (solve 3 [2..6] [Lit 1] []) 后，您将得到结果：

["1+2+3-4-5+6","1+2-3+4+5-6","1-2-3-4+5+6"]

给定 N，对于从 1 到 N 的连续数字，创建一个递归 C# 方法来打印出所有可能导致 X 的“+”和“-”组合

Given N, for consecutive numbers from 1 to N create a recursive C# method to print out all possible '+' and '-' combinations that result in X

c#

algorithm

recursion

coin-change