Question

Pascal中的问题，高手解答！

一球从n米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第k次落地时，共经过多少米？第k次反弹多高？（第0次则代表还没开始,反弹为0)

Answer 1

var k:longint
s,h,n:real;
begin
read(n,k);
if k=0 then begin writeln(0,' ',0);exit;end;
repeat
s:=s+n;
n:=n/2;
k:=k-1;
h:=n;
until k=0;
writeln(s,' ',h);
end.

Answer 2

var k,n,i:integer;
s,h:real;
begin
readln(n,k);
if k=0 then
s:=0
else
begin
s:=n;
h:=n;
for i:=2 to k do
begin
s:=s+h;
h:=h/2;
end;
end;
writeln(s:0:4);
readln;
end.

Answer 3

既然楼上已经有不错的解法了，我们就来讨论一下更快的做法吧。
题目意思其实是求n*((1/2)^k)
于是通过
(1/2)^i = (1/2^(i div 2))^2 （i为奇数） or (1/2^(i div 2-0.5))^2*1/2 （i为偶数）
可以分治得到效率为O(log2K)的做法，在k很大的情况下是不错的