本篇文章介紹一下使用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求最大奇約數的和的詳細內容。更多資訊請關注PHP中文網其他相關文章!