首页 > 试题广场 >

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

[编程题]求1+2+3+...+n
  • 热度指数：377253 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

数据范围：
进阶： 空间复杂度 ，时间复杂度
示例1

输入

5

输出

15
示例2

输入

1

输出

1
算法知识视频讲解
添加回答
推荐
Bine头像 Bine 
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 回复(107)
Java
拼多多招聘头像 拼多多招聘
总结前面大牛们的方法，提供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 回复(6)
Python
hichenway头像 hichenway
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)
单程车票头像 单程车票
这题剑指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 回复(7)
请叫我小奋青头像 请叫我小奋青
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)
Python
Yannyezixin头像 Yannyezixin
利用逻辑与短路特性 
# -*- 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)
SHINE.头像 SHINE.
class Solution {
public:
    int Sum_Solution(int n) {
        return ((int)pow(n,2) + n) >> 1;
    }
};
发表于 2015-09-09 20:53:09 回复(1)
Howie59头像 Howie59 
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)
ChrisZZ头像 ChrisZZ

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

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)
nailperry头像 nailperry 
解题思路：
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 回复(52)
S向J前W冲头像 S向J前W冲
用公式是不可以的，公式里有乘法！！实现乘法可以用sizeof***数组，两行代码就可以
class Solution {
public:
    int Sum_Solution(int n) {
        bool a[n][n+1];
        return sizeof(a)>>1;
    }
};

发表于 2015-12-05 14:56:41 回复(88)
Java
牛客79631828号头像 牛客79631828号 
public class Solution {
    public int Sum_Solution(int n) {
        n = n == 1 ? 1 : n + Sum_Solution(n-1);
        return n;
    }
}

发表于 2022-01-09 22:51:53 回复(0)
Java
sososostrong头像 sososostrong
方法一：牛客官方的变形递归法
方法二：数学对数法 
public class Solution {
    public int Sum_Solution(int n) {
        //数学对数原理：
        // log(a)+log(b) = log(a*b)
        //log(a)-logb = log(a/b)
        //所以log(ret)= log((1+n)*n/2)
        //通过等号两边同时去掉对数取得ret，并消除误差即可
        //假设log(a,N)表示底数为a,真数为N的对数，则a^log(a,N) = N
        //所以ret = 10^log(10,N) = 10^log10(N) = N
        double a = Math.log10(1+n) + Math.log10(n);
        double b = Math.log10(2);
        int ret = (int)(Math.pow(10,a-b)+0.5);//可通过四舍五入消除误差
        return ret;
    }
}


发表于 2020-10-27 21:16:49 回复(0)
董的人自然懂头像 董的人自然懂
static int sn;
static int ssum;
class temp
{
public:
    temp()
    {
        sn++;
        ssum = ssum+sn;
    }
 
 
};
classSolution {
public:
    intSum_Solution(intn) {
           sn=0;
        ssum=0;
        temp *t=new temp[n];
       delete[] t;
 
        return ssum;
    }
};
编辑于 2015-10-04 23:38:37 回复(3)
Java
QAQWQAQ头像 QAQWQAQ 
    public int Sum_Solution(int n) {
        return n + n * (n-1) / 2;
    }

发表于 2021-08-24 17:55:15 回复(0)
Python 3
来个offer叭！头像 来个offer叭！ 
# 递归
class Solution:
    def Sum_Solution(self , n: int) -> int:
        if n == 1:
            return 1
        sum = n
        sum += self.Sum_Solution(n-1)
        return sum

发表于 2022-07-20 23:33:22 回复(0)
C++
Noah.Suming头像 Noah.Suming 
静态变量C++
class Temp {
public:
    static int sum;
    static int s;
    Temp() {
        ++s;
        sum += s;
    }
};

int Temp::sum = 0;
int Temp::s = 0;
class Solution {
public:
    int Sum_Solution(int n) {
        vector<Temp> tmp(n);
        int res = Temp::sum;
        Temp::sum = 0;
        Temp::s = 0;
        return res;
    }
};

返回数组的大小/2 
class Solution {
public:
    int Sum_Solution(int n) {
        bool res[n][n+1];
        return sizeof(res) >> 1;
    }
};




发表于 2022-02-06 17:06:13 回复(0)
Java
624huiguorou头像 624huiguorou
/*
用递归。
    
声明sum与n分开，避免混乱。
用boolean类型的中间变量，使用&&的短路规则，进行递归结束。
*/ 
    /*
    用递归。
    
    声明sum与n分开，避免混乱。
    用boolean类型的中间变量，使用&&的短路规则，进行递归结束。
    */
    public int Sum_Solution(int n) {
        //声明sum与n分开，避免混乱
        int sum = n;
        //用boolean类型的中间变量，使用&&的短路规则，进行递归结束
        boolean flag = (n > 0) && ((sum += Sum_Solution(n-1)) > 1);
        return sum;
    }


发表于 2021-08-31 17:57:12 回复(1)
Python 3
xlxcc头像 xlxcc
python 版本
整体思路是使用递归求解：f(n) = n + f(n-1)
关键在于如何停止递归，思想如下：
当n > 0时，对n取两次非为True；当n == 0时，对n取两次非为False。
由于不能使用if判断，因此将递归函数和终止函数分开写，并使用数组保存，然后将上面对n的判断结果作为数组下标来选择使用哪个函数。
整体代码如下： 
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.choice = ['Solution().StopCur(n-1)', 'Solution().Sum_Solution(n-1)']
        
    def Sum_Solution(self, n):
        # write code here
        return n + eval(self.choice[not not n])
    
    def StopCur(self, n):
        return 0


发表于 2021-08-25 17:47:32 回复(0)
小小小牛客1124头像 小小小牛客1124

虽然说不能使用乘法，但是可以自己实现乘法

只要从两位相乘开始实现，就能指数级地实现4，8，16，32位的乘法。
函数multi_4以上的基本就是复制粘贴下就行了
有了乘法就能使用求和公式了，最后记得除以2（右移1位） 
class Solution {
public:
    int Sum_Solution(int n) {
       int m=multi_32(n,n+1,0)>>1;
       return m;
    }
    
    int multi_2(int a,int b,int start){
        //const int MASK=0x00000003<<start;
        const int MASK_1BIT=0x00000001<<start;
        
        int sum=0;
        const int a1=a &  (MASK_1BIT<<1);
        const int a2=a &  MASK_1BIT;
        const int b1=b &  (MASK_1BIT<<1);
        const int b2=b &  MASK_1BIT;
        
        sum=(a1&b1)<<(start+1) ;
        sum+=(a2&b2)<<start;
        sum+= ( ( a2&(b1>>1) )+( (a1>>1)&b2)  )<< (start+1);
        return sum;
        
    }
    
    int multi_4(int a,int b,int shift){
       // const int MASK=0x0000000f<<shift;
        const int MASK_2BIT=0x00000003<<shift;
        
        const int a1=a&(MASK_2BIT<<2);
        const int a2=a&MASK_2BIT;
        const int b1=b&(MASK_2BIT<<2);
        const int b2=b&MASK_2BIT;
        
        int sum;
        sum=multi_2(a1, b1, shift+2);
        sum+=multi_2(a2, b2, shift);
        sum+=multi_2(a1>>2, b2, shift)<<2;
        sum+=multi_2(a2, b1>>2, shift)<<2;
        
        return sum;
    }
    
    int multi_8(int a,int b,int shift){
        const int MASK_4BIT=0x0000000f<<shift;
        
        const int a1=a&(MASK_4BIT<<4);
        const int a2=a&MASK_4BIT;
        const int b1=b&(MASK_4BIT<<4);
        const int b2=b&MASK_4BIT;
        
        int sum;
        sum=multi_4(a1, b1, shift+4);
        sum+=multi_4(a2, b2, shift);
        sum+=multi_4(a1>>4, b2, shift)<<4;
        sum+=multi_4(a2, b1>>4, shift)<<4;
        
        return sum;
    }
    
    int multi_16(int a,int b,int shift){
        const int MASK_8BIT=0x000000ff<<shift;
        
        const int a1=a&(MASK_8BIT<<8);
        const int a2=a&MASK_8BIT;
        const int b1=b&(MASK_8BIT<<8);
        const int b2=b&MASK_8BIT;
        
        int sum;
        sum=multi_8(a1, b1, shift+8);
        sum+=multi_8(a2, b2, shift);
        sum+=multi_8(a1>>8, b2, shift)<<8;
        sum+=multi_8(a2, b1>>8, shift)<<8;
        
        return sum;
    }
    
    int multi_32(int a,int b,const int shift){
        const int MASK_16BIT=0x000000ff<<shift;
        
        const int a1=a&(MASK_16BIT<<16);
        const int a2=a&MASK_16BIT;
        const int b1=b&(MASK_16BIT<<16);
        const int b2=b&MASK_16BIT;
        
        int sum;
        sum=multi_16(a1, b1, shift+16);
        sum+=multi_16(a2, b2, shift);
        sum+=multi_16(a1>>16, b2, shift)<<16;
        sum+=multi_16(a2, b1>>16, shift)<<16;
        
        return sum;
    }
};


编辑于 2021-03-22 12:49:54 回复(0)
提交观点

问题信息

基础数学
难度：
1088条回答 132411浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号