C++版 - 剑指offer 面试题46：求1+2+3+...+n(不能使用乘除法、循环语句及条件判断语句) 题解

剑指offer 面试题： 求1+2+3+...+n

提交网址： http://www.nowcoder.com/practice/7a0da8fc483247ff8800059e12d7caf1?tpId=13&tqId=11200

参与人数：2426  时间限制：1秒  空间限制：32768K

题目描述

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

分析：

方法1： 短路与&&、短路或|| + 递归

不能用判断语句的关键字，但是能想到短路与&&、短路或||的特性：如果 || 前面一个为真，则||后面的不会再执行，如果 && 前面一个为假，则&&后面的不会再执行。

AC代码：

#include <iostream>
using namespace std;
class Solution {
public:
    int Sum_Solution(int n) {
        int res=n;
        res&&(res += Sum_Solution(n-1));
        return res;  // n=0时，累加和为0
    }
};
// 以下为测试部分
/* 
int main()
{
	Solution sol;
	cout<<sol.Sum_Solution(3)<<endl;
	return 0;
}
*/

方法2：使用二维数组+sizeof操作符+位操作

由于计算结果比较容易得到，即为 n(n+1)/2，故若选取占用1个Byte的bool(或char)型数组arr[n][n+1]，则sizeof(char)*n(n+1)>>1即为所求，如果选取占用4个Byte的int型数组arr[n][n+1]，则sizeof(int)*n(n+1)>>3 (和为\(\frac{n\cdot (n-1)}{2}\) ，sizeof int = 4，右移3位即除以8)即为所求。不过由于char可能会在不同的编译器上占的字节数不一样，不建议使用。本人选用了int型二维数组来解决。

AC代码：

class Solution {
public:
    int Sum_Solution(int n) {
        int a[n][n+1];
        return sizeof(a)>>3;
    }
};

为何向右移3位？(sizeof int = 4，右移3位即除以8)

\(1+2+3+...+n = \frac{n\cdot (n-1)}{2}\) =  \(\frac{4 \cdot {n\cdot (n-1)}}{8}\)

方法3：使用构造函数

方法4：使用函数指针

方法5：使用虚函数

方法6：使用模板函数(C++、Java等支持泛型)

后面4种方法来自于剑指offer原书2014版，暂时没弄太懂，有空了再琢磨琢磨...