1. 首页
  2. 问题列表
  3. 我怎样才能做一个递归函数，它只使用加法和两个变量进行除法
提问者：小点点

我怎样才能做一个递归函数，它只使用加法和两个变量进行除法


我最近在学校做了一个递归函数，它只使用加法（不允许减法）进行除法，而且只有2个变量。

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

  • n1除以n2。(N1:N2)
  • 答案应该是一个整数(int)，即在n1中可以容纳n2多少次（8:3应该是2，8:4也应该是2）。

我尝试用如下所示的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;
    }

如果有人知道我如何让它工作，我很乐意听到！提前谢谢！


共1个答案

匿名用户

下面是一种我希望代码使之不言而喻的方式。因为我假设我们不允许乘法，所以我在返回值中使用了第二个参数。如果允许我们进行乘法运算，我们可以用一个使用_n的表达式替换_n。

null

// Returns [floor(n / m) * m, floor(n / m)]
function f(n, m){
  if (n < m)
    return [0, 0];
  if (n == m)
    return [n, 1];
  
  const [_n, k] = f(n, m + m);

  if (_n + m > n)
    return [_n, k + k];
    
  return [_n + m, k + k + 1];
}

for (let n=1; n < 200; n++){
  for (let m=1; m<n; m++){
    const _f = f(n, m)[1];
    if (_f != ~~(n / m))
      console.log('Mismatch: ' + n + ', ' + m);
  }
}

console.log('Test done.');

相关问题