剑指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版,暂时没弄太懂,有空了再琢磨琢磨...