球弹跳高度的计算

题意

球从高度 $h$ 落下，每次反弹到上一高度一半。求第 10 次落地前总路程，以及第 10 次反弹高度。

思路

第一次只经过向下的 $h$ 。之后每次反弹高度既要上升又要下降，因此九个完整往返各加 2 * height；第十次落地后再折半一次得到第十次反弹高度。题面样例恰处于有效数字舍入边界，使用 Decimal 和半向上舍入匹配其 %g 输出。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from decimal import Decimal, ROUND_HALF_UP


def format_six_significant(value):
    if value == 0:
        return "0"
    quantum = Decimal(1).scaleb(value.adjusted() - 5)
    rounded = value.quantize(quantum, rounding=ROUND_HALF_UP)
    text = format(rounded, "f")
    return text.rstrip("0").rstrip(".") if "." in text else text


height = Decimal(input())
distance = height

for _ in range(9):
    height /= 2
    distance += 2 * height

height /= 2
print(format_six_significant(distance))
print(format_six_significant(height))

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#include <cstdio>
int main(){
    double h;
    scanf("%lf",&h);
    double sum = -h;
    double fang = 0;
    int i;
    for (i=1;i<=10;i++){
        sum += 2*h;
        h = h /2;
    }
    printf("%g\n",sum);
    printf("%g",h);
    return 0;
}

复杂度

循环次数固定为 9，时间复杂度和额外空间复杂度均为 $O(1)$ 。

总结

弹跳题要单独处理第一次下降和最后一次反弹，避免把往返次数多算或少算一次。

球弹跳高度的计算

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结