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

8830

发布于 2018-09-20 11:31:56

文章被收录于专栏：JavaEdge

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 删除

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

java

登录后参与评论

0 条评论

热度