题解 | #小球的距离#

class Balls {
public: 
    int calcDistance(int A, int B, int C, int D) {
        // write code here
        return 3*(A+B+C+D);
    }
};

/**
    假设初始高度为 X,则第一次落地经历距离为X; 反跳回高度为 X/2, 因此第二次落地经历距离为 X/2(此时没有考虑跳回经历的距离), 
    第三次为 X/2 的 1/2, 既X/4,每下一次都是上一次的1/2,一般会由此想到等比数列,公比q=1/2
    假设需要n次该小球不再弹起, 第一次 A1=X*q^1-1=X, A2=A1*q^(2-1)=A1*q=A1*1/2, A3=A1*q^(3-1) 
    则最后一次经历的距离为 An=A1*q^(n-1)
    题目要求可认为该等比数列在n趋于正无穷大时的和:
    Sn=A1+A2+A3+...+An
    (1) Sn=A1+A1*q^1+A1*q^2+...+A1*q^(n-1)
        给(1)式等号左右俩边同时乘 公比q 得(2)式:
    (2) q*Sn=A1*q+A1*q^1+A1*q^2+...+A1*q^n
             
    使用(1)式 减 (2)式 的(3)式:
    Sn-q*Sn=A1-A1*q^n 化简
    (1-q)Sn=A1(1-q^n)
    Sn=A1(1-q^n) / (1-q)
    当n趋于正无穷大时 limt(n->+)q^n ~= 0(q<1)
    因此上式 Sn=A1 / (1-q)
    当A1=X,q=1/2时: Sn=2*X
    
    该题还应该考虑每次反跳的X/2都会经历俩次(回跳一次,然后再落地又一次),除了第一次,之后每次都是俩倍距离,如下图
    ============================================================================================
    首次
    下落
     ↓|
     ↓|
     ↓|   第1次回跳
     ↓|    后再下落
     ↓|   ↑| ↓|   第2次回跳
     ↓|   ↑| ↓|   后再下落 第3次回跳
     ↓|   ↑| ↓|   ↑| ↓|    后再下落
     ↓|   ↑| ↓|   ↑| ↓|   ↑| ↓|............
    ============================================================================================
    因此重写和公式:
    Sn=A1 + 2*A1*q + 2*A1*q^2 + ... + 2*A1*q^(n-1)
        Sn=A1(1 + 2q + 2q^2 + ... + 2*q^(n-1))
    
    q*Sn=A1*q + 2*A1*q^2 + ... + 2*A1*q^n
    (1-q)Sn=A1 + A1*q - 2*A1*q^n
    Sn=(A1 + A1*q - 2*A1*q^n) / (1-q)
    Sn=A1*(1 + q - 2*q^n) / (1-q)
        limt(n->+)q^n ~= 0(q<1)
    Sn=A1*(1 + 1/2 - 2 * 0) / (1/2)
    Sn=3A1, 由此得出一个球的经历距离为3A;
*/