2017年网易校招算法编程题：数论 (PHP版)

野性酷女 2022-06-14 05:20 226阅读 0赞

小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数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

小易计算这个问题遇到了困难，需要你来设计一个[算法][Link 1]帮助他。(来自网易算法面试题)

<?php
        function f($n){
            if($n%2 != 0){//奇数
                return $n;
            }elseif($n%3 == 0 && $n%2 == 0){//能被3整除，也能被2整除的偶数
                return 3;
            }elseif((!strpos(sqrt($n),'.')) || !strpos(sqrt($n/2),'.')){//可以开方的偶数
                return 1;
            }else{
                return $n/2;
            }
        }
        echo f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7).'<br>';
        echo f(16)."<br>";
        echo f(15)."<br>";
        echo f(14)."<br>";
        echo f(13)."<br>";
        echo f(12)."<br>";
        echo f(11)."<br>";
        echo f(10)."<br>";
        echo f(9)."<br>";
        echo f(8)."<br>";
        echo f(7)."<br>";
        echo f(6)."<br>";
        echo f(5)."<br>";
        echo f(4)."<br>";
        echo f(3)."<br>";
        echo f(2)."<br>";
        echo f(1)."<br>";
        echo f(210);
    ?>

结果如下所示:

21  
1  
15  
7  
13  
3  
11  
5  
9  
1  
7  
3  
5  
1  
3  
1  
1  
3

注:该算法还不是最简便的高效算法，希望各位指点啊！

[Link 1]: http://lib.csdn.net/base/datastructure

发表评论取消回复

表情：

评论列表（有 0 条评论，226人围观）

还没有评论，来说两句吧...

相关阅读

相关 2017年网易校招算法编程题：优雅的点（PHP版）

题目如下: 小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他

￡神魔★判官ぃ/ 2022年06月14日 05:21/ 0 赞/ 297 阅读

相关 2017年网易校招算法编程题：数论 (PHP版)

小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题：定义函数f(x)为x最大的奇数约数，x为正整数。例如:f(44) = 11. 现在给出

野性酷女/ 2022年06月14日 05:20/ 0 赞/ 227 阅读

相关搜狐2017校招编程题

题目1 输出序列题通过率为100% include <iostream> include <string> include <sstream

桃扇骨/ 2022年06月09日 05:25/ 0 赞/ 216 阅读

相关 2017校招真题网易藏宝图

题目描述牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t

分手后的思念是犯贱/ 2022年05月24日 06:09/ 0 赞/ 220 阅读

相关 2017校招真题网易星际穿越

题目描述航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中

朴灿烈づ我的快乐病毒、/ 2022年05月24日 06:08/ 0 赞/ 228 阅读

相关 2017校招真题网易分苹果

题目描述 n 只奶牛坐在一排，每个奶牛拥有 a i 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到

超、凢脫俗/ 2022年05月24日 06:07/ 0 赞/ 260 阅读

相关 2017校招真题网易下厨房

题目描述牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。输入描述: 每个输入包含 1 个测试用例。每个测

- 日理万妓/ 2022年05月24日 01:23/ 0 赞/ 241 阅读

相关 2017校招真题网易地牢逃脱

题目描述给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x 0 , y 0 ) 位置出发，遍历这个地牢，和一般的

妖狐艹你老母/ 2022年05月24日 01:17/ 0 赞/ 228 阅读

相关 2017校招真题网易合唱团

题目描述有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能

- 日理万妓/ 2022年05月24日 00:15/ 0 赞/ 222 阅读

相关牛客网-2017校招真题-解救小易

题目描述有一片1000\1000的草地，小易初始站在(1,1)(最左上角的位置)。小易在每一秒会横向或者纵向移动到相邻的草地上吃草(小易不会走出边界)。大反派超超想去捕

ゞ浴缸里的玫瑰/ 2022年05月15日 00:27/ 0 赞/ 244 阅读