面试题:小球落下求路径长度
程序员文章站
2022-03-03 08:03:29
小球从n米落下,每次反弹上次高度的一半,问直到小球落地不动时,一共经过了多少米?...
问题描述
小球从n米落下,每次反弹上次高度的一半,问直到小球落地不动时,一共经过了多少米?
思路
预期说这是一道算法题,不如说是一道数学题或者思维题。
经过的路径的总长度为:
括号中的是一个等比数列求和问题,假设括号中的有m项,则上面这个式子可以写为:
(1/2)m的函数图像如图所示:
当m趋向无穷大时,(1/2)m趋向于0,最终结果为3n。即假设n为100,最后结果为300。
易错点
不能使用int或double类型去表示高度n,通过循环求sum。都会有损失。
public class Main {
public static void main(String args[]) {
int hight = 100;
System.out.println(calcLength(hight)); // 300
System.out.println(calcLength2(hight));// 197
System.out.println(calcLength3(hight));// 200.0
}
// 这个是正确答案
public static int calcLength(int n) {
return 3 * n;
}
// 这个是用int定义高度,可以跳出循环,但计算会有损失
public static int calcLength2(int n) {
int sum = 0;
while(n != 0) {
sum += n;
n /= 2;
}
return sum;
}
// 这个是用double定义高度,我原本以为无法跳出循环,其实是可以的,但是最后计算的结果也是会有损失
public static double calcLength3(double n) {
double sum = 0;
while(n != 0) {
sum += n;
n /= 2;
}
return sum;
}
}
本文地址:https://blog.csdn.net/realYuzhou/article/details/107700692