本篇文章介绍一下使用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

小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。

1. <?php 
2.  
3. $num = trim(fgets(STDIN)); 
4.  
5.  
6.  
7. function jNum($num){ 
8.  
9.         $m = $num/2; 
10.  
11.         $res = 1; 
12.  
13.         if($num&0x1 == 1){//如果他本身就是个奇数，那么他的最大奇约数就是他本身 
14.  
15.                 $res = $num; 
16.  
17.                 goto HELL; 
18.  
19.         } 
20.  
21.         for($i = 1; $i<=$m; $i=$i+2){//如果不是，那么就从1开始一直往上除，每次+2（奇数） 
22.  
23.                 if($num%$i==0){ 
24.  
25.                         $res = $i; 
26.  
27.                 } 
28.  
29.         } 
30.  
31.         HELL: 
32.  
33.         return $res; 
34.  
35. } 
36.  
37.  
38.  
39. function jNum2($num) 
40.  
41. { 
42.  
43.         $res = 0; 
44.  
45.  
46.  
47.         for($i=1;$i<=$num;$i++){ 
48.  
49.                 if(($i&0x1) == 1){//如果他本身就是个奇数，那么他的最大奇约数就是他本身 
50.  
51.                         $res+=$i; 
52.  
53.                 }else{ 
54.  
55.                         $n = $i; 
56.  
57.                         while(true){//优化，从最大的数开始往下除 
58.  
59.                                 $n = $n>>1; 
60.  
61.                                 if(($n&0x1) == 1){ 
62.  
63.                                         $res+=$n; 
64.  
65.                                         break; 
66.  
67.                                 } 
68.  
69.                         } 
70.  
71.                 } 
72.  
73.         } 
74.  
75.  
76.  
77.         HELL: 
78.  
79.         return $res; 
80.  
81. } 
82.  
83.  
84.  
85. function jNum3($num){//公式法 
86.  
87.         if($num == 1){ 
88.  
89.                 return 1; 
90.  
91.         } 
92.  
93.         if(($num&0x1) == 0){ 
94.  
95.                 return jNum3($num>>1)+$num*$num/4; 
96.  
97.         }else{ 
98.  
99.                 return jNum3($num-1)+$num; 
100.  
101.         } 
102.  
103.  
104.  
105. } 
106.  
107. //$sum = 0; 
108.  
109. //for($i = 1; $i<=$num; $i++){ 
110.  
111. //      $sum+=jNum($i); 
112.  
113. //} 
114.  
115. //echo $sum; 
116.  
117. //echo jNum2($num); 
118.  
119. 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

Tags: PHP求最大奇约数的和

分享到：