面试题：小球落下求路径长度

问题描述

小球从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