主题：求助啊，题目也忒BT了！！
ypyybbo
[专家分：30] 发布于 2007-10-09 23:07:00
一进制奶牛计数(ONE)
提交文件名：ONE.PAS
问题描述：
众所周知，奶牛们没有手指，因此，很遗憾他们不能使用十进制计数。他们采用的是一种称为“一进制”的计数表示方法。
这种计数方法包含：数字“1”，加号，减号，乘号和一些括号。这样的计数方法可以表示任何正整数。例如，22 = 1+1 + ((1+1+1+1) * (1+1+1+1+1))，用了11个1来表示22，因此，该表达式的UCC长度就是11。
而另一种表示22的计数方法如下：1 + (1+1+1) * (1+(1+1)*(1+1+1))，这个表达式的UCC长度是10（因为用了10个1来表示22）。而且，没有其他UCC长度更短的表达式能表示22了。
奶牛总是懒惰的，因此，他们总是在寻找一种简洁的表达式来表示正整数。请你编写程序，对给定的正整数，告诉奶牛们用“一进制”的表达式来表示该正整数，最短的UCC长度是多少。
输入文件（ONE.IN）：
输入数据有多个，每个只有一行，一个正整数N（1≤N≤2,000,000）。
输出文件（ONE.OUT）：
对应每个输入，输出每行一个整数，为表示N的最短UCC长度是多少。
输入输出样例：
ONE.IN
22
10
ONE.OUT
10
7
回复列表 （共7个回复）
沙发
angwuy [专家分：2280] 发布于 2007-10-11 20:55:00
用数学方法算也忒简单了
var n,t:integer;
begin
t:=0;
readln(n);
while n>3 do
begin
inc(t,3+n mod 3);
n:=n div 3;
end;
if n=1 then n:=0;
writeln(t+n);
end.
板凳
ypyybbo [专家分：30] 发布于 2007-10-13 12:03:00
算你强，不要学我
怀疑你的质量！！！[em6]
3 楼
shisutianxia [专家分：630] 发布于 2007-10-14 12:17:00
好像出错了，输入100，答案15，实际14,不过ANGWUY的算法思想的确很棒！！！！我一时绝对想不到
4 楼
Matodied [专家分：7560] 发布于 2007-10-14 13:51:00
我来解释一下angwuy的算法：
angwuy是把n分解3的因数，比如10是这样表示的：
(1 + 1 + 1) * (1 + 1 + 1) + 1。
为什么分解3的因数呢？因为3只能用3个1表示。
但是到26的时候好像就有点不对劲了，
angwuy的程序的答案是：
(1 + 1 + 1) * ((1 + 1 + 1) * (1 + 1) + 1 + 1) + 1 + 1
UCC长度是12，
而
(1 + 1 + 1) * (1 + 1 + 1) * (1 + 1 + 1) - 1
UCC长度是10。
angwuy可能没考虑减法吧！
5 楼
shisutianxia [专家分：630] 发布于 2007-10-14 13:57:00
我用笨方法做，大家看看可以怎么改进`
program nainu;
var t,n:integer;p:boolean;
begin
writeln('n=?');
readln(n);t:=0;
while(n>2) do
if n mod 2=0 then begin
t:=t+2;n:=n div 2;
end
else begin n:=n-1;t:=t+1;end;
write('min=',t+n);
end.
6 楼
angwuy [专家分：2280] 发布于 2007-10-14 18:30:00
好象确实漏了减法,更正后:
function min(a,b:integer):integer;
begin
if a>b then min:=b else min:=a;
end;
function fun(n:integer):integer;
begin
if n=1 then fun:=0
else if n=2 then fun:=2
else if n=3 then fun:=3
else if n mod 3=0 then fun:=3+fun(n div 3)
else if n mod 3=1 then fun:=min(fun(n div 3)+1,fun(n div 3+1)+2)+3
else if n mod 3=2 then fun:=min(fun(n div 3)+2,fun(n div 3+1)+1)+3;
end;
var n:integer;
begin
while not eof do
begin
readln(n);
writeln(fun(n));
end;
end.
7 楼
snoopy7 [专家分：70] 发布于 2007-10-20 20:58:00
上面的还是不对！
program ss;
var i,x,y:integer;
begin
read(x);
if x mod 9<> 0 then
begin
i:=0;
while(x>2) do
if x mod 2=0 then begin
i:=i+2;x:=x div 2;
end
else begin
x:=x-1;i:=i+1;end;
write('min=',i+x);end
else begin
i:=0;
while(x>3) do
if x mod 3=0 then begin
i:=i+3;x:=x div 3;
end
else begin x:=x-x mod 3;i:=i+x mod 3; end;
write('min=',i+x); end;
end.
[em9][em9]
我来回复
您所在位置：