c# - 如何创建一个仅使用加法和 2 个变量进行除法的递归函数

Question

我最近接到一份学校作业，要求制作一个递归函数，该函数仅使用加法(不允许减法)进行除法，并且只有 2 个变量。

编辑:基于评论的一些注释:

• n1 除以 n2。 (n1:n2)

• 答案应该是 n2 可以放入 n1 的次数的整数 (int)(8:3 应该得到 2，8:4 也应该得到 2)。

• 您可以假设输入仅为正整数。

按照评论中的要求，我会尽力将作业翻译成英文并尽可能准确:

Write a recursive function named "PDiv" that gets two whole positive numbers and returns their whole quotient, using addition operations only.

我尝试使用 2 个递归函数来实现，如下所示:(赋值只需要一个函数，因此这不是正确的答案)

public static int PDiv(int n1, int n2)
{
    if (n1 < n2)
        return 0;
    else if (n1 == n2)
        return 1;
    else
        return PDiv(n1, n2 + n2, n2) + 1;
}

public static int PDiv(int n1, int n2, int con)
{
    if (n1 < n2)
        return 0;
    else if (n1 == n2)
        return 1;
    else
        return PDiv(n1, n2 + n2, con) + 1;
}

除此之外，我还尝试过那个确实有效的方法，但它假装很聪明，但实际上并没有用加法来实现，而是加上了减号(基本上是减法)。示例:

public static int PDiv(int n1, int n2)
{
    if (n1 < n2)
        return 0;
    else if (n1 == n2)
        return 1;
    else
        return PDiv(n1 + -n2, n2) + 1;
}

如果有人知道我如何让它发挥作用，我很想听听!提前致谢!

Answer 1

这是我们实现这一目标的一种方法，前提是我们可以使用模运算符和局部变量。

这个想法是，如果我们知道 PDiv(n, m + m)，我们只需要知道是否还能再添加一个 m 即可。

C# 代码:

using System;

public class Test
{
    public static int PDiv(int n, int m)
    {
        if (n < m)
            return 0;
        if (n == m)
            return 1;
  
        int k = PDiv(n, m + m);

        return k + k + (n % (m + m) < m ? 0 : 1);
    }

    public static void Main()
    {
        Console.WriteLine(PDiv(21, 3));
    }
}