使用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的题。。

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

推荐学习：PHP视频教程

以上就是使用PHP求最大奇约数的和的详细内容，更多请关注其它相关文章！

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！