如何证明以下算法的正确性？

Question

我需要证明以下算法正常工作,我知道归纳,但不知道如何在这里使用它？如果知道算法的复杂性,它是多么最优,我会很高兴吗？什么是运行时间？请帮助我

#include <cstdlib>
#include <iostream>
#define c 2
//we should take c   more ot equal  then 2
using namespace std;
int multiply(int y,int z){
      // product yz
    if(z==0) return 0;
    return (multiply(c*y,int(z/c))+y*(z %c));
}

int main(int argc, char *argv[])
{
    int y=5;
    int z=7;
    cout<<multiply(y,z)<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

谢谢

Answer 1

1)对于z=0你的功能显然是正确的

2)假设multiply(x, y)返回x*y对0 <= y < y0.然后

  x*y
= x*((y/c)*c + y%c)    # by the definition of %
= x*c*(y/c) + x*(y%c)  # distributive, commutative laws
= multiply(x*c, y/c) + x*(y%c) # 0 <= y/c < y, induction hypothesis