美柑の部屋

涙は見せないと誓った。

Loading…

面试问题赏析：求1到N的和

在面试中，我们可能会遇到一些“不走寻常路”的问题。这类问题看似简单，但是经常有许多奇葩的要求。比如我们之前讨论过的一个问题：输入两个int类型的整数a和b，输出二者的和，要求不能使用四则运算符。最后我们得出的解决方法是利用位运算。今天我们再来讨论一道题目：输入一个int类型的正整数n，输出1到n的和，要求不能使用*、/、for、while、if、else、switch、case以及?:等关键字或运算符。

我们可以思考一下，如果不考虑这些限制条件，我们应该怎么去做。能想到的方法无非三种：首先是直接输出结果n*(n+1)/2（但是出现了乘除法，不能用）；其次是利用循环（显然不能用）；最后是利用递归（递归需要用条件判断语句判断是否达到终止条件，所以不能用）。
其实，上面提到的“不能用”，指的是我们不能在程序中显式地使用。我们仍然可以隐式地使用它们，也就是让编译器代替我们实现循环或条件判断。如果能发现这一点，我们就可以想出很多解法来了，在这里列举其中四种。

一、让编译器代替我们实现循环

方法一

假设我们有一个类Sum，在我们执行语句new Sum[n]时，会调用n次类Sum的构造函数。我们可以在类Sum中声明两个静态成员变量sum和n，并且分别初始化为0和1。在Sum的构造函数中，我们可以令sum+=n，然后n+=1。这样在构造函数被调用n次之后，Sum::sum的值就是我们想要的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Sum{
public:
    static int n;
    static int sum;
    Sum(){
        sum += (n++);
    }
};

int Sum::n = 1;
int Sum::sum = 0;
int main(){
    int n;
    cin >> n;
    Sum* dump = new Sum[n];
    cout << Sum::sum << endl;
    delete[] dump;
    return 0;
}

这种方法需要我们理解什么是一个类的静态成员，还需要我们知道在通过new操作符为类的一个或多个实例动态分配内存空间的时候，类的构造函数是会被调用的。在用代码实现的时候，我们还需要清楚类的静态成员变量是如何初始化的。

关于static成员变量和函数的一些补充展开

二、让编译器代替我们实现条件判断

方法二

我们知道，C++有一种语言特性叫做短路求值。具体来讲，在逻辑与操作符中，如果前面一个表达式值为false，不必对后面的表达式再做判断，直接返回false；在逻辑或操作符中，如果前面一个表达式值为true，不必对后面的表达式再做判断，直接返回true。我们可以发现，短路求值的效果和条件判断语句是很类似的。
假设我们用递归来实现求和的功能，递归函数为getSum(int n)，我们需要该函数达到以下效果：n==0的时候达到终止条件，不做递归调用；n>0的时候递归调用getSum(n-1)。参考刚才提到的短路求值，我们可以写出表达式n && getSum(n-1)，这个表达式刚好满足我们的要求。

1
2
3
4
5
6
7
8
9
10
11
12
13

int sum = 0;

int getSum(int n){
    n && getSum(n-1);
    return (sum += n);
}

int main(){
    int n;
    cin >> n;
    cout << getSum(n) << endl;
    return 0;
}

如果说上一种方法考察我们对静态成员变量的理解，这种方法则考察我们对短路求值这种语言特性的认识。

方法三

我们先观察一个表达式!!n。在n==0的时候，!n为true，!!n则为false，转化成整形则为0；在n>0的时候，!n为false，!!n则为true，转化成整形则为1。也就是说，这个表达式在n==0的时候返回0，其余情况返回1。
在了解了这一点之后，我们可以写出下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int getSumZero(int n);
int getSum(int n);
typedef int (*Func)(int n);
Func functions[2] = {getSumZero, getSum};

int getSumZero(int n){
    return 0;
}

int getSum(int n){
    return n + functions[!!n](n-1);
}

int main(){
    int n;
    cin >> n;
    cout << getSum(n) << endl;
    return 0;
}

可以看到，我们首先声明了两个函数，其中getSumZero对应递归的终止条件，而getSum则是递归的主函数。然后我们声明了一个由函数指针构成的数组functions，数组的长度为2，而数组的每个元素都是Func类型。根据之前我们定义的类型别名，我们知道Func类型实际上指的是一种函数指针类型，这种函数指针指向一个参数为int且返回值为int的函数。
在getSum函数的实现中，我们发现：当n>0时，我们会调用functions[1](n-1)，这其实是对getSum自身的递归调用；当n==0时，调用的则是getSumZero(n-1)，这就是递归的终止条件。通过!!n的值，我们可以从数组中选择一个函数进行调用，实现了隐式的条件判断。
这种方法需要我们理解C++中布尔类型和整数类型之间是如何进行转换的，也需要我们对函数指针的使用方法有一个大致的了解。

方法四

这个方法总体上和上一种方法类似，但是没有使用函数指针，而是使用了类的继承与虚函数。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class A;
class B;
A* arr[2];

class A{
public:
    virtual int getSum(int n){ return 0; }
};

class B : public A{
public:
    virtual int getSum(int n){ return n + arr[!!n]->getSum(n-1); }
};

int main(){
    int n;
    cin >> n;

    arr[0] = new A();
    arr[1] = new B();
    cout << arr[1]->getSum(n) << endl;
    delete arr[0];
    delete arr[1];
    return 0;
}

可以看到，我们定义了两个类A和B，其中B是A的子类。它们有一个虚成员函数getSum，其中A::getSum直接返回0，对应递归的终止条件；B::getSum覆盖了其父类的定义，对应递归的主函数。程序定义了一个A*类型的数组，其第一个元素指向一个A类型的实例，第二个元素指向一个B类型的实例。由于getSum是虚函数，程序会根据指针实际指向的类型（动态类型），而不是其声明时的类型A*（静态类型）进行调用。
其实，这个方法本质上与上一种方法是相同的，因为虚函数（多态）的实现方式是虚表，而虚表实际上就是由一些函数指针构成的。这种方法需要我们对类的继承、虚函数、多态等知识有一个清晰的了解，这些内容是C++的精华，在面试中也是必不可少的。

总结

通过上面几种方法我们可以发现，这个问题表面上是让我们实现一个求和的功能，实际上考察的是我们对C++一些重要的语言特性的了解程度，以及我们从这些语言特性入手解决问题的创新能力。

评论