to:天空还下着沙
正确的答案上面已经有了
to:落落 / chn2k
在这里我们首先要认识一个问题:我们要获得的只是一个具有通用性的公式,
即是对于不同数量的球都具有适用性的算法。而不是一个即具有通用性,又
能够实现最优方案的算法公式。事实上,由于球数的不同,实现最优方案的
算法可能各不相同,象这样含盖所有最优算法的公式可能根本不存在,举一
个最简单的例子,像落落提供的算法,(虽然我还没有看完。。)不需要代
入20000,只要代入12,便可以得到最后的答案肯定大于3。那是因为数学归
纳法所使用的公式是一个易于理解和操作的公式,一个这样的公式是不可能
号称“世界上目前最好的智力题目”的。
在这里我介绍一下我的思路:
首先我们需要知道在K个球的情况下,当K小于某个值的时候,称重次数N是
可以被确定下来的。即当K无限大时,每一组称重(一组是固定的次数1次或
2次或更多次的称重)都会排除一部分正常球,而当K缩小到某一个值之内时,
可以知道剩下还需要称几次。在这里,我假设K的最终值为3,则N=2,不需要
附加条件。
有了最终值,接下来讨论当K>=4的情况。我采用4分法方式。将K个球等分为4
份,若有余数M,则M必为(3,2,1,0)。算法是将4份中取任意两份称重,
若不相等,则坏球必在这两份中,若相等,则再称另外两组,判定坏球是否在
另外两组中,若还是相等,则坏球在余数中。
于是我们得到每一组称重最多要2次,当球数为K(K>=3),每组称重后的剩余
球数是K=(K-(K mod 4))/2,因为我们要获得的是最多需要几次称重,所以
要讨论运气最坏的情况,在K<=3之前,计算始终不会进入余数分支中。
余数分支的计算非常简单:当K=3则N=2,K=2 N=1,K=1 N=0,K=0 N无解(全是
正常球)
这样使用数学归纳法能够很快得到计算方法。我写了个函数实现这个算法:
Function do
itplease(k:interger,N:interger):Boolean;
//K为球数,N为称重数
begin
N:=0;
if (k<=3) then
begin
case k of
0:N:=-1;
1:N:=-1;
2:N:=-1;
3:N:=2;
end;
end;
while not(k<=3) do
begin
k:=(k-(k mod 4))/2
N:=N+2;
end;
case k of
0:N:=-1;
1:N:=N;
2:N:=N+1;
3:N:=N+2;
end;
end;