描述

题目描述

假设一个球从任意高度自由落下，每次落地后反跳回原高度的一半; 再落下, 求它在第5次落地时，共经历多少米?第5次反弹多高？

最后的误差判断是小数点6位

示例

输入：
1
输出：
2.875
0.03125

知识点：数学推理，递推，模拟

难度：⭐⭐⭐

题解

方法一：递推法

image-20211104191706677

算法流程：

  • 维护几个变量用来保存每次反弹的状态
    • distance：起点到第一次落地反弹前的路程
    • fhigh：第 i 次反弹后球能到的高度
  • 从第一次反弹到第 count - 1 次反弹进行循环处理
    • 每次反弹后，fhigh 为反弹前高度的一半：fhigh = fhigh / 2
    • 上一次反弹开始到下一次反弹之间走过的路程 distance += (fhigh * 2);

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int high = scanner.nextInt();
        	solution(high, 5);
        	System.out.println(distance);
        	System.out.println(height);
        }
    }

    private static double distance = 0;
    private static double height = 0;

    private static void solution(int high, int count) {
    	double fhigh = high;
		// 起点到第一次落地反弹前的路程
		distance += fhigh;
		// 总共循环处理(count - 1)次
    	for(int i = 1; i < count; i++) {
    		// 第i次反弹后球能到的高度
    		fhigh = fhigh / 2;
    		// 上一次反弹开始到下一次反弹之间走过的路程
    		distance += (fhigh * 2);
    		// 只需要计算倒数第二次反弹后的高度除以2，表示最后一次反弹后能到达的高度 
    		if(i == count - 1) {
	    		height = fhigh / 2;
    		}
    	}
    }
}

复杂度分析：

时间复杂度：O(N)O(N)，平均需要循环遍历 N 次，N为输入的高度

空间复杂度：O(1)O(1)，只用到了常量空间的变量来保存几个状态

方法二：数学推理+找规律

解题思路：

一两个简单的例子就能推算出规律

算法流程：

  • 假设输入的高度为 h

  • 对于第5次反弹的高度：

    • 每次弹起高度是原来的1/2，假设第5次弹起高度是h，2的5次幂就是32，也就是说初始高度应该是32h，反过来第五次输入 h/32

  • 对于走过的路程：

    • 第1次落地的经过的距离为h1 = h 第2次落地的经过的距离为h2 = h1 + (1/2^1) * 2 * h 第3次落地的经过的距离为h3 = h2 + (1/2^2) * 2 * h

      第4次落地的经过的距离为h4 = h3 + (1/2^3) * 2 * h

      第5次落地的经过的距离为h5 = h4 + (1/2^4) * 2 * h

    • 根据规律可知，第n次反弹经历的路程 h(n) = h(n-1) + (1 / 2^(n-1)) * 2 * h，而这种递推思想可以通过循环遍历来实现

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int high = scanner.nextInt();
        	solution(high, 5);
        	System.out.println(distance);
        	System.out.println(height);
        }
    }

    private static double distance = 0;
    private static double height = 0;

    private static void solution(int high, int count) {
    	double fhigh = high;
		// 起点到第一次落地反弹前的路程
    	distance = fhigh;
		// 总共循环处理(count - 1)次
    	for(int i = 2; i <= count; i++) {
    		// 公式实现：a[i] = a[i-1] + ((1 / 2^(i-1)) * h * 2)  
    		distance += ((1 / Math.pow(2, i-1)) * 2 * fhigh);
    	}
    	// 根据规律可得到第5次反弹的高度
    	height = fhigh / 32;
    }
}

复杂度分析：

时间复杂度：O(N)O(N)，需要循环遍历 count - 1 次，N为高度

空间复杂度：O(1)O(1)，只用到常量