首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

分享一个算法有关问题

2012-09-12 
分享一个算法问题有一个 0到100的区间, 一个游标在这段区间匀速度移动,每次移动距离不定,满100则从0重新开

分享一个算法问题
有一个 0到100的区间, 一个游标在这段区间匀速度移动,每次移动距离不定,满100则从0重新开始;

目前可以做一个实验,每一秒移动一次,每次可以拿到游标所在的区间(这个区间从0到某个数,或者从某个不为0的数到100),但是不能拿到游标的具体位置;

比如,第一秒可以得到游标处在0到90的区间, 第二秒可以得到游标在0到80区间, 第三秒在 90到100, 第四秒在70到100, 第五秒在0到50, 如此反复;

问题出来了,请问最少要经过多少次测试才能发现游标每次的移动距离,或者说大概的移动距离(结果可以是游标的最小移动距离和最大移动距离,不需要精确, 比如得到的结果可以是游标的移动距离是 5到10每次);

注: 游标每次最少移动5个单位;


本题得分重点,如何将游标的移动速度定位到最精确;

[解决办法]
这个问题只能确定最少移动距离,不能确定最大,因为超过100从0记。没次游标移动的距离只能从前后判断,其它的状态提供不了任何信息,因为有这个超过100从0记这个规则。

[解决办法]
这个问题貌似像二分法查看。二分法是比较稳定的查找方法。例如查找45,依次查看选择是
50 25 37 .。。这样
[解决办法]
这个区间是随机的?如果这样很有可能无解
假如连续100次都是0-98,只能说明移动的距离可能是被100整除的数之一根本无法判断范围
[解决办法]
这个问题最终是一个不等式组的问题。需要多少次,还与每次给的光标区间有关。按照最坏的情况是每次都给出区间是0到100,因为匀速移动,假设每次移动x,按最小移动算,则第1秒后处于x,0<= x <= 100,第2后处于2x,0<= 2*x <= 100;如此下去。到第20秒时,已经有0<= 20*x <= 100,此时x必为5(最小移动5)。所以,应该说最多经过20次可以确定最少每次移动5次。

热点排行