黄金分割二分法数值分析回顾

今天看了2012年写的对黄金分割二分法的数值探讨,推理公式不记得了,当时写的不细致,,晚上回顾了下,做了些补充

原文:

比如ABCDE 5个节点,通过以下斐波拉契数列二分方式组织起来,

找A需要3次,即从5开始到A的路径

找B需要3次

找C需要2次

找D需要2次

找E需要2次

平均期望次数E=总次数 / 节点数 = (3+3+2+2+2) / 5 = 2.4

这里,设斐波拉契数列Tn 为 1 1 2 3 5 8 13 21 ……

设总次数为F

可以发现,随着层次的增加,存在着递推关系

F0 = 0

F1 = 0

F2 = F1 + t(2) + F0 + t(1)

Fn = Fn-1 + t(n) + Fn-2 + t(n-1)

En = Fn / sum

= Fn / t(n+1)

= (Fn-1 + Fn-2 + t(n+1) ) / t(n+1)

= 1 + Fn-1 / t(n+1) + Fn-2 / t(n+1)

= 1 + En-1 * t(n) / t(n+1) + En-2 *t(n-1)

从这里可以看出,期望正好是左右2块的期望值加上深度1,在数学计算与逻辑上也是一致的

数值分析程序和数据见原文

因害怕失败而不敢放手一搏,永远不会成功

黄金分割二分法数值分析回顾

相关文章:

你感兴趣的文章:

标签云: