文章目录
  1. 1. 整数圆边点问题
  2. 2. 函数求和问题

  前些天同学参加网易校招,在线答题,前面是选择题,后面是编程题。编程题一共三道,第一道很简单,所以直接跳过。后面两道题目比较有意思,我虽然没有报名参加网易的校招,但是不妨碍我们拿出来说道说道。

整数圆边点问题

  (我自己瞎起的名字)

  题目:大意是给定一个以坐标轴原点为圆心指定半径长度的圆,求该圆上所有X/Y坐标均为整数的点的个数。

  输入:圆半径的平方

  输出:符合要求的点的个数

  分析:

  这道题目其实是一道更难的题目的简化版,那道更难的题目是圆心未固定,圆心也是输入的,由于圆心是变化的,所以处理起来略微复杂一下,需要用两个圆弧进行交叉过滤掉无需验证的数据。言归正传,对于本题,最直观也最简单的测量就是穷举法。最基本的思路是遍历所有的能囊括整个给定圆的最小正方形中的所有整数点,这样也是最笨的方法。

  稍微观察一下就会发现,其实这些个点是对称的,即第一象限的点和第三象限的点是轴对称的,第二和第四象限类似。那么,问题可以简化为找到第一象限中的点,然后乘以四就可以了。但是,这里要小心,圆与坐标轴相交的四个点是比较特殊的,扫描的时候需要分情况讨论。但其实也可以限定扫描范围,扫描的时候先不扫描这四个点,然后单独检测与X轴正方向相交的点,如果满足则四个点全满足条件,否则全不满足。

  关于如何扫描,我们只扫描第一象限内点,从左到右、从右到左、从上到下、从下到上你爱怎么扫就怎么扫,这个没什么影响。我是从左到右,扫描的范围是从(1,1)到(floor(r),floor(r)),其中r为圆的半径,而floor函数表示的是不大于r的最大整数。

  代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package wangyi;

public class IntCyclePointCount {
public static void main(String[] args) {
System.out.println(intCyclePointCout(5));
}
public static int intCyclePointCout(double r2) {
int count=0;
double r=Math.sqrt(r2);
int maxXY=(int) Math.floor(r);
//开始扫描
for(int i=1;i<=maxXY;i++){
for(int j=1;j<=maxXY;j++){
if ((i*i+j*j)==r2) {
count++;
}
}
}
//扫描完毕
count=4*count;
//检测额外的坐标轴交点
if (maxXY*maxXY==Math.floor(r2)) {
count+=4;
}
return count;
}
}

函数求和问题

  题目:定义函数f(n),如果x为奇数则f(n)=n,如果n为偶数,则f(n)=f(n/2),如f(28)=f(14)=f(7)=7。现输入m,求f(1)+f(2)+…+f(m)。

  输入:m

  输出:最后的结果和

  分析:

  最最最笨的方法是一个个算f(n),奇数直接输出,偶数的话不断除以二(位运算)直到遇到奇数输出,然后加起来,这种方法的时间复杂度是O(n!)的,一旦问题规模上去的话,即使单步运算优化到极致也无法避免计算时间的膨胀,显然是不可取的,事实也证明是不可取的(我同学一次次提交,一次次的timeout)。

  稍微聪明一点的方法是把之前计算的值存起来,一旦后续需要使用的话直接进行调用。例如计算出f(2)=1,那么把这个值存起来;计算到f(4)的时候,因为是偶数,需要进行除法,除了一次后为f(2),因为f(2)前一步已经计算并存储起来,那么可以直接拿出,即f(4)=1,再把f(4)的值也存起来;计算f(8)的时候也可利用到前面存的f(4),别的16、32等的计算与之类似。这么做使得后续的计算只需要进行一次的除法,即只需要回溯一次。这样总的时间复杂度变为了O(n)。但是这样也带来了额外存储空间的消耗,当问题规模超级超级大的时候(大过可以利用的存储空间时),同样也是不可取。可以对该方法进行略微的改进,即只记录前述若果步的结果,例如计算f(16)的计算只会需要用到f(8)而不需要变量小于8的结果值,那么可以丢弃掉f(2)和f(4)。具体的实现可以这么来,每次进行计算时进行一次回溯得到当前值的时候把被回溯的对象从额外存储中丢弃掉,即计算完f(4)的时候只存储f(4)而立即把f(2)释放掉,同理计算完f(8)后把f(4)释放掉。因为奇数是不参与前述回溯过程,无需进行考虑,上述优化只针对偶数而言,按照上述的策略实现了时间复杂度为O(n)、空间复杂度为O(1),这样的算法是略微可用的。

  难道就不能更进一步了吗?当然不是!还有更有趣的呢。解决这类问题的基本思路是递归迭代计算,最笨方法的递归迭代计算每一项即f(n)是不可取的,那么能否递归迭代计算最终的结果即多项的和s(n)呢?

  我们尝试一下进行推导,为了简化问题,我们假设s(n)=f(1)+f(2)+….+f(n);其中当n为奇数的时候f(n)=n,当n为偶数的时候f(n)=f(n/2),现求s(n)的表达公式或递推公式。

  先假设n为偶数,则

  s(n)=f(1)+f(2)+….+f(n)

    =(f(1)+f(3)+…+f(n-1))+(f(2)+f(4)+…+f(n))

    =(1+3+…+(n-1))+(f(1)+f(2)+….+f(n/2))

    =(1+n-1)*(n/2)/2+(s(n/2))

    =(n/2)^2+s(n/2)

  再讨论n为奇数的情况,则

  s(n)=f(1)+f(2)+….+f(n)

    =(f(1)+f(3)+…+f(n))+(f(2)+f(4)+…+f(n-1))

    =(1+n)*(n/2)/2+(f(1)+f(2)+…+f((n-1)/2))

    =(1+n)*n/4+s((n-1)/2)

  这样便得到了通项公式,但是这样还不够优雅是不是(有两种不同的情况)?怎么把他统一呢?这就要用到编程语言里的整除,利用整除的特殊性质,因为整除是向下取整,那么无论n为奇数还是偶数,公式全部可以统一为这样:

  s(n)=(n/2)^2+s(n/2)

  这样问题就变得很优雅简洁,直接递归实现该通项公式即可,几句话搞定,时空复杂度均为O(1),我就问你屌不屌,嘻嘻。

  talk is cheap, show me the fking code:

1
2
3
4
5
6
7
8
9
10
11
12
13
package wangyi;

public class GetSum {
public static void main(String[] args) {
System.out.println((int)getSum(520));
}
public static double getSum(int m){
if (m==1) {
return 1;
}
return (m/2)*(m/2)+getSum(m/2);
};
}
文章目录
  1. 1. 整数圆边点问题
  2. 2. 函数求和问题