《剑指offer》第六十四题（求1+2+…+n）-白红宇

《剑指offer》第六十四题（求1+2+…+n）

阅读量：5020 次

发布时间：2019-06-12

本文共 3206 字，大约阅读时间需要 10 分钟。

// 面试题64：求1+2+…+n// 题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case// 等关键字及条件判断语句（A?B:C）。#include 
     
      // ====================方法一====================//使用构造函数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];//建立n次，实现sum加和    delete[]a;    a = NULL;    return Temp::GetSum();}// ====================方法二====================//使用虚函数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_Solution2(int n){    A a;    B b;    Array[0] = &a;    Array[1] = &b;    int value = Array[1]->Sum(n);//当n大于0时，总是执行B类中的sum，直到n=0，!!n=0，然后变成了Array[0]->Sum(n)，即A类，注意Array设成全局变量    return value;}// ====================方法三====================//使用函数指针typedef unsigned int(*fun)(unsigned int);unsigned int Solution3_Teminator(unsigned int n){    return 0;}unsigned int Sum_Solution3(unsigned int n){    static fun f[2] = { Solution3_Teminator, Sum_Solution3 };//静态成员，第一次调用时候建立    return n + f[!!n](n - 1);}// ====================方法四====================//使用模版类型template 
      
        struct Sum_Solution4{    enum Value { N = Sum_Solution4
       
        ::N + n };//Sum_Solution4
        
         ::N就是我们要的值};template <> struct Sum_Solution4<1>{    enum Value { N = 1 };};template <> struct Sum_Solution4<0>{    enum Value { N = 0 };};// ====================测试代码====================void Test(int n, int expected){    printf("Test for %d begins:\n", n);    if (Sum_Solution1(n) == expected)        printf("Solution1 passed.\n");    else        printf("Solution1 failed.\n");    if (Sum_Solution2(n) == expected)        printf("Solution2 passed.\n");    else        printf("Solution2 failed.\n");    if (Sum_Solution3(n) == expected)        printf("Solution3 passed.\n");    else        printf("Solution3 failed.\n");}void Test1(){    const unsigned int number = 1;    int expected = 1;    Test(number, expected);    if (Sum_Solution4
         
          ::N == expected)        printf("Solution4 passed.\n");    else        printf("Solution4 failed.\n");}void Test2(){    const unsigned int number = 5;    int expected = 15;    Test(number, expected);    if (Sum_Solution4
          
           ::N == expected) printf("Solution4 passed.\n"); else printf("Solution4 failed.\n");}void Test3(){ const unsigned int number = 10; int expected = 55; Test(number, expected); if (Sum_Solution4
           
            ::N == expected) printf("Solution4 passed.\n"); else printf("Solution4 failed.\n");}void Test4(){ const unsigned int number = 0; int expected = 0; Test(number, expected); if (Sum_Solution4
            
             ::N == expected) printf("Solution4 passed.\n"); else printf("Solution4 failed.\n");}int main(int argc, char* argv[]){ Test1(); Test2(); Test3(); Test4(); system("pause"); return 0;}