大榕树 \ Pascal语言 \ Pascal入门

PascalFAQ之特殊技术

原文链接：http://www.mydrs.org/program/list.asp?id=459

如何实现卡时？

卡时是一种让程序在运行了指定长度的时间以后可以自动终止运行并输出结果的技术，其基本原理通常是在程序启动时获取启动时间，然后在程序重复执行的地方获取当前时间，通过计算时间差判断程序已经运行了多久，当程序已运行的时间达到或接近指定的时间后立即输出已知的最优结果并且中断程序。卡时技术通常用在使用穷举或搜索的程序中。

在Turbo Pascal中，可以通过访问MemL[Seg0040:$006C]来获取当前时间，它返回的是当日零时到现在所经过的时间，单位约为55毫秒（约1/18.2秒）。下面是一个使用卡时技术的样例程序：

{$N+}



var

  StartTime: Longint;

  I, J: Extended;



begin

  StartTime := MemL[Seg0040:$006C];

  I := 0;

  J := 0;

  repeat

    if I * I - 1234567 * I + 777 < J * J - 1234567 * J + 777 then J := I;

    I := I + 1;

  until MemL[Seg0040:$006c] - StartTime >= 500 div 55;

  Writeln('x^2 - 1234567x + 777 has a minimum result when x = ', J: 0: 0);

end.

上面的程序在运行0.5秒以后将自动输出结果并结束运行。注意，该程序如果跨越零时运行，将无法自动结束程序。如果你希望你的程序在跨越零时运行时仍然可以自动结束，请自行优化你的程序。

在Free Pascal中，很难像Turbo Pascal一样直接访问内存（除非你使用DOS模式编译），通常只能通过调用系统函数来获取当前时间，但在比赛中一般是不允许程序调用系统函数的，因此很难实现卡时。

作者：陈世熹
来源：
时间：2003-01-01

上一篇：PascalFAQ之基本技巧
下一篇：IOI2003国家集训队难题讨论

大榕树 版权所有 ©1999-2006