算法每日一题（六）—___穷举法

LNH_Sniper

问题：TOM共有5本新书，要借给A、B、C3位同学，每人只能借一本书，则TOM可以有多少种不同的借书方**

提示：本题目是典型的穷举法的应用，属于简单题

asd82937121

最多能借一本  最少可不可以不借

LNH_Sniper

asd82937121 发表于 2011-7-9 08:13

                               
登录/注册后可看大图

最多能借一本  最少可不可以不借

不可以不借

asd82937121

恩  这题挺锻炼思想的  实际上是吧实际问题转化为抽象的概念， 这个问题和彩票选数差不多  每个数字是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也可以得到答案，不过这就和编程没什么关系了。

LNH_Sniper

首先，穷举法是最为简单，也是最为直接，同时又是最为耗时的一种解决实际问题的算法思想。

穷诀法的基本思想是:在可能的解空间中穷举出每一种肯能的解，并对每个可能的解进行判断，从中得到答案。

其中最关键步骤是：划定问题的解体空间，并在该解空间中一一枚举每个可能的解。
这里需要注意的是：一、解空间必须覆盖问题的全部解。
                           二、解空间集合及问题的集合一定是离散的，简单的说就是集合中的元素是可列的、有限的。
------------------------------------------------------------------------------------------------------------------

问题分析：假设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;
}

Be_envious

每次的理解都不一样

wangyexin

LNH_Sniper 发表于 2011-7-9 20:12

                               
登录/注册后可看大图

首先，穷举法是最为简单，也是最为直接，同时又是最为耗时的一种解决实际问题的算法思想。

穷诀法的基本 ...

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: