0%

二进制数表示

2012-1-16 星期一

刚开始,见到了题目,我就想到要用递归思想,因为2的n次冥中,多出用到了一对括号。

第一时间,我就疑问,例如:10=23+21,那么3和2是怎么的出来的呢?我想:把变量n以1,2,3,4的方式增加,直到2的n次方大于a(原数),那么n-1,a-2的n次方,以此类推,直到a=0。由于题目说只能出现2(2),2,2(0)这几个组合,所以就单独拿出来输出(那字符串顶替是为了调试更方便查看),当n>2是,递归cf(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
procedure cf(a:longint);

var
k,t:longint;

begin
repeat
// 一开始,我另外自定义函数进行乘方计算,但到了较大的数时,竟然超时,只好改变算法。

k:=1; t:=0;
while k<=a do begin t:=t+1; k:=k*2; end;
k:=k div 2; t:=t-1;
a:=a-k;

case t of
0:st:=st+'2(0)';
1:st:=st+'2';
2:st:=st+'2(2)';
else
begin
st:=st+'2(';
//我发现,最后时总舵了一个“)”,所以就在最后一层递归中不加括号。(s为计算递归层数)。
s:=s+1;
cf(t);
s:=s-1;
end;
end;

if (a=0) and (s=1) then exit;
if a=0 then st:=st+')' else st:=st+'+';
until a=0;
end;//递归过程

begin
s:=1; readln(a); cf(a); writeln(st);
end.//主程序
Thank you so much.