c - 两个数字之间的乘法

Question

我有一个任务来构建一个将 2 个整数相乘且不使用 * 或“-”的函数。我只能使用“+”“/”和“%”。

我注意到很多人都在使用移位方法，但我不能不使用，因为我们还没有学习它。

尽管我可以在没有 1 个 while 循环的情况下轻松做到这一点，但诀窍是它应该具有 n log n 或 log n 运行时效率。

没有列表也没有数组，尽管我没有看到任何使用它们的方法。

有什么可行的方法吗？？？

标签： cmultiplication

Answer 1

这个算法是 O(nlogn)。分而治之。

double Multiply(int n, double x) {
    if (n == 0) 
        return 0.0;
    if (n == 1)
        return x;
    double a = Multiply(n/2, x);
    if ((n%2) == 1)
        return x + a + a;
    return a + a;
}

注意：代码未经测试。我无法在 iPad 上编译 C 代码。