使用PHP求最大奇约数的和

使用PHP求最大奇约数的和,第1张

概述使用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(@R_301_6345@s(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的题。。

本文转载自:https://blog.csdn.net/qq_28602957/article/details/77914402

推荐学习:PHP视频教程 总结

以上是内存溢出为你收集整理的使用PHP求最大奇约数的和全部内容,希望文章能够帮你解决使用PHP求最大奇约数的和所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/1164821.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-01
下一篇 2022-06-01

发表评论

登录后才能评论

评论列表(0条)

保存