奥林匹克竞赛论文-登山问题终稿.doc

PAGE PAGE 2 登山问题 (EXPLORER) 【问题描述】 一些OIer准备去翻越OI Mountain，一条雄伟的山脉。但是开始登山之前，OIers希望先知道这条山脉的最高点的位置。 山脉的横截面都是相同的，而且最高点两侧，山的高度也依次递减。OIer们可以使用卫星探测系统来测量某一具体位置上山的高度。每次，他们发出指令Explorer(x)，这时卫星就会返回山脉横截面中，坐标为x的位置上，山的海拔高度。 但是由于和卫星通信总是很慢?，OIers希望能够在40次内找出那个最高点。你能做到么？ 【如何调用交互库】 测试库提供三个函数：Start，Ask，Answer，它们的作用和用法如下： Start()必须首先调用，用它来获得实数L的值。 Ask(X)的作用是询问，用它来获得函数f(x)的值。 Answer(Ans)用来告诉测试库你得到的答案。，表示你的程序判断函数f(x)在Ans处取到最大值。 你的程序不得自行终止且不得访问任何文件。 【对Pascal程序员的提示】 你的程序应当使用下列语句引用测试库： uses tools_p; 测试库提供的函数/过程原型为： function Start:double; function Ask(x:double):double; procedure Answer(ans:double); 【对C++程序员的提示】 你程序头加上一行： #include “tools_c.h” 并且在RHIDE中设置Option-Linker为tools_c.o 测试库提供的函数原型为： double Start(); double Ask(double x); double Answer(double ans); 【数据说明】 　　如果问题中区间范围为[0,2]，f(x)=-(x-1)2+10，那么一种可能满分的调用方法如下： Pascal选手的调用方法 C++选手的调用方法 说明 Start; Start(); 返回值2，表示区间长度 Ask(0); Ask(0); 返回值9，表示f(0)=9 Ask(1.5); Ask(1.5); 返回值9.75 Ask(1); Ask(1); 返回值10 Ask(2); Ask(2); 返回值9 Answer(1); Answer(1); 返回结果，结束程序 注意，该例子只是对库函数的使用说明，并没有算法上的意义。 这里L最大为104，要求最后返回的答案与最高点横坐标误差不超过10-3。山的高度在[0, 8848.13]这个区间内。 【如何测试你的程序】 在当前目录下建立文件explorer.in，其中包含一个实数L，表示为函数f(x)的定义域为0—L,我们的交互库将会自动生成的值。 运行你的程序 运行结束后，交互库将会把整个对话记录在文件explorer.log中 【如何了解错误信息】 如果对话文件explorer.log中包行一行或多行以Error:开头的信息，则表示你的程序在运行过程中发生了错误。具体的错误信息如下所示。 Error: Input file explorer.in not found 交互库在当前目录下没有发现输入文件explorer.in。 Error: Start must call first! 你的程序没有初始化交互库。 Error: You have called Start twice 你的程序尝试多次调用Start函数。 Error: Parameter is out of range 你的程序调用Ask函数的参数不再内。 Error: You have called Ask more than 60 times 你的程序过多的调用了Ask函数（超过60次）。