算法每日一题（六）—___穷举法
本帖最后由 LNH_Sniper 于 2011-7-8 23:17 编辑问题：TOM共有5本新书，要借给A、B、C3位同学，每人只能借一本书，则TOM可以有多少种不同的借书方**
提示：本题目是典型的穷举法的应用，属于简单题
最多能借一本最少可不可以不借 asd82937121 发表于 2011-7-9 08:13 static/image/common/back.gif
最多能借一本最少可不可以不借
不可以不借
恩这题挺锻炼思想的实际上是吧实际问题转化为抽象的概念， 这个问题和彩票选数差不多每个数字是1-5,5选3，所有都列举就可以了呗 考虑这个问题的一般化，把m本书借给n个人，每人必须且只能借一本。
假设有f(m,n)种借法，则：
f(m,n)=m*f(m-1,n-1)（其中，m>=n）---第一个人有m种选择，剩下m-1本书借给n-1个人
且有
f(x,0)=1（其中x>=0）--- 把x本书借给0个人只有1种借法（就是不借）
所以用递归解这个问题是可以的。程序如下：#include<stdio.h>
int f(int m, int n){
if(n==0) return 1;
return m*f(m-1,n-1);
}
int main(){
printf("%d\n",f(5,3));
}其实数学好的话，直接算5*4*3也可以得到答案，不过这就和编程没什么关系了。 首先，穷举法是最为简单，也是最为直接，同时又是最为耗时的一种解决实际问题的算法思想。
穷诀法的基本思想是:在可能的解空间中穷举出每一种肯能的解，并对每个可能的解进行判断，从中得到答案。
其中最关键步骤是：划定问题的解体空间，并在该解空间中一一枚举每个可能的解。
这里需要注意的是：一、解空间必须覆盖问题的全部解。
二、解空间集合及问题的集合一定是离散的，简单的说就是集合中的元素是可列的、有限的。
------------------------------------------------------------------------------------------------------------------
问题分析：假设TOM的5本书进行编号{ 1，2，3，4，5 }，每个同学可借到的书的范围就限定在 { 1，2，3，4，5}中，因此TOM的借书方案不肯能超过5*5*5=125种，所以，这125种借书方案可以构成的解空间为{（ x1, x2, x3 ）| 1<= xi <= 5 , 且 x1 != x2 != x3 }
由上所述，可以得到该算法为：
for( i = 1; i <= 5; i++ )
for( j = 1; j <= 5; j++ )
for( k = 1; k <= 5; k++ )
if( i != j && j != k && i != k )
所以程序完整代码如下：
#include "stdio.h"
int main()
{
int i,j,k;
int enter = 0;
printf("There are differnet methods for TOM to distribute his book to A,B,C\n");
for( i = 1; i <= 5; i++ )
for( j = 1; j <= 5; j++ )
for( k = 1; k <= 5; k++ )
if( i != j && j != k && i != k )
{
enter++;
printf("(%d,%d,%d)",i,j,k);
if( enter == 10 )
{
printf("\n");
enter = 0;
}
}
return 0;
}
每次的理解都不一样 LNH_Sniper 发表于 2011-7-9 20:12 static/image/common/back.gif
首先，穷举法是最为简单，也是最为直接，同时又是最为耗时的一种解决实际问题的算法思想。
穷诀法的基本 ...
for( i = 1; i <= 5; i++ )
for( j = 1; j <= 5; j++ )
if(i!=j)
for( k = 1; k <= 5; k++ )
if( j != k && i != k )
这样写的话能减少循环次数
这是离散数学里面的鸽巢原理 5!/(5-3)!用代码 很简单的:lol:
页:
[1]