首页 > 笔试面试题 > 有趣的笔试题:捞鱼问题

有趣的笔试题:捞鱼问题

2012年6月12日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

话说这道题还是三年前径点公司来学院笔试中的一道题目,当时刚进入实验室,师兄在带着我们做新生培训的时候做过这道题,最近回顾DP的一些基础,翻找以前写的程序,发现了这道题,就贴一下,给出两种方法的代码,并对比了它们在不同规模问题下的效率。

题目:20个桶,每个桶中有10条鱼,用网从每个桶中抓鱼,每次可以抓住的条数随机,每个桶只能抓一次,问一共抓到180条的排列有多少种 (也可求概率)。

分析:我们要在20个桶中一共抓取180条鱼,每个桶能抓到鱼的条数为0-10,仔细想下,这个问题是可以分解成子问题的:假设我们在前i个桶中抓取了k(0<=k<=10*i)条鱼,那么抓取180条鱼的排列种数就等于在剩下的(20-i)个桶中抓取(180-k)条鱼的方法加上前i个桶中抓取k条鱼的方法。

例如,在第一个桶中抓取了2条鱼,那么总的排列数等于在剩下19个桶中抓取178条鱼的排列种数;如果在第一个桶中抓取了10条鱼,那么总的排列数等于在剩下19个桶中抓取170条鱼的排列数,,,依次分解该问题,总的排列数就等于所有这些排列数的总和。有点DP的感觉。

换个思维,在实现上这个题目可以有更为简洁的方法,我们看看这个问题的对偶问题,抓取了180条鱼之后,20个桶中剩下了20条鱼,不同的抓取的方法就对应着这些鱼在20个桶中不同的分布,于是问题转化为将20条鱼分到20个桶中有多少中不同的排列方法(这个问题当然也等价于180条鱼分到20个桶中有多少种不同的方法)?其中,每个桶最多放10条,最少放0条。这样一转化,无论是用搜索还是DP,问题规模都缩小了很大一块。

按照这个分析,最直接的方法就是用递归了,递归实现DP问题,自顶向下,为了防止重复计算子问题(例如求19个桶放12条鱼的方法数时算了一遍子问题17个桶放10条鱼的方法数,在算18个桶,17个桶时就不用再计算17个桶放10条鱼的情况了),一般设置一个备忘录,记录已经计算过的子问题,其实这个备忘录就是在自底向上实现DP时的状态转移矩阵

递归实现,如果桶没了,鱼还有,说明这种排列不符合要求,应该结束并返回0;如果桶还有,鱼没了,说明这种排列也不符合要求;只有在桶没了,鱼也没了的情况下才说明20条鱼恰好分放到了20个桶。根据上面分析我们知道每个桶有11种情况,代码如下:

#include <iostream>
using namespace std;

/*
  捞鱼:将20条鱼放在20个桶中,每个桶最多可以放10条
  求得所有的排列方法
  DP自顶向下递归 备忘录
*/

int dp[21][21]; /* 备忘录,存储子问题的解; 表示前i个桶放j条鱼的方法数 */

int allocate(int bucketN, int fishN)
{
	if(bucketN == 0 && fishN == 0)
	{
		return 1;
	}
	if(bucketN == 0 || fishN < 0)
	{
		return 0;
	}

	/* 如果子问题没有计算就计算,否则直接返回即可 */

	if(dp[bucketN][fishN] == 0)
	{
		for(int i = 0; i <= 10; ++i)
		{
			dp[bucketN][fishN] += allocate(bucketN-1,fishN-i);
		}
	}
	return dp[bucketN][fishN];
}

void main()
{
	int bucketN, fishN;
	while(scanf("%d %d", &bucketN, &fishN)!= EOF)
	{
		memset(dp,0,sizeof(dp));
		printf("%d\n",allocate(bucketN,fishN));
	}
}

输出:

结果如图,先输入一个小数据验证解是否正确,可以看出这个解是非常大的,最初实现的两种情况都是等了好久都没有出来结果,一种是没有使用备忘录,单纯递归的搜索,非常非常非常慢,等了两分钟都没有结果;一种是没有求对偶问题,而是求dp[20][180]也是相当的慢。

既然可以用DP,我们通常使用自底向上的方法,下面来看看非递归实现的方法。自底向上就需要考虑合法状态的初始化问题,从小规模去考虑,20个桶太大,考虑零个桶,一个桶,零个桶装多少鱼都是非法的,故就是0;一个桶装鱼,装0-10条鱼都是合法的,其余的就不合法了; dp[i][j]:前i个桶放j条鱼的方法共分为11种情况:前i-1个桶放j-k0<=k<=10)条鱼的方法总和。我们可以得到状态方程:


f(i,j) = sum{ f(i-1,j-k), 0<=k<=10}

考虑到这,dp的程序就出来了,代码如下:

#include <iostream>
using namespace std;

/*
  捞鱼:将20条鱼放在20个桶中,每个桶最多可以放10条
  求得所有的排列方法
  自底向上DP f(i,j) = sum{ f(i-1,j-k), 0<=k<=10}
  该方法中测试 20个桶 180条鱼,与递归速度做对比
*/

/* 实现1 */

int dp[21][200]; /* 前i个桶放j条鱼的方法数 */
int i, j, k;

void main()
{
	int bucketN, fishN;
	while(scanf("%d %d", &bucketN, &fishN)!= EOF)
	{
		memset(dp,0,sizeof(dp));

		for(int i = 0; i <= 10; ++i)  /* 初始化合法状态 */
		{
			dp[1][i] = 1;
		}
		for(int i = 2; i <= bucketN; ++i)  /* 从第二个桶开始 */
		{
			for(int j = 0; j <= fishN; ++j)
			{
				for(int k = 0; k <= 10 && j-k >= 0; ++k)
				{
					dp[i][j] += dp[i-1][j-k];
				}
			}
		}
		printf("%d\n",dp[bucketN][fishN]);
	}
}

输出:

当我们测试20个桶放180条鱼的方法,结果立即就算出来了,而用递归则是等了半天没反应,由此我们可以看出效率的差别有多大。同时,两个对偶问题的答案是一样的,说明我们的分析是没错的,:-)。

其实,代码还可以更简练,仔细想想,就是初始化状态的方法;其实初始化合法状态完全可以这样想,问题始终都是分解成子问题的,根据递归的实现方法,只有分解到0个桶装0条鱼才是合法的,那么我们就初始化这一个状态为合法即可,然后从第一个桶开始向上计算,代码如下:

/* 实现2 */

int dp[21][200];
int i, j, k;

void main()
{
	int bucketN, fishN;
	scanf("%d %d", &bucketN, &fishN);

	dp[0][0] = 1;  /* 初始化合法状态 */

	for(int i = 1; i <= bucketN; ++i)  /* 从第一个桶开始 */
	{
		for(int j = 0; j <= fishN; ++j)
		{
			for(int k = 0; k <= 10 && j-k >= 0; ++k)
			{
				dp[i][j] += dp[i-1][j-k];
			}
		}
	}
	printf("%d\n",dp[bucketN][fishN]);
}

从递归到非递归再到现在,一个看似规模很大很复杂的问题只用简单的几行代码就可以解决,关键在于怎么思考,要好好修炼。

总结:

  •  问题分解成子问题
  •  寻对偶问题减少问题规模
  • 不断Thinking,追求简炼代码

本文相关代码可以到这里下载。

(全文完)

  • Yx.Ac

    能具体说说么?找对偶问题是不会溢出的@outlaw

  • outlaw

    用int会溢出的