Return 语句有效但没有多大意义

Question

我有以下功能：

int mult(int y, int z)
{
  if (z == 0)
    return 0;
  else if (z % 2 == 1)
    return mult(2 * y, z / 2) + y;
  else 
    return mult(2 * y, z / 2);
}

我需要做的是通过归纳证明其正确性。现在我遇到的麻烦是，尽管我知道它自从运行以来就有效，但我无法遵循每个单独的步骤。

让我困惑的是 y 仅显示为参数，除了递归部分之外，它在任何地方都不会显示在返回中，但该函数实际上返回 y > 作为答案。

这是怎么发生的？我需要能够跟踪发生的一切，以便我可以对其进行迭代以进行证明。

Answer 1

因为这显然是一个家庭作业问题，所以我建议你做这项任务可能意味着你要做的事情。跟踪代码。

1) 给出 y 和 z 的起始值。
2）无论是在纸上还是在调试器中，跟踪调用该函数时发生的情况。
3) 使用当前的 y/z 值重复步骤 2，直到程序完成。

Answer 2

#include <iostream>

using namespace std;

int mult(int y, int z)
{
  if(z==0) {
    cout<<"z is null! - y:"<<y<<" z: "<<z<<endl;
    return 0;
  }
  else if (z%2==1)
  {
    cout<<"z is odd! - y:"<<y<<" z: "<<z<<endl;
    // make z even 
    return mult(2*y,z/2)+y;
  }
  else 
  {
    cout<<"z is even! - y:"<<y<<" z: "<<z<<endl;
    return mult(2*y,z/2);
  }
}


int main()  {

  cout<<"result: "<<mult(3,13)<<endl;

}

输出：

z is odd! - y:3 z: 13
z is even! - y:6 z: 6
z is odd! - y:12 z: 3
z is odd! - y:24 z: 1
z is null! - y:48 z: 0
result: 39

3 和 13 的工作原理：

偶数和奇数有一个开关（请参阅代码中的注释）。

当 z 为 null 时，递归“开始返回到初始调用”。如果数字 z 是奇数，则将 y 添加到递归调用的返回值中，如果数字 z 是偶数，则仅返回递归调用的值。

odd: return 0 + 24
odd: return 24 + 12
even: return 36
odd: return 36 + 3 

Answer 3

逐步分析

final result: 100
 mult(10, 10)
 {
     makes 100
     mult(20, 5)
     {
         makes 100
         mult(40, 2) + 20
         {
              makes 80
             mult(80, 1)
             {
                   makes 80
                  mult(160, 0) + 80
                  {
                        return 0;
                  }
             }
         }
     }
 }

Answer 4

注意：如果这是家庭作业，请如此标记。

所以，我们基本上得到了三种递归情况。为了使一切更清楚，我将 C 代码重写为一些功能性伪代码。将 mult 替换为直观的运算符号，并找出低级表达式（如 (z%2==1)）的描述性解释。

你会想出类似这样的话：

a ** b = 
| b is 0    -> 0 
| b is even -> 2a ** (b/2) 
| b is odd  -> 2a ** (b/2) + a 

你现在明白了吗？

Answer 5

一种方法是将每一行翻译成“英语”。我的翻译是这样的：

如果 z 为零，则返回零
如果 z 为奇数，则返回 mult(y*2, z/2) + y
如果 z 为偶数，则返回 mult(y*2, z/2)

一般模式是递归调用 mult，第一个参数加倍，第二个参数减半。

请注意，这里您使用 z/2 调用 mult，但它的参数是整数，因此如果您的函数继续递归，第二个参数将每次减半，直到它降至 1，最后是 1/2，向下舍入到 0 - 此时递归将停止，因为 z==0。

有了这些线索，您应该能够理解该算法是如何工作的。

Answer 6

归纳论证的基础是证明结果对于第一个值是有效的，并且如果该原理对于泛型值 N 是正确的，则可以证明它对于 N+1 成立。

为了简化，您可以首先证明它适用于 { 0, 1, 2 } 中的 z，这对于手动测试来说应该是微不足道的。然后，为了演示归纳步骤，您从通用 z=N 开始，并证明如果 mult( y, N ) 是有效结果，则 mult ( y, N+1 ) 就前一个结果而言也是有效的结果。由于偶数和奇数有不同的分支，因此您必须证明偶数和奇数 N 的归纳步骤。

Answer 7

ya = ya

a = 偶数

b = 下一个奇数（换句话说 a + 1）

因此，如果您只想用偶数（一个 'a' ) 当给定一个奇数 (a 'b') 时，您可以执行以下操作：

yb = y(a+1) = y*a + y

现在将 'a' 写为 2 会让大家感到困惑*(z/2)。

y*a 变为 (2*y)*(z/2)

y*b 变为 ((2*y)*(z/2))+y

由于 'z' 出现在偶数和奇数的公式中，因此我们想认为代码告诉我们 (2*y)*(z/2) = (2*y)*(z/2) + y 这显然是疯狂的！

原因是我们忽略了 z/2 是整数这一事实，因此 z 永远不可能是奇数。当 z 为奇数时，编译器不会让我们将 z/2 分配给整数。如果我们尝试使“z”为奇数，那么我们真正使用的整数是 (z-1)/2 而不是 z/2。

为了解决这个问题，我们必须测试 z/2 是否为奇数，并据此选择我们的公式（例如，以“a”表示的 ya 或 yb）。

在 mult(y,z) 中，“y”和“z”都是整数。使用上面的符号 mult(2*y,b/2) 会变成 mult(2*y,a/2)，因为 b/2 会被编译器截断为 a/2。

由于我们总是要获取“a”作为“mult”的参数，即使我们发送“b”，我们也必须确保只使用需要“a”的公式。因此，如上所述，我们使用 ya+1 代替 yb。

b/2 = a/2 + 1/2 但 1/2 不能表示为 int 的一部分。

Answer 8

并不是真正的答案，而是更多的建议。
您可能希望将递归调用从 2 次减少到 1 次：

int mult(int y, int z)
{
  int result = 0;  
  if (z == 0)
    return result;
  result = mult(2 * y, z / 2);  // Common between "then" and "else"
  if ((z % 2) == 1)
  {
     result += y;
  }
  return result;
}

这可以通过遵守“仅一个退出点”规则来再次简化：

int mult(int y, int z)
{
  int result = 0;  
  if (z != 0)
  {
    result = mult(2 * y, z / 2);  // Common between "then" and "else"
    if ((z % 2) == 1)
    {
       result += y;
    }
  }
  return result;
}

虽然许多编译器会自动执行此简化，但当代码被简化时，调试通常会更容易。调试器将在单步执行时匹配代码。

有时简化会增加清晰度。此外，添加注释将帮助您了解您在做什么以及下一个阅读代码的人。