您好,登錄后才能下訂單哦!
今天小編給大家分享的是PHP求最大奇約數(shù)和的方法示例,很多人都不太了解,今天小編為了讓大家更加了解PHP求最大奇約數(shù)和的方法,所以給大家總結(jié)了以下內(nèi)容,一起往下看吧。一定會(huì)有所收獲的哦。
小易是一個(gè)數(shù)論愛(ài)好者,并且對(duì)于一個(gè)數(shù)的奇數(shù)約數(shù)十分感興趣。一天小易遇到這樣一個(gè)問(wèn)題: 定義函數(shù)f(x)為x最大的奇數(shù)約數(shù),x為正整數(shù)。 例如:f(44) = 11.
現(xiàn)在給出一個(gè)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
小易計(jì)算這個(gè)問(wèn)題遇到了困難,需要你來(lái)設(shè)計(jì)一個(gè)算法幫助他。
<?php $num = trim(fgets(STDIN)); function jNum($num){ $m = $num/2; $res = 1; if($num&0x1 == 1){//如果他本身就是個(gè)奇數(shù),那么他的最大奇約數(shù)就是他本身 $res = $num; goto HELL; } for($i = 1; $i<=$m; $i=$i+2){//如果不是,那么就從1開(kāi)始一直往上除,每次+2(奇數(shù)) if($num%$i==0){ $res = $i; } } HELL: return $res; } function jNum2($num) { $res = 0; for($i=1;$i<=$num;$i++){ if(($i&0x1) == 1){//如果他本身就是個(gè)奇數(shù),那么他的最大奇約數(shù)就是他本身 $res+=$i; }else{ $n = $i; while(true){//優(yōu)化,從最大的數(shù)開(kāi)始往下除 $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);
開(kāi)始常規(guī)思路,一直調(diào)試的方法1,一直超時(shí),改為方法2,還是超時(shí),沒(méi)有什么本質(zhì)區(qū)別。
換思路。。
求sum(i)的過(guò)程中,如果i 為奇數(shù)可以直接求,就是 i 本身,即f(i) = i。
問(wèn)題就是求所有f(i), i為偶數(shù)的和。
因?yàn)槭亲畲笃婕s數(shù),所以f(2k) = f(k),所以f(2) + f(4) + … + f(2k) = f(1) + f(2) + … + f(k);
所以,數(shù)學(xué)歸納法,可以求出通用公式
這個(gè)做法還是不容易想到的。。。這么BT的題。。
以上就是PHP求最大奇約數(shù)和方法的簡(jiǎn)略介紹,當(dāng)然詳細(xì)使用上面的不同還得要大家自己使用過(guò)才領(lǐng)會(huì)。如果想了解更多,歡迎關(guān)注億速云行業(yè)資訊頻道哦!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。