小程序答案有缺陷，分书问题
问题描述：学校放寒假时，信息学竞赛教师有A、B、C、D、E共5本书，要分给参加培训的张、王、刘、孙、李5位学生，已知张同学喜爱C和D两本书，王同学喜爱A，B和E三本书，刘同学喜爱B和C两本书，孙同学喜爱D这本书，李同学喜爱B和E两本书，每人只能选1本书。编写程序帮助教师求出所有可能的分书方案，使得每个学生都满意。
八皇后 递归回溯 分书问题
#include <stdio.h>
int num[1000][5]={0};
int j=0;
int chenggong(int a[],int n)
{
int m; //如果不加这三行能正常运行，但不能排除分到重复的书
for(m=0;m<n;m++) //例如：31242 这种情况，不符合题目要求
if(a[m]==a[n]) break; //但加上这三行，也能正常运行，但无解。
if(m==n)
{
switch(n)
{
case 0:
{
if(a[n]==3||a[n]==4) return 1;
else return 0;
break;
}
case 1:
{
if(a[n]==1||a[n]==2||a[n]==5) return 1;
else return 0;
break;
}
case 2:
{
if(a[n]==2||a[n]==3) return 1;
else return 0;
break;
}
case 3:
{
if(a[n]==4) return 1;
else return 0;
break;
}
case 4:
{
if(a[n]==2||a[n]==5) return 1;
else return 0;
break;
}
}
}
else return 0;
}
int fenshu(int a[],int n) //类似于八皇后的解法，分别用12345表示ABCDE五本书
{
int i,k;
for(i=1;i<=5;i++)
{
a[n]=i;
if(chenggong(a,n))
{
if(n==5)
{
for(i=0;i<5;i++)
num[j][i]=a[i];
j++;
}
else fenshu(a,n+1);
}
}
}
int main()
{
int a[5]={1,1,1,1,1};
int i,k;
fenshu(a,0);
for(i=0;i<j;i++)
{
for(k=0;k<5;k++)
printf("%d ",num[i][k]);
printf("\n");
}
return 0;
}
为了让大家都能满意，所以
->孙同学D书->张同学C书->刘同学B书->李同学E书->王同学A书
//学校放寒假时，信息学竞赛教师有A、B、C、D、E共5本书，要分给参加培训的张、王、刘、孙、李5位学生，
//已知张同学喜爱C和D两本书，王同学喜爱A，B和E三本书，刘同学喜爱B和C两本书，孙同学喜爱D这本书，李同学喜爱B和E两本书，
//每人只能选1本书。编写程序帮助教师求出所有可能的分书方案，使得每个学生都满意。
#include <stdio.h>
#include <locale.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int i,n;
setlocale(LC_ALL,"chs");
vector<char> P(5);
vector<char>::iterator b,e;
b=P.begin();
e=P.end();
for (i=0;i<5;i++) P[i]='A'+i;
n=0;
do {
if ((P[0]=='C'
[解决办法]
P[0]=='D')
&& (P[1]=='A'
[解决办法]
P[1]=='B'
[解决办法]
P[1]=='E')
&& (P[2]=='B'
[解决办法]
P[2]=='C')
&& (P[3]=='D')
&& (P[4]=='B'
[解决办法]
P[4]=='E')) {
printf("%2d: ",++n);
for(i=0;i<5;i++) printf("%.2s%c","张王刘孙李"+i*2,P[i]);
printf("\n");
}
} while (next_permutation(b,e));
printf("The total: %d",n);
return 0;
}
// 1: 张C王A刘B孙D李E
//The total: 1
