2018-09-04Q:求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。方法一：递归实现1+2+..+n;
2018-09-04Q:求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。方法一：递归实现1+2+..+n;
JavaEdge
发布于 2018-09-20 11:31:56
发布于 2018-09-20 11:31:56
Q:求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
总结前面大牛们的方法，提供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.09.04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录