Loading...
最近学校数据结构课程布置了一个作业,我觉得很有意思,这里记录一下题目布线问题:印刷电路板将布线区域划分为n×m个方格阵列。布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案要求:布线时电路只能沿直线或直角布线。已布线方格做上封闭标记,其他线路布线不允许穿过封闭区域。(如下图所示)算法实现这里使用队列式分支限界法来解决首先,记录起点步数为0,起点的上下左右中,可达的节点步数为1,并将...
适用情况当大量数据位于数据流中,无法一次性读取进内存,未知数据的大小,从中抽取k个数,并且要保证每次抽取的概率相等,这个时候,就适用水塘抽样算法算法详解当k=1时当k=1时,即只抽取一个数算法:每次只保留一个数,当遇到第 i 个数时,以 $\frac{1}{i} $的概率保留它,$\frac{(i-1)}{i} $的概率保留原来的数。对于数字1~4,依次读取之,有:读取1时,概率为1,保留1...
众所周知,斐波那契数是很多动态规划的教程里面的第一个案例,既简单,简单到即使在不会动态规划的情况下,也可以用动态规划的方法把他做了出来,又经典,小小一个题目包含了动态规划的思想,确实不错。因此,尽管斐波那契数比较简单,我依然选择记录一下,算是作为动态规划的第一个笔记吧。当然,本文仅仅算是我个人的理解,跟大佬们讲的有些许甚至很大的出入,仅供参考。什么是动态规划动态规划(英语:Dynamic p...