您好,登录后才能下订单哦!
今天小编给大家分享的是PHP求最大奇约数和的方法示例,很多人都不太了解,今天小编为了让大家更加了解PHP求最大奇约数和的方法,所以给大家总结了以下内容,一起往下看吧。一定会有所收获的哦。
小易是一个数论爱好者,并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题: 定义函数f(x)为x最大的奇数约数,x为正整数。 例如:f(44) = 11.
现在给出一个N,需要求出 f(1) + f(2) + f(3)…….f(N)
例如: N = 7
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21
小易计算这个问题遇到了困难,需要你来设计一个算法帮助他。
<?php $num = trim(fgets(STDIN)); function jNum($num){ $m = $num/2; $res = 1; if($num&0x1 == 1){//如果他本身就是个奇数,那么他的最大奇约数就是他本身 $res = $num; goto HELL; } for($i = 1; $i<=$m; $i=$i+2){//如果不是,那么就从1开始一直往上除,每次+2(奇数) if($num%$i==0){ $res = $i; } } HELL: return $res; } function jNum2($num) { $res = 0; for($i=1;$i<=$num;$i++){ if(($i&0x1) == 1){//如果他本身就是个奇数,那么他的最大奇约数就是他本身 $res+=$i; }else{ $n = $i; while(true){//优化,从最大的数开始往下除 $n = $n>>1; if(($n&0x1) == 1){ $res+=$n; break; } } } } HELL: return $res; } function jNum3($num){//公式法 if($num == 1){ return 1; } if(($num&0x1) == 0){ return jNum3($num>>1)+$num*$num/4; }else{ return jNum3($num-1)+$num; } } //$sum = 0; //for($i = 1; $i<=$num; $i++){ // $sum+=jNum($i); //} //echo $sum; //echo jNum2($num); echo jNum3($num);
开始常规思路,一直调试的方法1,一直超时,改为方法2,还是超时,没有什么本质区别。
换思路。。
求sum(i)的过程中,如果i 为奇数可以直接求,就是 i 本身,即f(i) = i。
问题就是求所有f(i), i为偶数的和。
因为是最大奇约数,所以f(2k) = f(k),所以f(2) + f(4) + … + f(2k) = f(1) + f(2) + … + f(k);
所以,数学归纳法,可以求出通用公式
这个做法还是不容易想到的。。。这么BT的题。。
以上就是PHP求最大奇约数和方法的简略介绍,当然详细使用上面的不同还得要大家自己使用过才领会。如果想了解更多,欢迎关注亿速云行业资讯频道哦!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。