求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
数据范围： 
进阶： 空间复杂度)
，时间复杂度 )
进阶： 空间复杂度
[编程题]求1+2+3+...+n
总结前面大牛们的方法，提供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
那么 a * b = (2^e0 + 2^e1 + 2^e2+...) * b
= b * 2^e0 + b * 2^e1 + b * 2^e2 + ...
= (b << e0) + (b << e1) + ....
接下来看代码：
= (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) + ....
= (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)
这题剑指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)
利用逻辑与短路特性
# -*- 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)
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) {
//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)
解题思路：
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)
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)
方法一：牛客官方的变形递归法
方法二：数学对数法
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++ 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)
/*
用递归。
声明sum与n分开，避免混乱。
用boolean类型的中间变量，使用&&的短路规则，进行递归结束。
用递归。
声明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 版本
整体思路是使用递归求解：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)
虽然说不能使用乘法，但是可以自己实现乘法
只要从两位相乘开始实现，就能指数级地实现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)
问题信息
难度：
1089条回答
2567收藏
133872浏览
通过挑战的用户
查看代码-
2023-02-25 22:19:40 -
2023-02-20 19:38:23
-
2022-12-16 10:17:06 -
2022-11-11 10:30:59
-
2022-10-18 10:36:06
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Solution { public: int Sum_Solution(int n) { int ans = n; ans && (ans += Sum_Solution(n - 1)); return ans; } };