剑指Offer - 面试题64：求1+2+...+n

题目

求1+2+…n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)

分析

递归法

当我们第一眼看见题，循环、递归、还有公式法等。但是当我们看完要求后，发现我们想的各种解法都包含了条件中禁止的要求。

循环必须要for、while、do while,所以pass掉。公式法必须要乘除法，也pass掉。

那么我们只能从递归下手了。我们先写一个不受限制的递归求累加

int sumNums(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    return n + sumNums(n - 1);
}

现在唯一有问题的就是if语句。仔细一想我们使用&&的一个功能来代替if语句。当&&前面的表达式不成立时就不执行&&后面的表达式也就递归结束了。n > 0 && (n += sumNums(n - 1))，然后当n=0时，我们就返回n即可。

#include <iostream>
using namespace std;
int sumNums(int n)
{
    bool sign = n > 0 && (n += sumNums(n - 1));
    return n;
}
int main()
{
    int n = 0;
    cout << "n = ";
    cin >> n;
    cout << "1+2+...+" << n << " = " << sumNums(n);
    return 0;
}

数学法

1+2+…+10的累加就是下图矩阵的蓝色区域

我们再补一列，如下图 发现刚好就是矩阵的一半。这个时候你应该明白怎么做了吧。

创建一个二维数组sign[n][n+1]且为char类型（因为char类型刚好一个字节，后面不用除法），然后求出数组的字节数刚好就是矩阵的总格子数。然后右移一次就刚刚好。本质就是累加求和公式(n*(n+1))/2。

#include <iostream>
using namespace std;
int sumNums(int n)
{
    bool arr[n][n + 1];
    return static_cast<int>(sizeof(arr) >> 1);
}
int main()
{
    int n = 0;
    cout << "n = ";
    cin >> n;
    cout << "1+2+...+" << n << " = " << sumNums(n);
    return 0;
}

在《剑指Offer》书中还有几种比较巧妙的解法。感兴趣的可以直接去读。我这里附上PDF链接剑指Offer第二版PDF+源码。

本章完!