什么是算法？简单地说，算法就是有穷规则构成的用于解决某一类问题的运算序列或执行步骤。在《算法之美：隐匿在数据结构背后的原理》第1章中我们讲到要解决一个问题可能会有不同的方法，当时所举的例子就是求圆周率π的近似值。对于这个问题你能想到多少种算法呢？
探秘算法世界，求索数据结构之道；
汇集经典问题，畅享编程技法之趣；
点拨求职热点，敲开业界名企之门。
本书内容简介及勘误表请参见《算法之美隆重上市欢迎关注（另附勘误表在此）》。
方法(1)：首先根据微积分中的泰勒公式，可以使用下面这个公式来求π的近似值
方法(2)：其次可以还可以利用下面这个马青公式来求解π的近似值：
马青公式由英国天文学家约翰·马青（John Machin，1686 –1751）于1706年发现，他利用这个公式计算到了100位的圆周率。此外，上式中的反三角函数可以领用下面这个泰来展开式进行计算：
方法(3)：最后，也是我们准备来动手实践一下的就是利用蒙特卡洛法。这个方法背后的理论基础是概率论中的伯努利大数定律。众所周知，圆的面积公式为S=πr2，当r= 1 时，S=π。如果在一个边长为1的正方形中有一个内切圆，那么该圆的面积就是π/4。利用这一原理，可以假设有大量的随机点等概率均匀地落入此正方形中。若正方形的面积为S'，内切圆的面积为S，如果落入正方形中的点数为N'，落入内切圆的面积为N，这时便有S'/S=N'/N，所以可据此求得π=4×N/N'。
下面就编写一个Java程序来实现蒙特卡洛法求π的近似值：
[java]view plaincopyimportjava.io.BufferedReader; importjava.io.InputStreamReader; publicclassMonteCarloPi{ publicstaticvoidmain(String[]args)throwsException{ BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in)); System.out.print("HowmanydartsshoudItossattheboard?\n"); Strings=br.readLine(); intnumberOfDarts=Integer.parseInt(s.trim()); doubleradius=1.0; Dartboardd=newDartboard(radius); for(inti=1;i<=numberOfDarts;i++){ Tosst=Toss.getRandom(radius); d.strike(t); } doublefractionIn=d.getFractionIn(); doublepi=4.0*fractionIn; System.out.println("Piisapproximately"+pi); } } classDartboard{ privatedoubleradius; privateintinsideCircle,outsideCircle; publicDartboard(doubleradius){ this.radius=radius; insideCircle=0; outsideCircle=0; } publicvoidstrike(Tosstoss){ doublex=toss.getX(); doubley=toss.getY(); if(Math.sqrt(x*x+y*y)<radius) insideCircle++; else outsideCircle++; } publicdoublegetFractionIn(){ doubletotal=(double)(insideCircle+outsideCircle); return(double)insideCircle/total; } } classToss{ privatedoublex,y; publicToss(doublex,doubley){ this.x=x; this.y=y; } publicdoublegetX(){returnx;} publicdoublegetY(){returny;} publicstaticTossgetRandom(doubleradius){ doublex,y; doublesize=Math.random(); doublesign=Math.random(); size=size*radius; if(sign>0.5) x=size; else x=-size; size=Math.random(); sign=Math.random(); size=size*radius; if(sign>0.5) y=size; else y=-size; returnnewToss(x,y); } }
执行一下上述代码，然后我们来验证一下其效果如何...[plain]view plaincopyHowmanydartsshoudItossattheboard? 1000000 Piisapproximately3.142028
可见所得到的结果较好地近似于圆周率π。
（本文完）
