浅谈《剑指offer》原题：不使用条件、循环语句求1+2+……+n

2023-02-17 07:42:15

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

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

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

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

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

解法一：利用宏定义求解

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

  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. int main()
  7. {
  8. int sum = 0;
  9. int n = 0;
  10. H;
  11. printf("%d\n", sum);
  12. return 0;
  13. }

怎么样！有木有很搞笑。。。。

解法二：利用构造函数

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

  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. unsigned int Temp::N = 0;
  15. unsigned int Temp::Sum = 0;
  16. unsigned int Sum_Solution1(unsigned int n)
  17. {
  18. Temp::Reset();
  19. Temp *a = new Temp[n];
  20. delete []a;
  21. a = NULL;
  22. return Temp::GetSum();
  23. }
  24. int main()
  25. {
  26. printf("%d\n", Sum_Solution1(1000));
  27. return 0;
  28. }

解法三：利用虚函数求解

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

  1. #include <stdio.h>
  2. #include <iostream>
  3. using namespace std;
  4. class A;
  5. A* Array[2];
  6. class A
  7. {
  8. public:
  9. virtual unsigned int Sum(unsigned int n)
  10. {
  11. return 0;
  12. }
  13. };
  14. class B:public A
  15. {
  16. public:
  17. virtual unsigned int Sum(unsigned int n)
  18. {
  19. return Array[!!n]->Sum(n-1) + n;
  20. }
  21. };
  22. int Sum_Solutiion2(int n)
  23. {
  24. A a;
  25. B b;
  26. Array[0] = &a;
  27. Array[1] = &b;
  28. int value = Array[1]->Sum(n);
  29. return value;
  30. }
  31. int main()
  32. {
  33. printf("%d\n", Sum_Solutiion2(1000));
  34. return 0;
  35. }

这种思路基于虚函数来实现函数的选择，当n不为0的时候，一直调用的是B::Sum()；当n等于0时，调用的就是函数A::Sum()。

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

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

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

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

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

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

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

上一篇：剑指offer（20）包含min函数的栈


下一篇：windows命令行