Question

pascal题

四、猫猫的小鱼
（catfish.pas/cpp/c）
【问题描述】
猫猫是丛林里很多动物心中的天使，她为此十分自豪。猫猫最爱吃鱼了，她每天都要去池塘钓鱼吃。猫猫经常吃鱼脑，数学特别强，然而，小女生的性格决定了她的贪玩。
一天，猫猫钓到了很多条鱼。她并不想马上就把可怜的鱼儿吃掉，而是先折磨够之后再吃（有句话叫什么来着～最毒不过猫猫心）。
猫猫将这很多很多（数不过来）条鱼按照外观的漂亮程度排序，每个鱼的编号依次为1、2、3……N，第i条鱼的美观程度为3(i-1)。
猫猫要把这些鱼放到桶里去。她每次拿的鱼的数目是任意的。中的鱼的“总美观程度”为各条鱼美观程度之和。例如：猫猫这一次拿了第一条鱼和第三条鱼，那么美观程度为1+9=10。
猫猫想知道，她可以获得的第k大的“总美观程度”是多少。
从文件中读入k，输出猫猫能够获得的，第k大的“总美观程度”。
输入数据：
输入文件catfish.in包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。
输出数据：
输出文件catfish.out包含n行，每行输出一个对应的结果。
输入样例1：
1
7
输出样例2：
13
样例说明：
猫猫能够拿到的美观程度从小到大为1、3、4、9、10、12、13……所以第7大的美观程度是13。
对于50%的输入文件，有k≤5000。
对于100%的输入文件，有k≤231-1。

Answer 1

我的想法是：因为鱼的美观程度都是3的整数次幂，所以可用三进制表示法。如：取第一条鱼可表示为1，取第三条可表示为100，取第一、二、三条可表示为111。显然，由于每条鱼都有其各自的美观程度，美观程度的总和的三进制表示中只可能出现0和1，不可能有2。这样，也就是要求出一个三进制的递增数列，且每一个数中都不含数字2。
由此，我想到二进制，于是立刻得出算法。先把k转换成二进制，再把这个二进制数当成三进制数，还原为十进制数，这就是最后结果。
比如当k=7时，二进制形式为111，把它看成三进制数，计算它的值：
1*3^2+1*3^1+1*3^0=9+3+1=13。

program catfish;
var
infile,outfile:text;
jg,k,q,n,i:longint;
begin
assign(infile,'catfish.in.txt');
reset(infile);
assign(outfile,'catfish.out.txt');
rewrite(outfile);
read(infile,n);
for q:=1 to n do begin
read(infile,k);
jg:=0;
while k>0 do begin
for i:=0 to 30 do
if (trunc(exp(i*ln(2)))<=k) and (trunc(exp((i+1)*ln(2)))>k) then begin
k:=k-trunc(exp(i*ln(2)));
jg:=jg+trunc(exp(i*ln(3)));
break;
end;
end;
writeln(outfile,jg);
end;
close(infile);
close(outfile);
end.