不是VIP会员,不能显示答案

题目解答

题目:
var
data : array[1..20] of integer;
n,i,h,ans: integer;

procedure merge;
begin
data[h-1] := data[h-1] + data[h];
dec(h);
inc(ans);
end;

begin
readln(n);
h := 1;
data[h] := 1;
ans := 0;
for i:=2 to n do
begin
inc(h);
data[h] := 1;
while (h>1) and (data[h]=data[h-1]) do
merge;
end;
writeln(ans);
end.

(1)
输入:8
(2)
输入:2012
输出:7 2004
考点: 0
分析:
解答: 本题是统计合并的次数,合并的过程过程执行一次便统计一次。合并的条件是data[h]=data[h-1],试验十几个数据后归纳出最后data数组里的数据是:1024,512,256,128,64,16,8,4。即:2012=1024+512+256+128+64+16+8+4,即最终的结果是将输入的一个数通过归并的方式拆分为若干个2的整数次方的和,而2^m需要2^m-1次合并,所以最终的结果为1023+511+255+127+63+15+7+3=2004
做加法还不够快,只要看最后h的值,结果为n-h。h的值其实是输入的n转化为相应的二制数中1的个数,如2012(10)=1111101100(2),共8位1,所以结果为2012-8=2004。
评论:
老师: 0