您的位置: 首页  >  IT文章  >  浅谈《剑指offer》原题：不使用条件、循环语句求1+2+……+n 解法一：利用宏定义求解 解法二：利用构造函数 解法三：利用虚函数求解 解法四：利用函数指针求解 解法五：利用模板类型来求解

浅谈《剑指offer》原题：不使用条件、循环语句求1+2+……+n 解法一：利用宏定义求解 解法二：利用构造函数 解法三：利用虚函数求解 解法四：利用函数指针求解 解法五：利用模板类型来求解

分类: IT文章 • 2023-12-02 14:56:19

转载自：浅谈《剑指offer》原题：求1+2+……+n

如侵犯您的版权，请联系：windeal12@qq.com



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

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

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

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

[cpp] view plaincopy
  1. #include <stdio.h>  
  2. #define L   sum+=(++n);  
  3. #define K   L;L;L;L;L;L;L;L;L;L;  
  4. #define J   K;K;K;K;K;K;K;K;K;K;  
  5. #define H   J;J;J;J;J;J;J;J;J;J;  
  6.   
  7. int main()  
  8. {  
  9.     int sum = 0;  
  10.     int n = 0;  
  11.     H;  
  12.     printf("%d ", sum);  
  13.     return 0;  
  14. }  
怎么样！有木有很搞笑。。。。

解法二：利用构造函数

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

[cpp] view plaincopy
  1. #include <stdio.h>  
  2. #include <iostream>  
  3. using namespace std;  
  4. class Temp  
  5. {  
  6. public:  
  7.     Temp(){++N; Sum += N;}  
  8.     static void Reset(){N=0; Sum=0;}  
  9.     static unsigned int GetSum(){return Sum;}  
  10. private:  
  11.     static unsigned int N;  
  12.     static unsigned int Sum;  
  13. };  
  14.   
  15. unsigned int Temp::N = 0;  
  16. unsigned int Temp::Sum = 0;  
  17.   
  18. unsigned int Sum_Solution1(unsigned int n)  
  19. {  
  20.     Temp::Reset();  
  21.   
  22.     Temp *a = new Temp[n];  
  23.     delete []a;  
  24.     a = NULL;  
  25.     return Temp::GetSum();  
  26. }  
  27.   
  28. int main()  
  29. {  
  30.     printf("%d ", Sum_Solution1(1000));  
  31.     return 0;  
  32. }  

解法三：利用虚函数求解

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

[cpp] view plaincopy
  1. #include <stdio.h>  
  2. #include <iostream>  
  3. using namespace std;  
  4.   
  5. class A;  
  6. A* Array[2];  
  7.   
  8. class A  
  9. {  
  10. public:  
  11.     virtual unsigned int Sum(unsigned int n)  
  12.     {  
  13.         return 0;  
  14.     }  
  15. };  
  16. class B:public A  
  17. {  
  18. public:  
  19.     virtual unsigned int Sum(unsigned int n)  
  20.     {  
  21.         return Array[!!n]->Sum(n-1) + n;  
  22.     }  
  23. };  
  24.   
  25. int Sum_Solutiion2(int n)  
  26. {  
  27.     A a;  
  28.     B b;  
  29.     Array[0] = &a;  
  30.     Array[1] = &b;  
  31.     int value = Array[1]->Sum(n);  
  32.     return value;  
  33. }  
  34. int main()  
  35. {  
  36.     printf("%d ", Sum_Solutiion2(1000));  
  37.     return 0;  
  38. }  
这种思路基于虚函数来实现函数的选择，当n不为0的时候，一直调用的是B::Sum()；当n等于0时，调用的就是函数A::Sum()。


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

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

[cpp] view plaincopy
  1. #include <stdio.h>  
  2.   
  3. typedef unsigned int (*fun)(unsigned int);  
  4.   
  5. unsigned int Sum_Solutiion3_Teminator(unsigned int n)  
  6. {  
  7.     return 0;  
  8. }  
  9.   
  10. unsigned int Sum_Solutiion3(unsigned int n)  
  11. {  
  12.     static fun f[2] = {Sum_Solutiion3_Teminator, Sum_Solutiion3};  
  13.     return n + f[!!n](n-1);  
  14. }  
  15.   
  16. int main()  
  17. {  
  18.     printf("%d ", Sum_Solutiion3(1000));  
  19.     return 0;  
  20. }  

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

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

[cpp] view plaincopy
  1. #include <stdio.h>  
  2. #include <iostream>  
  3.   
  4. template <unsigned int n>struct Sum_Solutiion4  
  5. {  
  6.     enum Value{N = Sum_Solutiion4<N-1>::N + n};  
  7. };  
  8.   
  9. template <> struct Sum_Solutiion4<1>  
  10. {  
  11.     enum Value{N = 1};  
  12. };  
  13.   
  14. int main()  
  15. {  
  16.     printf("%d ", Sum_Solutiion4<1000>::N);  
  17.     return 0;  
  18. }  

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


相关推荐