📄 2_4.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.4.1 递推关系 </h1><p> Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。 </p> <p> 问题：有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为F<sub>n</sub> 其中当月新生兔数目设为N<sub>n</sub> 对。第n-1个月留下的兔子数目设为O<sub>n</sub> 对。 </p> <p> <img border="0" src="2_4.pic/image008.gif" width="111" height="24"></p> <p>但O<sub>n</sub> =F<sub>n-1, </sub>N<sub>n</sub>=O<sub>n-1=</sub>F<sub>n-2</sub>即第n-2个月的所偶兔子到第n个月都有繁殖能力了。 </p> <p> <img border="0" src="2_4.pic/image012.gif" width="308" height="24"></p> <p>由递推关系(2-3-1)式可依次得到 </p> <p> <img border="0" src="2_4.pic/image014.gif" width="232" height="48"></p> <p>§2.4.2 问题的求解 </p> <p> 设 G(x)=F<sub>1</sub>x+F<sub>2</sub>x<sup>2</sup>+<sup>...</sup></p> <p> <img border="0" src="2_4.pic/image018.gif" width="139" height="75"></p> <p> <img border="0" src="2_4.pic/image020.gif" width="159" height="7"></p> <p> <img border="0" src="2_4.pic/image022.gif" width="236" height="24"></p> <p> <img border="0" src="2_4.pic/image024.gif" width="152" height="24"></p> <p> <img border="0" src="2_4.pic/image026.gif" width="313" height="131"></p> <p> <img border="0" src="2_4.pic/image028.gif" width="104" height="72"> <img border="0" src="2_4.pic/image030.gif" width="87" height="72"></p> <p> <img border="0" src="2_4.pic/image032.gif" width="143" height="44"></p> <p> <img border="0" src="2_4.pic/image034.gif" width="281" height="109"></p> <p> <img border="0" src="2_4.pic/image036.gif" width="143" height="41"></p> <p>其中 </p> <p> <img border="0" src="2_4.pic/image038.gif" width="272" height="48"></p> <p> <img border="0" src="2_4.pic/image040.gif" width="311" height="48"></p> <p> <img border="0" src="2_4.pic/image042.gif" width="140" height="49"></p> <p> §2.4.3 若干等式 </p> <p> 1） F<sub>1</sub>+F<sub>2</sub>+<sup>...+</sup>F<sub>n</sub>=F<sub>n+2</sub>+(-1) (2-3-3)</p> <p> 证明： </p> <p> <img border="0" src="2_4.pic/image046.gif" width="131" height="120"></p> <p> <img border="0" src="2_4.pic/image048.gif" width="199" height="7"> </p> <p> <img border="0" src="2_4.pic/image050.gif" width="269" height="24"></p> <p> 2） F<sub>1</sub>+F<sub>3</sub>+F<sub>5</sub>+<sup>...+</sup>F<sub>2n-1</sub>=F<sub>2n</sub> (2-3-4)</p> <p> 证明： </p> <p> <img border="0" src="2_4.pic/image054.gif" width="147" height="120"></p> <p> <img border="0" src="2_4.pic/image055.gif" width="199" height="7"></p> <p> <img border="0" src="2_4.pic/image057.gif" width="211" height="24"></p> <p> 3） F<sub>1</sub><sup>2</sup>+F<sub>2</sub><sup>2</sup>+<sup>...+</sup>F<sub>n</sub><sup>2</sup>=F<sub>n</sub>F<sub>n+1</sub> (2-3-5)</p> <p> 证明： </p> <p> <img border="0" src="2_4.pic/image061.gif" width="275" height="128"></p> <p> <img border="0" src="2_4.pic/image062.gif" width="199" height="7"></p> <p> <img border="0" src="2_4.pic/image064.gif" width="209" height="27"></p> <p>§2.4.4 在选优法上的应用 </p> <p> 设函数y=f(x)在区间(a,b)上有一单峰极值点，假定为极大点。 </p> <p> 所谓单峰极值，即只有一个极值点£ ，而且当x与£偏离越大，偏差|f(x)-f(£)|也越大。如下图： </p> <p> <img border="0" src="2_4.pic/image181.gif" width="334" height="227"></p> <p>设函数f(x)在x=£点取得极大值。要求用若干次试验找到£点准确到一定的程度。最简单的方法，把(a,b)三等分，令： </p> <p> <img border="0" src="2_4.pic/image072.gif" width="231" height="41"></p> <p> 如下图： </p> <p> <img border="0" src="2_4.pic/image182.gif" width="334" height="222"></p> <p> 当f(x<sub>1</sub>)>f(x<sub>2</sub>) ，则极大点£必在(a,x<sub>2</sub>)区间上，区间(x<sub>2</sub>,b)可以舍去。 </p> <p> <img border="0" src="2_4.pic/image183.gif" width="726" height="274"></p> <p> 当f(x<sub>1</sub>)<f(x<sub>2</sub>)，则极大点£必在(x<sub>1</sub>,b)区间上，区间(a,x<sub>1</sub>)可以舍去。 </p> <p> <img border="0" src="2_4.pic/image184.gif" width="726" height="287"></p><p> 当f(x<sub>1</sub>) = f(x<sub>2</sub>) ，则极大点£必在(x<sub>1</sub>,x<sub>2</sub>) 区间上，区间(a,x<sub>1</sub>) 和(x<sub>2</sub>,b) 均可以舍去。 </p> <p> <img border="0" src="2_4.pic/image185.gif" width="726" height="274"></p><p> 可见做两次试验，至少可把区间缩至原来区间的2/3，比如f(x<sub>1</sub>)>f(x<sub>2</sub>)，进一步在(a,x<sub>2</sub>)区间上找极值点。若继续用三等分法，将面对着这一实事，即其中x<sub>1</sub>点的试验没发挥其作用。为此设想在(0,1)区间的两个对称点x,l-x分别做试验。 </p> <p> <img border="0" src="2_4.pic/image186.gif" width="293" height="81"></p><p>设保留(0,x)区间，继续在(0,x)区间的下面两个点x<sup>2</sup>,(1-x)x 处做试验，若</p> <p> <img border="0" src="2_4.pic/image117.gif" width="247" height="24"></p> <p>则前一次1-x的点的试验，这一次可继续使用可节省一次试验。由(2-3-6)式有 </p> <p> <img border="0" src="2_4.pic/image119.gif" width="169" height="72"></p> <p> <img border="0" src="2_4.pic/image187.gif" width="551" height="81"></p><p>这就是所谓的0.618优选法。即若在(0,1)区间上找单峰极大值时，可在x<sub>1</sub>=0.618, x<sub>2</sub>=1-0.618=0.382点做试验。比如保留区间(0,0.618)，由于(0.618)<sup>2</sup>=0.382，故只要在0.618x0.382点作一次试验。 </p> <p> 优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。 </p> <p> (a) 所有可能试验数正好是某个F<sub>n</sub> 。 </p> <p> <img border="0" src="2_4.pic/image188.gif" width="486" height="81"></p> <p> 这时两个试验点放在F<sub>n-1</sub>和F<sub>n-2</sub>两个分点上，如果F<sub>n-1</sub>分点比较好，则舍去小于F<sub>n-2</sub>的部分；如果F<sub>n-2</sub>点更好，则舍去大于 F<sub>n-1</sub>的部分。在留下的部分共F<sub>n-1</sub>个分点，其中第F<sub>n-2</sub>和F<sub>n-3</sub>第 二试验点，恰好有一个是刚才留下来的试验可以利用。 </p> <p> 可见在F<sub>n</sub>个可能试验中，最多用n-1次试验便可得到所求的极值点 </p> <p> (b)利用Fibonacci数列进行优选不同于0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比F<sub>n</sub>小,但比F<sub>n-1</sub>大时,可以虚加几个点凑成F<sub>n</sub>个点，但新增加的点的试验不必真做，可认定比其他点都差的点来处理。 </p> <p> 证：对n用数学归纳法。 </p> <p> n=2时，将区间(a,b)平分成F<sub>2+1</sub>=2 段。在分点（包括端点a，b）分别标上0,1,2。在1点的两侧取ç，在1+ç与1-ç两点上测试，无论哪一点较优，保留下来的区间长度均为1+ç ，命题成立。 </p> <p> 假设对于n-1，命题成立 </p> <p> 对于n，将(a,b)平分成F<sub>n+1</sub>段，对分点（包括端点a，b）依次标上0,1,<sup>...</sup>,F<sub>n+1</sub>。先在F<sub>n-1</sub>点与F<sub>n</sub>点测试，无论哪一点较优，保留下来的区间均为F<sub>n</sub>段。根据归纳假设，再做n-1次测试（内含前两次测试之一）可将含极值点的区间缩小到1+ç段，即原区间(a,b)的1/F<sub>n+1</sub>+ç。 </p> <p> 因</p> <p> <img border="0" src="2_4.pic/image178.gif" width="196" height="27">，</p> <p>当n较大时，可将相继的两个测试点取在待测区间的0.618及1-0.618处。由 </p> <p> <img border="0" src="2_4.pic/image180.gif" width="237" height="49"></p> <p>可知，0.618法比F<sub>n</sub>法最多多测试一次。0.618法的优点是不必事先定测试次数。 </p> <p> 定理：设在给定区间内有单峰极值点。如果包含极值点在内的可测点为F<sub>n-2</sub>+1个，则测试n次必可找到极值点，n>=2。 </p> <p> 证：对n用数学归纳法。 </p> <p> n=2时，F<sub>2-2</sub>-1=2命题成立 </p> <p> 假设对于n-1，命题成立 </p> <p> 下面证明对n命题成立。设可测试点的标号依次是0,1,<sup>...</sup>,F<sub>n</sub>,<sup>...</sup>,F<sub>n+1</sub>,<sup>...</sup>,F<sub>n+2</sub>-1。先在F<sub>n</sub>点及F<sub>n+1</sub>点测试。无论哪一点较优，保留下来的可测点都为F<sub>n+1</sub>-1个。根据归纳假设，再测试n-1必可找到极值点。而在保留的F<sub>n+1</sub>-1个可测试点中，有一点（ F<sub>n</sub>或F<sub>n+1</sub> ）的测试结果下一次比较好时正好用上，这样总测试次数为n。</p> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -