2009年9月刊《程序员》算法题之我见——思索之三

时间:2023-02-11 15:04:40

本系列文章目录

 

20099月刊《程序员》算法题之我见——思索之一

20099月刊《程序员》算法题之我见——思索之二

20099月刊《程序员》算法题之我见——思索之三 

 

接上文“20099月刊《程序员》算法题之我见——思索之二

 

仔细分析后发现,似乎不能推导出一个统一的公式来计算出大于三行的可能数。只能另辟蹊径。

 

问题七:M=15N=2P=S,求方案总数

这个问题现在的解决方法如下

第一步:先得到每一行P=2S的方案数以及每一个方案

 

第二步:将每一个方案一拆二,分为SS。这表示这两个方案使能够相邻的,将相邻的可能压入一个表,用来备用。这一步的理由参看上一篇文章

 

第三步:初始化第一行的每一种可能,每一种的可能都计数为1。从第二行开始,通过查表,得知上一行的每一个方案在这一行的相邻方案是什么,然后计数。随着行数的增多,每种方案在每一行出现的可能数都会发生变化。

 

第四步:到最后一行,统计最后一行每一种方案的各自可能数。然后求总和。

 

经过测试,M=15N=150P=4的解为70种,和之前的问题五的答案一致。当M=15N=4P=2的解出乎我的意料,为3328134种。不知其他人的答案是否和我的一致,欢迎交流。

下面详细分析每一步,并贴代码,用的是VB2005

 

函数

Public Function CacuInternSiteCount(ByVal Line As Integer, ByVal SitePerLine As Integer, ByVal InternPerLine As Integer) As Integer

Line表示行数

SitePerLine表示每一排的座位数

InternPerLine表示每一排的实习生数

返回方案总数

先是变量定义:

 

都是临时变量,后面再详细介绍。

 

预备步:

 

在后面的第二步计算中,要将每一个方案一拆二。而一拆二的依据就是利用组合原理,从2S中选出S的组合来,这个利用的组合函数,以及获得组合的方法在详细可以参见“遍历组合的实现——VB2005遍历排列的实现——VB2005两篇文章

 

第一步:先得到每一行P=2S的方案数以及每一个方案。这里得到的每一个方案也是调用组合函数。得到一个组合再判断这个组合是否符合题目的要求,用的是IsOk这个函数。

第二步:将每一个方案一拆二,分为SS。这表示这两个方案使能够相邻的,将相邻的可能压入一个表,用来备用。

 

 

这里调用了IsOk函数,这是判断实习生的位置是否符合题目的要求,代码如下:

还有一个注意的地方,很多人以为VB2005是没有移位运算的,可其实是有的。这里的S1就是2S的一个组合,然后拆分为S2S3S的组合。

 

第三步:初始化第一行的每一种可能,每一种的可能都计数为1。从第二行开始,通过查表,得知上一行的每一个方案在这一行的相邻方案是什么,然后计数。随着行数的增多,每种方案在没一行出现的可能数都会发生变化。

 

最后一步统计:统计每一种情况出现的可能数,求总和,并返回。

 

 

最后将上述所有代码一起贴下来。也欢迎大家交流。