首页 > 试题广场 > 求1+2+3+...+n
[编程题]求1+2+3+...+n
  • 热度指数:298719 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
推荐
class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n - 1));
        return ans;
    }
};

编辑于 2015-06-19 17:53:23 回复(102)

class assist{
public:
    assist() {N++;sum += N;}
    static void reset(){N=0;sum=0;}//在VS中不需要此调用函数也可以(不进行多加一次)
    static unsigned int GetSum(){return sum;}
private:
    static int N;
    static int sum;
};
int assist::N = 0;
int assist::sum = 0;
//设置一个静态变量N和sum,在构造函数中进行累加运算;
//然后构造一个以辅助类为类型、大小为n的数组,重复调用此构造函数n次来实现n次的累加运算
class Solution {
public:
    int Sum_Solution(int n) {
        assist::reset();
        assist * p = new assist[n];
        delete []p;
        p = nullptr;
        return assist::GetSum();
    }
};
//第二种方法:使用模板函数进行编程,显示定义输入参数为1的模块
    template <int m> inline int SumTo() { return m + SumTo<m-1>(); }  template <> inline int SumTo<1>() { return 1; }
//第三种方法:使用虚函数
class Base; Base* Array[2]; class Base{ public:      virtual int Sum(int n){return 0;} }; class Derived : public Base{ public:     virtual int Sum(int n){return Array[!!n]->Sum(n-1) + n;}      }; //使用虚函数来构造递归,在基类种定义虚函数Sum(n)返回0,通过将指针数组的两个元素分别绑定到基类和派生类,其中基类的Sum() //结束递归,!!n来构造true(1) false(0)来对指针数组进行访问 class Solution { public:     int Sum_Solution(int n) {         Base a;         Derived b;         Array[0] = &a;         Array[1] = &b;         return b.Sum(n);     } };
//使用短路计算来构造递归:重点是输入0的时候输出0来结束递归 //缺点:递归的层数不能太深<3000 class Solution { public:     int Sum_Solution(int n) {         int ret = n;         n && (ret += Sum_Solution(n-1));          return ret;     } };

编辑于 2017-12-13 22:30:59 回复(16)
解题思路:
1.需利用逻辑与的短路特性实现递归终止。 2.当n==0时,(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断,为false,然后直接返回0;
3.当n>0时,执行sum+=Sum_Solution(n-1),实现递归计算Sum_Solution(n)。
    public int Sum_Solution(int n) {
    	int sum = n;
    	boolean ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
    	return sum;
    }

编辑于 2015-08-14 09:42:59 回复(51)
//其实只要先看我们手里有什么牌就能一步一步想到利用短路特性了
//我们手里现在可以使用(按优先级高低)单目运算符:++和--,双目运算符:+,-,移位运算符<<和>>,关系运算符>,<等,逻辑运算符&&,||,&,|,^,赋值=
//单目和双目的作用是一样的,移位显然没有规律性,因为一个二进制位并不能区分某个数和其他数,这也就排除了&,|,^,因为不需要做位运算了
//关系运算符要和if匹配,但这是不行的,这时看看剩下的运算符只能选&&,||了
//如果做过Java笔试题,会对这两个运算符非常敏感,他们有短路特性,前面的条件判真(或者假)了,就不会再执行后面的条件了
//这时就能联想到--n,直到等于0就能返回值。
public class Solution {
    public int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum>0)&&((sum+=Sum_Solution(--n))>0);
        return sum;
    }
}

编辑于 2016-09-08 10:27:49 回复(12)
用公式是不可以的,公式里有乘法!!实现乘法可以用sizeof***数组,两行代码就可以
class Solution {
public:
    int Sum_Solution(int n) {
        bool a[n][n+1];
        return sizeof(a)>>1;
    }
};

发表于 2015-12-05 14:56:41 回复(81)
总结前面大牛们的方法,提供java的两种阶梯思路:
共同点:一,利用利用短路 && 来实现 if的功能;二,利用递归来实现循环while的功能
不同点:方法一:递归实现1+2+..+n;方法二:n(n+1)/2,递归实现n(n+1);方法三,利用Math实现n(n+1)
关于如何递归实现a*b,有大佬总结过,我搬下来:利用位运算来做,快速幂,快速模乘,
原理是把a拆成2的幂的和,a = 2^e0 + 2^e1 + 2^e2.... 
     那么 a * b = (2^e0 + 2^e1 + 2^e2+...) * b 
                      = b * 2^e0 + b * 2^e1 + b * 2^e2 + ...
                      = (b << e0) + (b << e1) + ....
接下来看代码:
方法一:递归实现1+2+..+n;
 public static int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && ((sum += Sum_Solution(--n)) > 0);
        return sum;
    }
方法三,利用Math实现n(n+1)
  public static int Sum_Solution1(int n) {
        return (int) (Math.pow(n, 2) + n) >> 1;
    }
方法二:n(n+1)/2,递归实现n(n+1)
先参考使用while的例子,再转换
原理是把a拆成2的幂的和,a = 2^e0 + 2^e1 + 2^e2.... 
 那么 a * b = (2^e0 + 2^e1 + 2^e2+...) * b 
                      = b * 2^e0 + b * 2^e1 + b * 2^e2 + ...
                      = (b << e0) + (b << e1) + ....

public static int Sum_Solution2(int n) {
        int res = 0;
        int a = n;//若a=2=10
        int b = n + 1;//b=3=11
        while (a != 0) {
            if ((a & 1) == 1)//a在第二位==1的时候才更新res=0+110=6
                res += b;
            a >>= 1;//a右移1位 1
            b <<= 1;//b左移动1位 110
        }
        return res>>=1;//n(n+1)/2     }
接下来,用(a & 1) == 1和(a != 0)来代替判断语句
 public int Sum(int n) {
        int res = multi(n, n + 1);//n*(n-1)
        return res>>=1;//n*(n-1)/2
    }
    
    private int multi(int a, int b) {
        int res = 0;
        //循环体内部, if ((a & 1) == 1), res += b;
        boolean flag1 = ((a & 1) == 1) && (res += b) > 0;
        a >>= 1;
        b <<= 1;
        // while (a != 0) {}循环条件
        boolean flag2 = (a != 0) && (res += multi(a,b)) > 0 ;
        return res;
    }


发表于 2018-06-12 18:01:59 回复(4)
//用异常退出递归
public class Solution {
    public int Sum_Solution(int n) {
        return sum(n);
    }
    int sum(int n){
        try{
            int i = 1%n;
            return n+sum(n-1);
        }
        catch(Exception e){
            return 0;
        }
    }
}
发表于 2017-03-17 21:48:18 回复(21)
Python版的短路求值代码来了~
要注意python中逻辑运算符的用法,a  and  b,a为False,返回a,a为True,就返回b
class Solution:
    def Sum_Solution(self, n):
        # write code here
        ans=n
        temp=ans and self.Sum_Solution(n-1)
        ans=ans+temp
        return ans

发表于 2018-02-14 21:38:51 回复(11)
我就猜到大家都是用 && 的短路原则的,这样复杂是O(n)的
我来一个复杂度 32的,可以说O(logM)吧,M是数值大小,对于int也可以说是O(1)吧虽然常数有点大。
原理就是,类似快速幂,俗称快速模乘。
a * b
可以这样算
res = 0
while(a){
    if(a & 1) res += b;
    a >>= 1;
    b <<= 1; 
}
原理是把a拆成2的幂的和,a = 2^e0 + 2^e1 + 2^e2....
那么 a * b = (2^e0 + 2^e1 + 2^e2+...) * b = b * 2^e0 + b * 2^e1 + b * 2^e2 + ...
= (b << e0) + (b << e1) + ....

//奇数返回0xffffffff,否则0
#define f(x) ((((x) & 1) << 31) >> 31)
class Solution {
public:
    int Sum_Solution(int n) {
        int a = n, b = n + 1, s = 0;
        //复制32次。。
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        return s >> 1;
    }
};

编辑于 2016-07-23 03:40:42 回复(44)

python solution:

# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
        # write code here
        return sum(list(range(1,n+1)))
发表于 2017-10-07 17:39:48 回复(31)

各位看官可能觉得O(n)复杂度的算法实在是太糟糕了,这里提供一种新解决思路,我们直接利用位移自己写一个乘法出来,而n*(n+1)/2中最后的除以二操作我们则以左移一位实现,代码如下

class Solution {
public:
    int multi(int a, int b){
        int res = 0;
        (a&1) && (res += b);
        a >>= 1; b <<=1;
        a && (res += multi(a, b));
        return res;
    }
    int Sum_Solution(int n) {
        return multi(n, n+1)>>1;
    }
};
编辑于 2018-04-14 00:18:22 回复(3)
这题剑指offer上说有用构造函数来解的,但是在java中:
temp[] test = new temp[n]
这样的初始化,并不会调用构造函数
这里采用递归调用的思想,并借用&&的短路特性来求解 :
public class Solution {

    public int Sum_Solution(int n) {
        int result = 0;
        int a = 1;
        boolean value = ((n!=0) && a == (result = Sum_Solution(n-1)));
        result += n;    
        return result;
    }

}

编辑于 2015-06-11 16:27:04 回复(6)
public class Solution {
    public int Sum_Solution(int n) {
        n = (int) (Math.pow(n, 2)+n)>>1;
        return n;
    }
}
用了Math的幂函数~不知道算不算严谨~
发表于 2015-06-05 10:36:45 回复(38)
利用逻辑与短路特性
# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
		return n and (n + self.Sum_Solution(n - 1))

发表于 2016-07-27 19:57:12 回复(2)
class Solution {
public:
    int Sum_Solution(int n) {
        return ((int)pow(n,2) + n) >> 1;
    }
};
发表于 2015-09-09 20:53:09 回复(1)
利用&&的短路特性。
int fun(int n, int &sum) {
    n && fun(n-1, sum);
    return (sum += n);
}
发表于 2015-06-03 16:54:49 回复(1)
# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
        res = n
        return n and n + self.Sum_Solution(n-1)

发表于 2018-04-17 13:13:30 回复(4)
1.
import java.util.*;
public class Solution {
    public int Sum_Solution(int n) {
        int sum = n;
        boolean ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
        return sum;
    }
}
2.
import java.util.*;
public class Solution {
    public int Sum_Solution(int n) {
        n = (int)(Math.pow(n,2)+n)>>1;
        return n;
    }
}

发表于 2018-08-19 16:10:37 回复(0)
解题的关键是使用递归,利用递归代替了循环,并且使用逻辑与运算判断n何时为0
class Solution:
    def __init__(self):
        self.sum = 0
    def Sum_Solution(self, n):
        # write code here
        def recur(n):
            self.sum += n
            n -= 1
            return (n>0) and self.Sum_Solution(n)
        recur(n)
        return self.sum
函数recur()实现了循环,从n一直递减加到了1,逻辑与and操作实现了当n=0时,不再计算Sum_Solution(n),
返回self.sum

发表于 2018-03-07 19:51:54 回复(1)
利用逻辑操作的短路性质
class Solution {
public:
	int Sum_Solution(int n) {
		int ret = 0;
		n == 0 || (ret = Sum_Solution(n - 1));
		return n + ret;
	}
};

发表于 2016-04-14 15:47:25 回复(0)

先取对数再指数算回去。就不用傻傻的递归。

class Solution {
public:
    int Sum_Solution(int n) {
        //return n*(n+1)/2;
        return multi(n, n + 1) >> 1;
    }
    int multi(int a, int b){
        // we can guarantee that both a and b is positive integers
        int res = int(pow(10, log10(a) + log10(b))+0.5);
        return res;
    }
};
发表于 2017-03-04 16:00:27 回复(2)

问题信息

难度:
917条回答 113025浏览

热门推荐

通过挑战的用户

查看代码