整数除法

Question

我曾面临以下面试问题。

考虑这个函数声明：

void 测验(int i)
{
    如果（i>1）
    {
        测验（i / 2）；
        测验（i / 2）；
    }
    写输出（“*”）；
}

函数调用quiz(5)打印了多少个星号？

我的回答是：

具有整数除法结果类型的语言（Javascript、PHP 等）是 浮动 - 七个星号。函数测验被调用：

1. 当 i=5 – 一次，打印星号。
2. 当 i=2.5 – 两次时，打印星号。
3. i=1.25 – 四次，打印星号。
4. i=0.625 – 八次，不打印星号

除法结果类型名称为的语言（C/C++、C#、Java 等） 整数 - 三个星号。函数测验被调用：

1. 当 i=5 – 一次，打印星号。
2. 当 i=2 – 两次时，打印星号。
3. 当 i=1 – 四次时，不打印星号。

问题语法类似于C/C++、Java，所以答案是三个

面试是闭卷考试 - 在面试期间我无法运行此代码并检查它。面试官告诉我，我的回答并不绝对正确（或者至少，他们没想到会是这样）。然而，我已经在家里运行了这段代码（使用 PHP、Javascript 和 C#），结果正如我所描述的那样。

那么，我是否遗漏了一些警告，或者我的回答比他们预期的更详细？

Answer 1

如果将代码更改为：

void quiz(int i)
{
    if (i > 1)
    {
        quiz(i / 2);
        quiz(i / 2);
    }
    printf("* for %d\n", i);
}

您将看到 quiz(5) 的结果是：

* for 1
* for 1
* for 2
* for 1
* for 1
* for 2
* for 5

因此，您得到了每个 i 的正确调用次数，您只是没有注意到 writeOutput是在 if 之外，而不是在 if 之内。

Answer 2

当 i <= 1 时， writeOutput 也会被调用。

Answer 3

鉴于该函数采用 int 作为参数，它（在通常情况下）永远不会将 2.5 作为参数。当然，除非有人说#define double int，但在这种情况下，没有什么是可靠的了。

所以你的答案可能应该只是你答案的第二部分。

Answer 4

我在 Java 中得到 7：

public class fun {



public void quiz(int i)
{

    if (i > 1)
    {
        quiz(i / 2);
        quiz(i / 2);
    }
    System.out.println("Value of i = " + i);
    System.out.println("*");
}

public static void main(String[] args){

    fun f = new fun();
    f.quiz(5);

}
}

输出 =

Value of i = 1
*
Value of i = 1
*
Value of i = 2
*
Value of i = 1
*
Value of i = 1
*
Value of i = 2
*
Value of i = 5
*

有两件事使得这个简单的函数很难手动跟踪。

第一：递归。递归函数使用调用堆栈，很难在纸上跟踪 i 的状态......尤其是在面试中;-)

第二：就像其他人所说的那样， print(*) 位于 if 之外......也许有一点收获！

Answer 5

我认为除了答案之外，如果你能提供复杂性分析，面试官会很高兴。
复杂度为 2**ceil(lg(n))-1 （其中 ** 是幂运算符）：

您可以通过编写一棵树来可视化它以及我们得到的结果是一个严格且完整的二叉树（下面是 n=5 的情况，为简洁起见省略了几个节点）

           5
         /   \
        2     2
       / \   /  \
      1   1 1    1
     / \  ..........
    0   0 ..............

另外，从问题来看，我不认为面试官期望对其他语言进行分析，例如 python 3.x，其中默认行为是浮点除法，*会打印更多次。当预设浮点数时，调用次数为： 2 ** (ceil(lg(n))+1) -1 ，（调用树会比整数除法，让我们练习一下:)）

您可以运行以下Python代码：

nCalls = 0
def quiz(n):
    global nCalls
    nCalls += 1
    if n>1:
        quiz(n/2)
        quiz(n/2)

test = [5, 9, 15]
for n in test:
    nCalls = 0
    quiz(n)
    print("nCalls for %d : %d" % (n,nCalls) )

在Python 2.x上：（整数除法）

nCalls for 5 : 7
nCalls for 9 : 15
nCalls for 15 : 15

在Python 3.x上：（浮点）

nCalls for 5 : 15
nCalls for 9 : 31
nCalls for 15 : 31

HTH。