[交流]应用全排序算法解决一道逻辑推理题
全排序算法就是列举一些字符的所有排列顺序的一种算法，比较典型的采用递归法。下面是一种简单的全排序算法。
void Swap(char* a, char* b)
{// 交换a和b
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void Perm(char list[], int k, int m)
{ //生成list [k：m ]的所有排列方式
int i;
if (k == m) {//输出一个排列方式
for (i = 0; i <= m; i++)
putchar(list[i]);
putchar( '\n ');
}
else // list[k：m ]有多个排列方式
// 递归地产生这些排列方式
for (i=k; i <= m; i++) {
Swap (&list[k], &list[i]);
Perm (list, k+1, m);
Swap (&list [k], &list [i]);
}
}
int main(int argc, char *argv[])
{
char s[6]= "01234 ";
Perm(s,0,4);
return 0;
}
算法作者：拉格浪日，来源：燕赵草叶风 2006-7-1
下面我简单地应用这个算法解决一道推理问题。该推理是这样的：
一天晚上，一对已婚夫妇，和他们的儿子女儿在家里发生了一起谋杀案，凶手、帮凶、被害人和目击者分别是家里的人。情况如下：
（1）目击者和那个帮凶不是同一性别
（2）年龄最大的和目击者不是同一性别
（3）年龄最轻的和被害人不是同一性别
（4）帮凶比受害者大
（5）父亲是年龄最长者
（6）凶手不是家中最年轻的成员
凶手、帮凶、被害人和目击者分别是谁？
算法的基本思路是：定义两个数组，一个数组表示家庭成员，另一个数组表示他们可能扮演的角色。当找出一种排列方式，然后一个数组对另一个数组赋值，如符合题目条件，则进行输出。
代码如下：
#include <string.h>
#include <iostream.h>
struct Person
{
char szName[20];
bool Sex; // true 表示男，false表示女
int age; // 定义年龄
};
void Swap(char* a, char* b)
{// 交换a和b
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void Perm(char list[],Person Familys[],Person Characters[], int k, int m)
{
int i = 0;
if (k == m) {
for (i = 0; i <= m; i++)
{
Characters[i] = Familys[(list[i]-48)];
}
// 假如符合题目条件
if((Characters[1].Sex!=Characters[3].Sex) // 目击者和那个帮凶不是同一性别
&&(Familys[0].Sex!=Characters[3].Sex) //年龄最大的和目击者不是同一性别
&&(Familys[3].Sex!=Characters[2].Sex) // 年龄最轻的和被害人不是同一性别
&&(Characters[1].age> Characters[2].age)// 帮凶比受害者大
&&(Characters[0].age> 20) // 凶手不是家中最年轻的成员
)
{
cout < < "murderer: " < <Characters[0].szName < <endl;
cout < < "accessary: " < <Characters[1].szName < <endl;
cout < < "be murdered: " < <Characters[2].szName < <endl;
cout < < "the age of be murdered: " < <Characters[2].age < <endl;
cout < < "eyewitness: " < <Characters[3].szName < <endl;
cout < < "the age of eyewitness: " < <Characters[3].age < <endl;
cout < <endl;
}
}
else
{
// 递归地产生这些排列方式
for (i=k; i <= m; i++)
{
Swap(&list[k], &list[i]);
Perm(list, Familys,Characters,k+1, m);
Swap (&list [k], &list [i]);
}
}
}
int main(int argc, char* argv[])
{
// 定义一个家庭数组,Familys[0]为父亲,Familys[1]为母亲，Familys[2]为子女中年龄大的一个，Familys[3]为子女中年龄小的一个
Person Familys[4];
// 初始化数组成员，
strcpy(Familys[0].szName, "Father ");
Familys[0].Sex = true;
Familys[0].age = 50;
strcpy(Familys[1].szName, "Mother ");
Familys[1].Sex = false;
Familys[1].age = 40;
// 首先假设儿子的年龄比女儿要大
strcpy(Familys[2].szName, "Son ");
Familys[2].Sex = true;
Familys[2].age = 30;
strcpy(Familys[3].szName, "Daughter ");
Familys[3].Sex = false;
Familys[3].age = 20;
// 定义一个角色数组,Characters[0]为,Characters[1]为帮凶，Characters[2]为被害人，Characters[3]为目击者
Person Characters[4];
char s1[5]= "0123 ";
Perm(s1,Familys,Characters,0,3);
char s2[5]= "0123 ";
// 其次假设儿子的年龄比女儿要小
strcpy(Familys[2].szName, "Daughter ");
strcpy(Familys[3].szName, "Son ");
Familys[2].Sex = false;
Familys[3].Sex = true;
Perm(s2,Familys,Characters,0,3);
return 0;
}
编译环境：VC6.0 WinXp sp2
[解决办法]
void Swap(char* a, char* b)
{// 交换a和b
char temp;
temp = *a;
*a = *b;
*b = temp;
}
===============================
void Swap(char* a, char* b)
{// 交换a和b
a ^= b;
b ^= a;
a ^= b;
}
这样效率会更高,而且不使用临时变量
[解决办法]
你还是为你的Person类提供构造、==/!=、输出流运算符 < <吧。代码现在太累赘了。
