问题描述
这个问题基于 Joel Spolsky 的一个谜题 从 2001 年开始.
This problem is based on a puzzle by Joel Spolsky from 2001.
一个人找到了一份街头油漆工的工作，在马路中间画虚线."第一天他跑了 300 码，第二天跑了 150 码，3号就更不用说了.老板大怒，要求解释.
A guy "gets a job as a street painter, painting the dotted lines down the middle of the road." On the first day he finishes up 300 yards, on the second - 150, and on the 3rd even less so. The boss is furious and demands an explanation.
我忍不住了，" 那个家伙说.每天我离油漆罐越来越远！"
我的问题是，你能估计他第三天走过的距离吗?
My question is, can you estimate the distance he covered in the 3rd day?
链接线程中的一个评论确实得出了一个精确的解决方案，但我的问题是关于一个足够好的估计——比如 10%——这很容易从一般原则中得出.
One of the comments in the linked thread does derive a precise solution, but my question is about a good enough estimation -- say, 10% -- that is easy to make from the general principles.
澄清:这是关于算法分析的某种方法，不是关于开发算法，也不是代码.
clarification: this is about a certain method in analysis of algorithms, not about developing an algorithm, nor code.
推荐答案
这里有很多未知数——他的行走速度，他的绘画速度，画笔里的颜料能持续多久……
There are a lot of unknowns here - his walking speed, his painting speed, for how long does the paint in the brush last...
但显然这里有两个进程在进行.一个是二次的——它是在油漆罐和油漆点之间来回走动.另一个是线性的——它是绘画的过程，本身.
But clearly there are two processes going on here. One is quadratic - it's the walking to and fro between the paint can and the painting point. The other is linear - it's the process of painting, itself.
考虑到第 10 天甚至第 100 天，很明显线性分量变得可以忽略不计，并且过程变得非常接近二次方——步行几乎需要所有时间.相反，在第一天的前几分钟，它接近于线性.
Thinking about the 10th or even the 100th day, it is clear that the linear component becomes negligible, and the process becomes very nearly quadratic - the walking takes almost all the time. During the first few minutes of the first day, on the contrary, it is close to being linear.
因此我们可以说时间t作为距离s的函数遵循幂律t ~ s^a 的变化系数 a = 1.0 ... 2.0.这也意味着s ~ t^b, b = 1/a.
We can thus say that the time t as a function of the distance s follows a power law t ~ s^a with a changing coefficient a = 1.0 ... 2.0. This also means that s ~ t^b, b = 1/a.
第 1 天和第 2 天之间的 b 系数近似为
The b coefficient between day 1 and day 2 is approximated as
b(1,2) = log (450/300) / log 2 = 0.585 ;; and so,
a(1,2) = 1/b(1,2) = 1/0.585 = 1.71
正如预期的那样，a 系数低于 2.对于第 2 天和第 3 天之间的时间段，我们可以将其设置为大约 1.71 和 2.0,
Just as expected, the a coefficient is below 2. Going for the time period between day 2 and day 3, we can set it approximately to the middle value between 1.71 and 2.0,
a(2,3) = 1.85 ;; a = 1.0 .... 2.0
b(2,3) = 0.54 ;; b = 1.0 .... 0.5
s(3) = s(2) * (3/2)^b(2,3)
= 450 * (3/2)^0.54
= 560 yards
因此第三天走过的距离可以估算为560 - 450 = 110码.
Thus the distance covered in the third day can be estimated as 560 - 450 = 110 yards.
如果 a 系数已经具有最大可能值 2.0 会怎样(这是不可能的)?然后，450*(3/2)^0.5 = 551 码.而对于另一个极端，如果它是相同的 1.71(显然也不可能)，450*(3/2)^0.585 = 570.
What if the a coefficient had the maximum possible value, 2.0, already (which is impossible)? Then, 450*(3/2)^0.5 = 551 yards. And for the other extreme, if it were the same 1.71 (which it clearly can't be, either), 450*(3/2)^0.585 = 570.
这意味着 110 码的估计是合理的，两边的误差都小于 10 码.
This means that the estimate of 110 yards is plausible, with an error of less than 10 yards on either side.
这篇关于画家拼图 - 估计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！