朱金灿 全排序算法就是列举一些字符的所有排列顺序的一种算法，比较典型的采用递归法。下面是一种简单的全排序算法。 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; } 其实在STL的next_permutation泛型算法已经实现了全排序，因此更为方便的做法是直接调用这个算法，代码如下： #include <iostream> #include <vector> #include <string> #include <algorithm> #include <functional> using namespace std; class Person { public: Person(); Person(Person &Other); bool CompareAge(Person &Other); bool CompareAge(int nAge); bool CompareSex(Person &Other); void operator << (int nIndex); void operator = (Person &Other); void Initial(char *pszName,bool bSex,int nAge); void ChangeAge(int NewAge); private: char m_szName[20]; bool m_Sex; // true 表示男，false表示女 int m_Age; // 定义年龄 }; Person::Person() { } void Person::Initial(char *pszName,bool bSex,int nAge) { strcpy(m_szName,pszName); m_Sex = bSex; m_Age = nAge; } void Person::operator =(Person &Other) { strcpy(m_szName,Other.m_szName); m_Sex = Other.m_Sex; m_Age = Other.m_Age; } bool Person::CompareAge(Person &Other) { if(m_Age>Other.m_Age) return true; else return false; } bool Person::CompareAge(int nAge) { if(m_Age>nAge) return true; else return false; } bool Person::CompareSex(Person &Other) { if(m_Sex!=Other.m_Sex) return true; else return false; } void Person::ChangeAge(int NewAge) { m_Age = NewAge; } void Person::operator <<(int nIndex) { switch(nIndex) { case 0: cout<<"murderer: "<<m_szName<<endl; break; case 1: cout<<"accessary: "<<m_szName<<endl; break; case 2: cout<<"be murdered: "<<m_szName<<endl; cout<<"the age of be murdered: "<<m_Age<<endl; break; case 3: cout<<"eyewitness: "<<m_szName<<endl; cout<<"the age of eyewitness: "<<m_Age<<endl; break; default: break; } } void GetMurderer(Person Familys[]) { vector<char> s1(4); int i =0; s1[0] = '0'; s1[1] = '1'; s1[2] = '2'; s1[3] = '3'; Person Characters[4]; for (i = 0; i <= 3; i++) { Characters[i] = Familys[(s1[i]-48)]; } if(Characters[1].CompareSex(Characters[3])// 目击者和那个帮凶不是同一性别 &&(Familys[0].CompareSex(Characters[3]))//年龄最大的和目击者不是同一性别 &&(Familys[3].CompareSex(Characters[2])) // 年龄最轻的和被害人不是同一性别 &&(Characters[1].CompareAge(Characters[2]))// 帮凶比受害者大 &&(Characters[0].CompareAge(20)) // 凶手不是家中最年轻的成员 ) { Characters[0]<<0; Characters[1]<<1; Characters[2]<<2; Characters[3]<<3; cout<<endl; } vector<char>::iterator start; start = s1.begin(); vector<char>::iterator end; end = s1.end(); while ( next_permutation(start,end)) { for (i = 0; i <= 3; i++) { Characters[i] = Familys[(s1[i]-48)]; } // 假如符合题目条件 if(Characters[1].CompareSex(Characters[3])// 目击者和那个帮凶不是同一性别 &&(Familys[0].CompareSex(Characters[3]))//年龄最大的和目击者不是同一性别 &&(Familys[3].CompareSex(Characters[2])) // 年龄最轻的和被害人不是同一性别 &&(Characters[1].CompareAge(Characters[2]))// 帮凶比受害者大 &&(Characters[0].CompareAge(20)) // 凶手不是家中最年轻的成员 ) { Characters[0]<<0; Characters[1]<<1; Characters[2]<<2; Characters[3]<<3; cout<<endl; } } } int main(int argc, char* argv[]) { // 定义一个家庭数组,Familys[0]为父亲,Familys[1]为母亲，Familys[2]为子女中年龄大的一个，Familys[3]为子女中年龄小的一个 Person Familys[4]; Familys[0].Initial("Father",true,50); Familys[1].Initial("Mother",false,40); Familys[2].Initial("Son",true,30); Familys[3].Initial("Daughter",false,20); GetMurderer(Familys); // 交换儿子和女儿 Familys[2].ChangeAge(20); Familys[3].ChangeAge(30); Person tmpPerson; tmpPerson = Familys[2]; Familys[2] = Familys[3]; Familys[3] = tmpPerson; GetMurderer(Familys); return 0; } 编译环境：VC6.0 WinXp sp2 运行结果如下：
评论