黄金分割及经典算法

《黄金分割及经典算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、美，无处不在——浅谈“黄金分割”和信息学的联系安徽芜湖一中　杨思雨美，无处不在——浅谈“黄金分割”和信息学的联系安徽芜湖一中杨思雨摘要本文主要介绍了“黄金分割”与信息学竞赛的联系及其在一些信息学问题中的应用，全文可以分为四个部分。第一部分引言，主要介绍了“黄金分割”的由来及其和各领域的联系，进而提出探索黄金分割与信息学竞赛的联系。第二部分中逐渐深入的分析了一个例题，最终揭示了问题本质上与黄金分割数的联系，说明了黄金分割数在一些数学性较强的题目中有着广泛的应用。第三部分通过分析另一个例题，介绍了一种优选法——“黄金分割法”。第四部分指出黄金分割与信息学竞赛联系密切，总结全文。

2、关键字黄金分割信息学联系目录引言1例题一2例题二5总结7参考文献7附录8程序描述10第17页共17页美，无处不在——浅谈“黄金分割”和信息学的联系安徽芜湖一中　杨思雨引言早在古希腊时期，人们就发现了“黄金分割”。两千多年前，数学家欧多克斯提出了这样的问题：如图1，线段AB上有一点P，将线段AB分割为两段——AP和PB，若它们长度之比恰好等于整条线段AB与较长一段AP的长度之比，那么P点应该在线段AB什么位置呢？图1我们不妨假设线段AP的长度为1，设线段PB的长度为x，那么线段AB的总长度就是1+x。由，得到方程。解出，记为φ，它的近似值为0.618。而相应的，线段AB的长度

3、就是，记为Φ。在这之后，人们围绕这个比值开展了许多研究，意大利著名的艺术家、科学家达·芬奇还把ф命名为“黄金分割数（GoldenSectionNumber）”。有趣的是，人们发现黄金分割在自然界和其它各个领域中到处可见。例如，人的肚脐是人体总长的黄金分割点，人的膝盖又是肚脐到脚跟的黄金分割点；在有些植物的茎上，相邻叶柄之间的夹角是137º28′,这恰好是把圆周分为1:0.618的两条半径的夹角。此外，黄金分割也被看作是美的化身，人们认为符合黄金分割比例的事物都非常协调，富有美感。这就使得它在建筑、绘画、雕塑、摄影和音乐等艺术领域也有着很广泛的应用，例如：在古希腊帕忒农神庙的

4、设计中就存在着许多组黄金分割比；而在荷兰画家梵高的作品《岸边的渔船》中，整幅画的宽和高分别被桅杆和地平线分成两部分，这样的分割也正好符合了黄金分割比例。其实，在信息学也蕴含着这样的奥妙，本文就将通过两个例题，介绍信息学和黄金分割的一些联系。例题一取石子游戏(STONE)第17页共17页美，无处不在——浅谈“黄金分割”和信息学的联系安徽芜湖一中　杨思雨有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目

5、，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。输入输出要求输入文件由若干行，表示若干种石子的初始情况，其中每一行中包含两个非负整数a和b，表示两堆石子的数目，a和b均不大于1,000,000,000。输出文件对应也是若干行，每行包含一个数字1或0，如果最后你是胜利者，则为1，反之，则为0。样例输入和相应输出样例一输入输出6100样例二输入输出218447010问题描述有两堆石子，游戏开始后，由两个人轮流取石子，每次有两种取法：一是在任意一堆中取走任意数目的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完的人是胜者。现在给出初始的两堆石子

6、的数目a和b（0≤a,b≤109），假设双方都采取最好的策略，判断先手是否有必胜策略。算法一问题中，两堆石子的个数a和b决定了最后的胜负。因此，我们用(a,b)作为表示当前局面的“状态”。通过建立博弈树，判断给出的初始状态(a,b)是必胜还是必败。需要注意的是，由于规则中两个石子堆并没有差别，因此状态(a,b)和状态(b,a)实际上是等价的。（0,0）（1,2）（0,2）（1,0）（1,1）（0,1）（0,0）（0,0）（0,1）（1,0）（0,1）（0,0）（0,0）来看一个例子，游戏开始时，两堆石子的数目分别是1和2，那么初始状态为(1,2)，自顶向下构造出的博弈树如图

7、2（其中，重复子状态可以只扩展一个）。第17页共17页美，无处不在——浅谈“黄金分割”和信息学的联系安徽芜湖一中　杨思雨图2接下来，就可以分三种情况，判断各个状态的胜负情况：(1)如果一个状态没有子状态，根据规则判断胜负；(2)如果一个状态至少有一个子状态先手败，那么该状态先手胜；（0,0）（1,2）（0,2）（1,0）（1,1）（0,1）（0,0）（0,0）（0,1）（1,0）（0,1）（0,0）（0,0）败败败败败败胜胜胜胜胜(3)如果一个状态的所有子状态都是先手胜，那么改状态先手败。图3这样，我们就可以得出初