题目要求：
5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
A选手说：B第二，我第三；
B选手说：我第二，E第四；
C选手说：我第一，D第二；
D选手说：C最后，我第三；
E选手说：我第四，A第一；
比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。
正常思路：
通过五层循环，尝试25种不同的结果
出现两个人抢名次的情况，也就是两个人或者更多的人名次相同的情况，例如两个第二，三个第三这样的，所以即使满足了条件，也要查看一下五个人的名次是否重复
这个交给一个函数来执行，只要五个人名次并列，那就返回0，否则返回1即可。
#include<stdio.h> int check_date(int* arr)//查重，如果没用重复的返回1，有重复的返回0 { int temp[6] = { 0 };定义的范围要大于形参 for (int i = 0; i < 5; i++) { if (temp[arr[i]]==1) { return 0; } temp[arr[i]] = 1; } return 1; } int main() { int arr[5]; int flag = 0; for ( arr[0] = 1; arr[0] <= 5; arr[0]++) { for ( arr[1] = 1; arr[1] <= 5; arr[1]++) { for ( arr[2] = 1; arr[2] <= 5; arr[2]++) { for ( arr[3] = 1; arr[3] <= 5; arr[3]++) { for ( arr[4] = 1; arr[4] <= 5; arr[4]++) { int count = 0; if ((arr[1] == 2) + (arr[0] == 3) == 1 && (arr[1] == 2) + (arr[4] == 4) == 1 && (arr[2] == 1) + (arr[3] == 2) == 1 && (arr[2] == 5) + (arr[3] == 3) == 1 &&(arr[4] == 4) + (arr[0] == 1) == 1) { if(check_date(arr)==1) printf("%d %d %d %d %d\n", arr[0], arr[1], arr[2], arr[3], arr[4]); } } } } } } return 0; }
查重函数的升级
检查是否重复的过程，我们是用一个数组来做的，实际每个标签只有0和1两种可能，没必要一定要用数组做，可以考虑用一个位来做（哈希中的位图），代码如下：
int checkData(int *p) { char tmp = 0; int i; for (i = 0; i < 5; i++) { tmp |= 1 << p[i]; //tmp每次或上一位1，p[i]如果是1~5都有，则1<<1到1<<5都或上的结果将会是00111110，如果有并列，则一定会至少却其中一个1，结果就不会是00111110，所以可以判断tmp最终的结果是不是这个数字来判断有没有重复。 } return tmp == 0x3E; }
大牛操作：使用递归函数
void diveRank(int * p, int n) { if(n >= 5) //此时的n是用来控制循环层数的。 { if ((p[1] == 2) + (p[0] == 3) == 1 && //B第二，我第三 (p[1] == 2) + (p[4] == 4) == 1 && //我第二，E第四 (p[2] == 1) + (p[3] == 2) == 1 && //我第一，D第二 (p[2] == 5) + (p[3] == 3) == 1 && //C最后，我第三 (p[4] == 4) + (p[0] == 1) == 1 && //我第四，A第一 checkData(p)) //查重 { for (int i = 0; i < 5; i++) { printf("%d ", p[i]); } putchar('\n'); } return; } for(p[n] = 1; p[n] <= 5; p[n]++) { diveRank(p, n + 1); //通过递归模拟多层循环，每进一次递归相当于进了一层新的循环。 } } int main() { int p[5]; diveRank(p, 0); return 0; }
再次升级：
#include <stdio.h> void swapArgs(int * a, int * b) //交换函数 { int tmp; tmp = *a; *a = *b; *b = tmp; } void diveRank(int * p, int n) { if(n >= 5) //此时的n也是用来控制循环层数的。 { if ((p[1] == 2) + (p[0] == 3) == 1 && //B第二，我第三 (p[1] == 2) + (p[4] == 4) == 1 && //我第二，E第四 (p[2] == 1) + (p[3] == 2) == 1 && //我第一，D第二 (p[2] == 5) + (p[3] == 3) == 1 && //C最后，我第三 (p[4] == 4) + (p[0] == 1) == 1) //我第四，A第一 //由于此时是执行的全排列，所以查重也省了。 { for (int i = 0; i < 5; i++) { printf("%d ", p[i]); } putchar('\n'); } return; } int i; for(i = n; i < 5; i++) //这个递归方式就完成了对1~5的全排列，方法是从后向前不停的执行交换。可以参考改进二和原代码，将这个递归程序写回成循环后，可以更好的理解。 { swapArgs(p + i, p + n); diveRank(p, n + 1); swapArgs(p + i, p + n); } } int main() { int p[5] = { 1, 2, 3, 4, 5 }; //当然由于是全排列，所以初值必须给好。 diveRank(p, 0); return 0; }
