Skip to content

Latest commit

 

History

History
229 lines (169 loc) · 7.09 KB

47.求1+2+3+...+n.md

File metadata and controls

229 lines (169 loc) · 7.09 KB
Raw

47.求1+2+3+...+n

题目描述

  • 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

 

解题思路

下面的思路来自《剑指offer》，考察的是发散思维。

  • 思路一，构造函数结合类属型和类函数，跳转到代码。

    题目本质上是把某个语句重复执行N次。可以创建一个Temp类，该类有一个类属型N和一个类属性SUM，调用类的Reset()函数的时候将两个类属型清零，调用类的构造函数的时候让N++并且SUM+=N，类似于学面向对象的时候记录总共创建了多少个实例一样。在主函数中创建大小为N的该类的数组，然后把数组内存delete掉，调用类的GetSum函数获取SUM类属型即可。如果把Temp定义在Solution类的里面的话要注意Temp类的静态成员初始化要放在Solution类的外面，但最好不要使用嵌套类，因为比较麻烦。

    • 声明为static的属性为类属性，声明为static的成员函数为类函数，static函数由于没有this指针，因此仅能访问类的静态成员。

    • 注意类的static属性必须在类外进行初始化且必须初始化。初始化时前面不加static，以免与一般静态变量或对象相混淆，静态数据成员初始化的格式：

      <数据类型> <类名>::<静态数据成员名> = <值>;

      例如：int Temp::Sum = 0;

  • 思路二，利用数组充当函数选择器，虚函数结束递归，跳转到代码。

    当n不为0的时候，对n进行两次取反即!!n的结果就是true，而当n为0的时候!!n的结果是false，true和false作为下标的时候相当于1和0，因此可以利用!!n作为数组的下标，选择调用哪个函数，当false作为下标时选择结束递归的函数。这里利用对象数组和虚函数实现，具体的看代码更容易理解。

  • 思路三，利用函数指针数组充当函数选择器，跳转到代码。

    利用上面的原理，将函数指针放到数组中也可以实现，即函数指针数组。

  • 思路四，模版函数或者模板类型，跳转到代码。

    • 模板函数
    template <int m> inline int SumTo() { return m + SumTo<m-1>(); }
template <> inline int SumTo<1>() { return 1; }

    这个方法要求在编译的时候就知道模板参数m的值，即m必须是一个常量，不知道怎么在牛客上测试，在本地使用类似SumTo<5>()的形式直接调用是可以的，但是把5换成一个变量就不行了。

    • 模板类型（==目前没搞懂==）
    template <int n> struct SumTo{
    enum Value {N = n + SumTo<n-1>::N};
};
template <> struct SumTo<1>{
    enum Value {N = 1};
};

    同样要求模板参数n为常量，需要在编译时就确定该常量的值，不知道怎么在牛客上测试，但是在本地通过类似SumTo<5>::N的方式可以得到结果。

下面的思路来自牛客网。

  • 思路五，短路原理，跳转到代码。

    非常巧妙，利用逻辑运算符的特点，a && b表达式中如果表达式a为0或者false就不会计算表达式b，使得当递归到0的时候不再往下递归，代码非常简单，看代码比较容易看懂。

    int Sum_Solution(int n) {
    n && (n += Sum_Solution(n-1));
    return n;
}

 

代码

class Temp{
private:
    static int N;
    static int Sum;
public:
    Temp() {N++; Sum += N;} // 构造函数
    static void Reset() {N=0; Sum=0;}  // 加上这个函数是为了可以多次重复测试
    static int GetSum() {return Sum;} // 加上static，定义成类函数
};
int Temp::N = 0;
int Temp::Sum = 0;

class Solution {
public:
    int Sum_Solution(int n) {
        Temp::Reset();
        Temp* a = new Temp[n];
        delete []a;
        a = NULL;
        return Temp::GetSum();
    }
};
  • 思路一，构造函数结合类属型和类函数，嵌套类，仅内部类的静态成员初始化部分有所不同。
class Solution {
private:
    class Temp{
    private:
        static int N;
        static int Sum;
    public:
        Temp() {N++; Sum += N;} // 构造函数
        static void Reset() {N=0; Sum=0;}  // 加上这个函数是为了可以多次重复测试
        static int GetSum() {return Sum;} // 加上static，定义成类函数
    };

public:
    int Sum_Solution(int n) {
        Temp::Reset();
        Temp* a = new Temp[n];
        delete []a;
        a = NULL;
        return Temp::GetSum();
    }
};
int Solution::Temp::N = 0; // 类成员初始化要放在类定义的后面
int Solution::Temp::Sum = 0;
  • 思路二，利用数组充当函数选择器，虚函数结束递归，跳转到原理。
class A{
public:
    virtual int Sum(int n) {return 0;}
};

A* ObjectArray[2];

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

class Solution {
public:
    int Sum_Solution(int n) {
        A a;
        B b;
        ObjectArray[0] = &a;
        ObjectArray[1] = &b;
        
        return b.Sum(n);
    }
};
  • 思路三，利用函数指针数组充当函数选择器，跳转到原理。
int sum0(int n);  // 先声明函数，用于函数指针数组初始化
int sumN(int n);
int (*FP[2])(int) = {sum0, sumN};  // 函数指针数组
int sum0(int n) {return 0;}
int sumN(int n) {return n + FP[!!n](n-1);}

class Solution {
public:
    int Sum_Solution(int n) {
        return sumN(n);
    }
};

或者借助函数的static变量：

typedef int (*FP)(int);

int sum0(int n) {return 0;}
int sumN(int n) {
    static FP fp[2] = {sum0, sumN};  // 创建函数指针数组
    return n + fp[!!n](n-1);
}
class Solution {
public:
    int Sum_Solution(int n) {
        return sumN(n);
    }
};

  • 思路四，模板函数或者模板类型，本地可用，牛客因为不能在编译时确定模板参数的值，不知道怎么测试， 跳转到原理。

    • 模板函数

      template <int m> inline int SumTo() { return m + SumTo<m-1>(); }
template <> inline int SumTo<1>() { return 1; }

    • 模板类型

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

  • 思路五，短路原理，跳转到原理。

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