【题目】
学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
【算法分析】
可用穷举法，先不考虑“每人都满意” 这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有5！=120种。然后在120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。
为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如54321就表示第5本书（即E）分给张，第4本书（即D）分给王，……，第1本书（即A）分给李。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。
算法设计：S1：产生5个数字的一个全排列；
S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来；
S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1；
S4：结束。
【改进】
上述算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，选第一本书即给张同学的书，1是不可能的，因为张只喜欢第3、4本书。这就是说，1××××一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不必选了，这样就减少了运算量。换句话说，第一个数字只在3、4中选择，这样就可以减少3/5的运算量。同理，选定了第一个数字后，也不应该把其他4个数字一次选定，而是选择了第二个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。
综上所述，
改进后的算法应该是：
在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的，所以可以用回溯算法。
【算法设计】
代码(雾)：
int Search(i) { for (j=1;j<=5;j++) { if (第i个同学分给第j本书符合条件) { 记录第i个数 if (i==5) 打印一个解; else Search(i+1); 删去第i 个数 } } }
代码(真)：
#include<iostream> #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<string> #include<cmath> using namespace std; int book[6],k=0;//方案,k为第几种 bool x[6]= {0}; //是否可用 bool like[6][6]= {{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,0,0,1}, {0,0,1,1,0,0},{0,0,0,0,1,0},{0,0,1,0,0,1}}; //存放喜欢情况，1为喜欢 int print() { k++;//k为第几个 cout<<k<<" "; for(int j=1; j<=5; j++) { cout<<j<<":"<<char(64+book[j])<<" ";//转换为字符型,容易看 } cout<<endl; } int search(int i) { for(int j=1; j<=5; j++) { if(!x[j]&&like[i][j]) { x[j]=1;//标记不能使用 book[i]=j;//记录下来 if(i==5) print(); else search(i+1); x[j]=0;//回溯 book[i]=0; } } } int main() { search(1);//从第一个开始寻找 return 0; }