做 ACM 的那些人应该也都知道传说中的“疯狂提交找错法”吧。就是如果你题目没有过的话，提交的罚时是不会在最后的分数里面扣掉的。当然是希望在尽量少的次数内过掉，但是情急之下，疯狂提交也是一个办法，不管怎么算它都是有好处的：

  • 如果最后题目 AC (Accept) 了，虽然罚时会让排名下降，但是不管罚时多少，多做出一道题的总比少做出一道题目的排名要靠前。
  • 如果题目没有 AC ，也并没有什么损失。

但是疯狂提交也必须要能“找错”，否则就没有什么意义了。今天我也非常疯狂地爽了一把，并且最后成功找到问题，把题目 AC 了。

其实我平时并不做 ACM ，因为我对存算法不太在行，而且我也特别讨厌 ACM 这种纯黑箱的形式，只告诉你正确或者错误，而得不到一点调试信息。但是仔细想想其实现实世界很多地方是这样的，比如许多商业软件，没有提供源代码，出错以后你也只能是茫然，再比如自己发布软件的时候，甚至连“对”或者“错”这样的单纯的结果都没有，你只能尽可能地去遇见和避免各种 Bug 和错误。所以其实做 ACM 的题目应当还是一个相当不错的锻炼吧。

但是数值分析这门课的几个作业是 ACM 形式的判题系统，所以还得去做。这次的题目并不难，就是代数方程求根，算法也在书上都讲过了。然而做出来的程序无论如何都是 Wrong Answer 。这四五天的空余时间几乎都在做这个题目，唉，做得郁闷到极点，怎么就能不对呢？我尝试了各种各样的方法，牛顿法、改进的牛顿法、二分法、Steffensen 方法，还把它们结合起来，修改各种优化参数……总之就是过不了。

最后我静下来仔细想了一下，如果测试数据里面的数据非常大的话，用 double 进行计算必定会溢出，那样肯定算不出结果来，但是我看到题目的状态显示有人确实通过了，所以测试数据应该不会特别大。不过令我郁闷的是我在使用二分法的时候竟然 TLE (Time Limit Exceeded) 了，那除非是一个很大的区间啊！

最后我决定用疯狂提交找错法了。我要探测测试数据！但是 OJ (Online Judger) 给出的结果种类非常少，包括 WA (Wrong Answer) 、TLE 和 Runtime Error SIGSEGV 等，根本不能从中得出测试数据，然而我们可以对测试数据（包括整个运行环境中的任何状态）进行一个 bool 测试并得到结果：结果就由 WA 和 SIGSEGV 两种状态来区分。于是我写了一个 helper 函数：

void fire_seg_fault(){ int *ip = 0; *ip = 0;}

原理很简单，就是要产生一个运行时错误， abort 函数不允许调用，除以零似乎也被忽略掉了，不过对 NULL 指针解引用是绝对会造成运行时错误的。然后在代码里面就可以对测试数据进行探测了，比如：

if (n > 1000) fire_seg_fault();

提交，然后根据结果是 WA (或者 TLE) 还是 SIGSEGV 来判断 n 的范围。然后逐次缩小范围，对于整数来说总是可以在比较可观的次数之内得到一个准确的值。对于浮点数来说，其实计算机里面的浮点数也不会是无限位的，所以从理论上来说也可以通过逐步缩小范围得到“精确”的值（也就是它给定的值）。

经过我疯狂探测，得出了测试数据的规模：

  • 一共有 14 组测试数据。
  • 有 a > b 的情况。(真过分，ACM 就经常有这种情况啊，说“a and b are the two end-points of the given interval”，故意不说 a 比 b 小，然后又在示例测试中把所有的例子都写成 a 比 b 小，让你产生错觉，却又在测试数据里面来个 a 比 b 大，如果不小心误以为 a 一定比 b 小的就要郁闷了）
  • a 的取值范围为 -100 到 1 。
  • b 的取值范围为 -0.5? 到 3 。
  • eps 如题目中描述的一样，一直都是 0.00005 。

出乎我的意料竟然测试数据的规模这么小的。可是竟然在二分法的时候会 TLE ，这就让我不解了。接着我继续用探针探测出 TLE 出在第三组测试数据上。第三组数据 n 是 5 ，并不大，所以我决定把第三组的参数全部探测出来，当然并不是特别轻松的活，我都想用脚本来写个“探测机”了。不过总算数据并不变态，最后还是被我探测出来了：

a == -4b == 2n == 5c[5] == 1c[4] == 4.6c[3] == -1.94c[2] == 0.296c[1] == -0.0199c[0] == 0.0005

这下为什么会 TLE 就明了了，画出函数图形如下所示：
graph.png
我在判断结束条件的时候用了如下语句：

if (fp == 0 || (GOOD_ENOUGH(b-a, eps) && GOOD_ENOUGH(fp, eps)))

其中 GOOD_ENOUGH 是一个用于判断绝对值的宏。总之就是函数值 fp 在给定的区间 (-4,2) 里面的函数值永远都达不到给定的精度 (eps) ，所以就在那里死循环了。去掉那个判断得出的结果会飞掉，因为我在这里犯了一个很严重的错误：左右两边函数值的符号是一样的，不能用二分法。

但是我是在牛顿法失败的情况下才会去用二分法。牛顿法为什么会失败呢？实际上，在给定的区间之内根本没有实根，只有 4 个虚根，唯一的实根是 -5 左右的那个，但是那个是在区间之外的，可是几乎所有的收敛序列都直接收敛到那里去了，但是是在给定的区间之外的，无疑要被丢弃。

可是这样的话题目不是有问题吗？题目中说过：

It is guaranteed that a unique real number r exists in the given interval such that p(r) = 0.

在给定的区间之内明明没有根嘛，不过单从图形上来看的话，还是很接近零的。最后我将牛顿法的初始值选取密度加大了，总算得到一个看上去像样点的解，算出来的函数值是 0.0045 ，唉，这和零相比应该还有很大的差距吧，可是我把程序提交上去之后竟然 AC 了！不过让我觉得好像是有些碰运气的感觉啊。

不过毕竟是郁闷了几天的题目了，总算是通过了。发现自己在做这样的题目的时候经常都是考虑得太过复杂了。但是如果数学功底再扎实一些，从理论上来仔细分析一下的话，也许不会出现这种类似于“侥幸”通过的尴尬情况了吧。 :)