首页 > 试题广场 >

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

[编程题]求1+2+3+...+n

热度指数：370073 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围： $0 < n \le 200$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

推荐

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

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

利用逻辑与短路特性

# -*- 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.

class Solution {

public:

int Sum_Solution(int n) {

return ((int)pow(n,2) + n) >> 1;

}

};

发表于 2015-09-09 20:53:09 回复(1)

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)

ML3426

利用逻辑操作的短路性质

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)

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

解题思路：
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冲

用公式是不可以的，公式里有乘法！！实现乘法可以用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号

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

方法一：牛客官方的变形递归法

方法二：数学对数法

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)

C/C++

代码呀代码

class Solution
{
  public:
    int Sum_Solution(int n) 
    {
       if( n < 0)
           return 0;
        else
           return n + Sum_Solution(n-1);  
    }
};

利用递归可以达到要求

编辑于 2019-10-31 09:46:42 回复(0)

打工不可能打工的

public class Solution {
    public int Sum_Solution(int n) {
        return (n + ((int)(Math.pow(n, 2) - n) >> 1));
    }
}

发表于 2018-08-11 02:04:56 回复(1)

董的人自然懂

  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

    public int Sum_Solution(int n) {
        return n + n * (n-1) / 2;
    }

发表于 2021-08-24 17:55:15 回复(0)

Python 3

来个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

静态变量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)

提交观点

问题信息

基础数学

难度：

1083条回答 2475收藏 130068浏览

通过挑战的用户

查看代码

Elastic...

2023-02-25 22:19:40
郁闷的马里奥风度翩翩

2023-02-20 19:38:23
Dice_L

2022-12-16 10:17:06
幻影20181...

2022-11-11 10:30:59
干脆面la

2022-10-18 10:36:06

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

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题