面试题64:求1+2+....+n

题目

求1+2+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句

解题思路和代码

• 利用构造函数求解
  创建n个该类型的实例，那么该类型的构造函数将确定会被调用n次。

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个该类型的实例
    //该类型的构造函数会被调用n次
    delete []a;
    a = NULL;

    return Temp::GetSum();
}

• 虚函数求解
  递归方法，那么递归的终止条件怎么确定呢？
  当n=0时，返回0就可以作为递归的终止条件。那么我们可以定义两个函数，一个函数充当递归函数，一个函数处理终止递归的情况。这是二选一的问题，可以用布尔变量。比如:值为true(1)的时候调用一个函数，值为false(0)的时候调用第二个函数。对非零数值连续做两次反运算可以转换为true.
  ->指向运算符

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);
    return value;
}

• 利用逻辑与的短路特性实现递归终止

1. 当result=0时，~result && (result += Sum_Solution(n-1));~ 只执行前面的判断，为false，直接返回0
2. 当result != 0时， ~result && (result += Sum_Solution(n-1));~通过前面的判断，为true，则执行 ~(result += Sum_Solution(n-1));~ 进入递归函数计算

class Solution{
    public:
     
        int Sum_Solution(int n)
        {
            int result = n;
            result && (result += Sum_Solution(n-1));
            return result;
        }
};

• 利用函数指针求解
  函数指针提前定义函数类型和返回值

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);
}

• 利用模板类型求解

Sum_Solution4<5>::N就是1+2+3+4+5的结果。当编译器看到Sum_Solution4<5>时，就会为模板类Sum_Solution4以参数5生成该类型的代码。但以5为参数的类型需要得到以4为参数的类型，因为Sum_Solution4<5>::N=Sum_Solution4<4>::N+5。这个过程会一直递归到参数为1的类型。

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

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

完整代码见GitHub