河内塔与递归

河内塔,又叫汉诺塔,是法国数学家爱德华·卢卡斯于1883年发明,给定一个由八个圆盘组成的塔,这些圆盘按照大小递减的方式在三根桩柱上,需要把整个塔一道另一根桩柱上,一次只能移动一个圆盘,并且必须保证较大的圆盘永远在下面。在电影《猩球崛起》中有这样一个片段,凯撒的妈妈美瞳(Bright eyes)在实验室内在服用一种药物后,智商堪比人类,在对她进行河内塔游戏的测试中,有非常优秀的表现。
实验中的黑猩猩
河内塔还有一个美丽的传说:有64个这样的圆盘组成的塔,上帝命令一群牧师夜以继日的工作,当牧师完成上面的任务时,塔将坍塌,世界也将毁灭。 …阅读更多>>

蒙特卡罗方法和随机数

蒙特·卡罗方法(Monte Carlo method),也称统计模拟方法,是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明,而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。与它对应的是确定性算法。蒙特·卡罗方法在金融工程学,宏观经济学,计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

蒙特卡罗方法最典型的应用是求圆周率π,如下图,在坐标系中,有一个以(0,0)为圆点,半径为1的圆,接下来画一个边长为2的正方形,做到把圆内切在正方形上,如图:
获取圆周率的方法 …阅读更多>>

排序算法的思考和实践

排序是程序开发过程中非常常见的一种操作,是将一组无序的记录序列调整为有序记录。例如,30个学生的考试成绩需要进行从大到小的排列,很多高级语言为我们提供了内置的排序操作,下面是PHP,
JS, 和Python为我们提供的对学生成绩进行排序的方法:

<?php
$score = array(68,79,85,92,99,75,66,88,71,71,63,89,91,96,83,85,86,66,63,66,59,60,65,66,69,67,79,80,90,60);
echo sort($score);//升序排列
echo rsort($score);//降序排列
?>

score = new Array(68,79,85,92,99,75,66,88,71,71,63,89,91,96,83,85,86,66,63,66,59,60,65,66,69,67,79,80,90,60);
score.sort(); //升序排列(字符编码顺序)
score.sort(function(a,b){ return a-b}); //升序排列
score.sort(function(a,b){ return b-a}); //降序排列
score = [68,79,85,92,99,75,66,88,71,71,63,89,91,96,83,85,86,66,63,66,59,60,65,66,69,67,79,80,90,60]
print sorted(score)  //升序排列
print sorted(score,cmp=lambda x,y:cmp(y,x)) //降序排列

…阅读更多>>