首页 > 代码库 > 浅谈《剑指offer》原题:求1+2+……+n

浅谈《剑指offer》原题:求1+2+……+n

《剑指offer》上的一道原题,求1+2+……+n,要求不能使用乘除法,for、while、if、else、switch、case等关键字以及条件判断语句(a?b:c)。

第一次看到这道题大约有一年的时间了,在霸笔网易的时候,当时我就晕了。。。心想这是神马东西,后来发现这是原题!!然后后悔自己没看过书了。。。

《剑指offer》上给出了不错的解法,但是这里有个解法更巧妙,虽然技术含量不高,但是可以参考,这就是《程序员面试笔试宝典》中所给出的答案。

解法一:利用宏定义求解

假设n=1000。相信看到答案的你们都会笑了。

#include <stdio.h>
#define L	sum+=(++n);
#define K	L;L;L;L;L;L;L;L;L;L;
#define J	K;K;K;K;K;K;K;K;K;K;
#define H	J;J;J;J;J;J;J;J;J;J;

int main()
{
	int sum = 0;
	int n = 0;
	H;
	printf("%d\n", sum);
	return 0;
}
怎么样!有木有很搞笑。。。。

解法二:利用构造函数

实际上就是利用类里面的静态成员变量,然后通过构造函数去调用。其实对于c++掌握熟练的人来说,也可以很轻松的明白。

#include <stdio.h>
#include <iostream>
using namespace std;
class Temp
{
public:
	Temp(){++N; Sum += N;}
	static void Reset(){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::Reset();

	Temp *a = new Temp[n];
	delete []a;
	a = NULL;
	return Temp::GetSum();
}

int main()
{
	printf("%d\n", Sum_Solution1(1000));
	return 0;
}

解法三:利用虚函数求解

这也利用了多态的性质,特别巧妙。

#include <stdio.h>
#include <iostream>
using namespace std;

class A;
A* Array[2];

class A
{
public:
	virtual unsigned int Sum(unsigned int n)
	{
		return 0;
	}
};
class B:public A
{
public:
	virtual unsigned int Sum(unsigned int n)
	{
		return Array[!!n]->Sum(n-1) + n;
	}
};

int Sum_Solutiion2(int n)
{
	A a;
	B b;
	Array[0] = &a;
	Array[1] = &b;
	int value = http://www.mamicode.com/Array[1]->Sum(n);>	这种思路基于虚函数来实现函数的选择,当n不为0的时候,一直调用的是B::Sum();当n等于0时,调用的就是函数A::Sum()。


解法四:利用函数指针求解

在纯C语言的编程环境中,我们不能使用虚函数,这时候函数指针就可以达到一样的效果了!

#include <stdio.h>

typedef unsigned int (*fun)(unsigned int);

unsigned int Sum_Solutiion3_Teminator(unsigned int n)
{
	return 0;
}

unsigned int Sum_Solutiion3(unsigned int n)
{
	static fun f[2] = {Sum_Solutiion3_Teminator, Sum_Solutiion3};
	return n + f[!!n](n-1);
}

int main()
{
	printf("%d\n", Sum_Solutiion3(1000));
	return 0;
}

解法五:利用模板类型来求解

本质都是多态。可惜不是所有编译器都支持,VC++6.0就不支持。。

#include <stdio.h>
#include <iostream>

template <unsigned int n>struct Sum_Solutiion4
{
	enum Value{N = Sum_Solutiion4<N-1>::N + n};
};

template <> struct Sum_Solutiion4<1>
{
	enum Value{N = 1};
};

int main()
{
	printf("%d\n", Sum_Solutiion4<1000>::N);
	return 0;
}

感觉这道题这些方法都能理解的话,说明c++水平已经不错了,我当时第一次看见都是云里雾里的!




浅谈《剑指offer》原题:求1+2+……+n