来源：据说是某一年某个公司的面试题
题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、s witch、case 等关键字以及条件判断语句（A?B:C）
分析：这题本来很简单，但是不能用循环和条件判断语句。但是理论上所有的递归都可以转化为循环，那是否可以用递归代替循环呢？照着这个思路走下去，貌似可以。可是用递归的话，递归怎么终止呢？这就得在return语句中做文章了。最让人奔溃的是不让用乘除法。但是乘法本质上是加法的累加。
思路：
- 把循环化为递归。
- 乘法改为递归实现的累加。
- 递归的终止靠return语句做文章。
我最终的答案如下（包括测试程序）：
#include <stdio.h>
int sum = 0;
_Bool summation(int n)
{
sum += n;
return n-1 && summation(n-1);
}
int main()
{
int n;
scanf("%d",&n);
summation(n);
printf("%d\n",sum);
return 0;
}
上面代码最妙的地方在与return n-1 && summation(n-1)，利用了&&的运算规则，解决了递归终止的问题。
编译加上参数-std=c99，测试了几个数据，结果正确。
后记：
1.不知道return语句中的 n-1 && summation(n-1)算不算判读语句，算不算违规。如果不算的话，我觉得我的答案还是很简单的。算的话，那我的答案就不合格了。
2.全局变量可以改成函数中的静态变量，如果觉得全局变量不优雅的话。
3.根据网友Jujy给出的答案，他是用了宏定义和移位运算，答案比我这里的稍显麻烦，但他没用递归，我没看懂。
参考文档：珍藏版]微软等数据结构+算法面试100 题全部出炉 [完整100 题下载地址]：
http://download.csdn.net/source/2885434
转自：http://blog.csdn.net/candcplusplus/article/details/11841979
分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能有效地考查发散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。
通常求1+2+…+n除了用公式n(n+1)/2之外，无外乎循环和递归两种思路。由于已经明确限制for和while的使用，循环已经不能再用了。同样，递归函数也需要用if语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。
我们仍然围绕循环做文章。循环只是让相同的代码执行n遍而已，我们完全可以不用for和while达到这个效果。比如定义一个类，我们new一含有n个这种类型元素的数组，那么该类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。如下代码正是基于这个思路：
class Temp
{
public:
Temp() { ++ N; Sum += N; }
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n];
delete []a;
a = 0;
return Temp::GetSum();
}
我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归，我们不妨定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture（1）的时候调用第一个函数，false（0）的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为false。有了上述分析，我们再来看下面的代码：
class A;
A* Array[2];
class A
{
public:
virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
return value;
}
这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数B::Sum；当n为0时，执行A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些：
typedef int (*fun)(int);
int solution3_f1(int i)
{
return 0;
}
int solution3_f2(int i)
{
fun f[2]={solution3_f1, solution3_f2};
return i+f[!!i](i-1);
}
--------------------------
不用循环/goto/递归输出1~100的10种写法
1、使用逗号表达式
|
1
2
3
4
5
6
7
8
9
10
11
|
#include<iostream>using namespace std;
int i;
void b() { cout << i++ << endl; }
void c() { b(), b(), b(), b(), b(); }
void a() { c(), c(), c(), c(), c(); }
int main()
{ i = 1;
a(), a(), a(), a();
} |
2、巧妙宏写法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <stdio.h>#define F4 "%d\n%d\n%d\n%d\n"#define F20 F4 F4 F4 F4 F4#define F100 F20 F20 F20 F20 F20#define X4(y) , y, y + 1, y + 2, y + 3#define X20(y) X4(y) X4(y + 4) X4(y + 8) X4(y + 12) X4(y + 16)#define X100(y) X20(y) X20(y + 20) X20(y + 40) X20(y + 60) X20(y + 80)int main()
{ printf(F100 X100(1));
return 0;
} |
3、C++模板元
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <stdio.h>template<int N>
struct X : X<N - 1>
{ X() { printf("%d\n", N); }
};template<>
struct X<0> {};
int main()
{ X<100> x;
return 0;
} |
4、利用类对象数组的构造递增静态变量
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <stdio.h>class X
{public:
X() { ++i; printf("%d\n", i); }
private:
static int i;
};int X::i = 0;
int main()
{ X arr[100];
return 0;
} |
5、二逼青年写法
|
1
2
3
4
5
6
|
#include <iostream>int main()
{ std::cout << "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n24\n25\n26\n27\n28\n29\n30\n31\n32\n33\n34\n35\n36\n37\n38\n39\n40\n41\n42\n43\n44\n45\n46\n47\n48\n49\n50\n51\n52\n53\n54\n55\n56\n57\n58\n59\n60\n61\n62\n63\n64\n65\n66\n67\n68\n69\n70\n71\n72\n73\n74\n75\n76\n77\n78\n79\n80\n81\n82\n83\n84\n85\n86\n87\n88\n89\n90\n91\n92\n93\n94\n95\n96\n97\n98\n99\n100\n";
return 0;
} |
6、使用setjmp/longjmp实现循环
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <csetjmp>#include <iostream>using namespace std;
int main()
{ jmp_buf b;
int x = 1;
setjmp(b);
cout << x++ << endl;
if (x <= 100)
longjmp(b, 1);
return 0;
} |
7、python曲线救国
|
1
2
3
4
5
6
7
8
9
10
|
#include <stdlib.h>#include <stdio.h>int main()
{ FILE *f = fopen("foo.py","w");
fprintf(f,"print range(1,101)");
fclose(f);
return system("python foo.py");
} |
8、C++11优雅实现
|
1
2
3
4
5
6
7
8
9
10
11
|
#include <iostream>#include <numeric>#include <iterator>#include <array>int main()
{ std::array<int, 100> arr;
std::iota(std::begin(arr), std::end(arr), 1);
std::copy(std::begin(arr), std::end(arr), std::ostream_iterator<int>(std::cout, "\n"));
} |
9、汇编实现跳转
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <iostream>using namespace std;
int main(void)
{ int i = 1;
__asm begin_loop:
if (i <= 100)
{
cout << i << endl;
i++;
__asm jmp begin_loop;
}
return 0;
} |
10、创建子进程
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>#include <stdlib.h>int main()
{ int x = 0;
x |= !fork() << 0;
x |= !fork() << 1;
x |= !fork() << 2;
x |= !fork() << 3;
x |= !fork() << 4;
x |= !fork() << 5;
x |= !fork() << 6;
if(1 <= x && x <= 100) std::cout << x << std::endl;
return 0;
}* 注：输出顺序可能无法保证 |