1701009720
小球自上方落下，经过n个钉子。每经过一个钉子时只有两种可能结果：向左或向右，这是一个具有两个结果（成功和失败）的随机试验E，将向右视为成功，其概率为p，向左视为失败，其概率为1-p。小球碰到一个钉子下落一格，相当于进行了一次试验E，自顶端落下，碰到n个钉子，最终落到某个格子的过程，恰好相当于将试验E重复了n次，因此一次投球过程就是一个n重贝努利试验。n重贝努利试验的成功次数X正好就是小球向右移动的次数，是一个随机变量，根据概率论的结果，它服从二项分布，即X～B（n，p）。其取值与模拟模型的对应关系如表8-4所示。
1701009721
1701009722
表8-4 格子编号与随机变量取值对应表
1701009723
1701009724
1701009725
1701009726
1701009727
利用概率论知识，二项随机变量X的分布列为：
1701009728
1701009729
1701009730
1701009731
1701009732
有了上面的理论分析之后，我们可以比较n次投球小球堆积的频率图和X～B（n，0.5）的分布图之间的差异。
1701009733
1701009734
编写MATLAB程序如下：
1701009735
1701009736
clc,clear,close all %清屏和清除变量 warning off %消除警告 %Galton钉板试验 %设置参数 m = 500; n=5; p=0.5; rand(‘seed’,3); R=binornd(n,p,1,m); %模拟服从二项分布的随机数，相当于模拟投球m次 %确定落在编号为i-1的格子的小球频率 for i=1:n+1 k=[]; k = find(R==(i-1)); h(i)=length(k)/m; end x=0:n; figure(‘color’,[1,1,1]) subplot(121) %画频率图 axis([-1,6,0,1]) bar(x,h) xlabel(‘(1)500次投球小球堆积的频率图’) f = binopdf(x,n,p); subplot(122) axis([-1,6,0,1]) bar(x,f) xlabel(‘(2)理论分布B(5,0.5)的分布图’)
1701009737
1701009738
运行程序输出图形如图8-13所示。
1701009739
1701009740
1701009741
1701009742
1701009743
图8-13 用二项分布描述Galton钉板试验
1701009744
1701009745
500次投球小球堆积频率图和理论分布X～B（n，0.5）的分布图是接近的，因此可知道，Galton试验过程中，小球运动是服从二项分布X～B（n，p）的。
1701009746
1701009747
1701009748
1701009749
1701009750
我和数学有约：趣味数学及算法解析 [:1701004258]
1701009751
我和数学有约：趣味数学及算法解析 8.4 七桥问题
1701009752
1701009753
图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”，如图8-14所示，结构简图如图8-15所示。
1701009754
1701009755
1701009756
1701009757
1701009758
图8-14 哥尼斯堡的七座桥 图8-15 结构简图 1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”的游戏，用图论的术语，就是如何找出一个连通图中的生成圈。
1701009759
1701009760
近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学、生物遗传学、心理学、经济学和社会学等学科中。
1701009761
1701009762
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。
1701009763
1701009764
1701009765
1701009766
1701009767
图8-16 七桥模型树形图
1701009768
1701009769
哥尼斯堡七桥问题就是一个典型的例子，简化的树形图如图8-16所示。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连接起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。