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

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

保举学习：PHP视频教程

以上就是应用PHP求最年夜奇约数的以及的具体内容，更多请存眷资源魔其它相干文章！