用非常规方法求1+2+···+n

用非常规方法求1+2+···+n2015-09-28今天在《剑指offer》里看到了下面这样一个简单且有趣的题，考察程序员的发散思维能力，前提是你对C++相关知识点熟悉，否则是想不出来方案的，分享给大家。

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

点评：这个问题本身没有太多的实际意义，因为在软件开发中不可能有这么苛刻的限制。但不少面试官认为这是一道不错的能够考查应聘者发散思维能力的题目，而发散思维能够反映出应聘者知识面的宽度，以及对编程相关技术理解的深度。

分析：通常求1+2+ ··· +n有三种常规思路：（1）循环；（2）递归（需要用if语句或者条件判断语句来判断是继续递归下去还是终止递归）；（3）使用公式n*（n+1）/2。因为题目限制，这三种常规方案都不可行。那么如何用非常规方案求解该问题呢？下面提供两种解题思路，对应四种解决方案，本质上还是采用循环或递归的思路，只是写法改变了。

解题思路一：循环角度

基本思想：从循环角度思考。循环只是让相同的代码重复执行n遍而已，我们完全可以不用for和while来达到这个目的。比如下面采用的构造函数法。

方案一：利用构造函数求解

具体方案：我们先定义一个类型，接着创建n个该类型的实例，那么这个类型的构造函数将确定会被调用n次。我们可以将与累加相关的代码放到构造函数里。

实现代码：

class Temp{public:Temp（） { ++N; Sum += N; }static void init（） { N = 0; Sum = 0; }static unsigned int getSum（） { return Sum; }private:static unsigned int N;static unsigned int Sum;};unsigned int Temp::N = 0;unsigned int Temp::Sum = 0;unsigned int sum_solution1（unsigned int n）{Temp::init（）;Temp *temp = new Temp[n];delete []temp;temp = NULL;return Temp::getSum（）;}

解题思路二：递归角度

基本思想：从递归角度思考。根据题目限制我们不能在一个函数中判断递归终止的条件，那么我们不妨定义两个函数：一个函数充当原递归函数中递归的角色，另一个函数处理递归终止的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然的想到布尔变量，比如值为true（1）的时候调用第一个函数，值为false（0）的时候调用第二个函数。那如何将数值变量n转换成布尔变量呢？解决方法就是对n连续做两次取反运算，即！！n，这样非零的n就会转换为true，0就转换为false。

基于该思想有下面三种解决方案。