C语言经典例题|【C语言典例】——day8（猜名次） C语言经典例题|c语言

※※※大家好！我是同学〖森〗，一名计算机爱好者，今天让我们进入刷题模式。若有错误，请多多指教。点赞 ? 收藏留言都是我创作的最大的动力！

题目描述

5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
A选手说：B第二，我第三；
B选手说：我第二，E第四；
C选手说：我第一，D第二；
D选手说：C最后，我第三；
【C语言经典例题|【C语言典例】——day8（猜名次）】E选手说：我第四，A第一；
比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。

问题解析

1、建造一个数字p【5】表示A B C D E.
2、用for循环来猜每一个人的名次，共5人，5个名次，需要5个循环，每个循环代表一个人，每个循环循环5次，表示5个名次。
3、每个人的描述都说对了一半，由于比较表达式只有0和1两个结果，可以用比较表达式的值总和为1的方式直接判定。例如：A说：（p【1】== 2）+ （p【0】 == 3）==1
4、五个人的说的话都是半错半对，所以要同时成立，用&&。
5、写一个子函数判断是否有同名次。
6、输出结果。

程序源码

#include int main() { int p[5]; //0 1 2 3 4分别代表a b c d e for (p[0] = 1; p[0] <= 5; p[0]++) { for (p[1] = 1; p[1] <= 5; p[1]++) { for (p[2] = 1; p[2] <= 5; p[2]++) { for (p[3] = 1; p[3] <= 5; p[3]++) { for (p[4] = 1; p[4] <= 5; p[4]++) //五层循环遍历 { //这里是五个人的描述，由于比较表达式只有0和1两个结果， //如果要两个条件有且只有一个为真，则可以用比较表达式的值总和为1的方式直接判定。别忘了还要判定不能并列。 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第一 (p[0] * p[1] * p[2] * p[3] * p[4]) == 120 //不能并列 ) { printf("A B C D E\n"); for (int i = 0; i < 5; i++) { printf("%d ", p[i]); }putchar('\n'); } } } } } } return 0; }

运行结果

文章图片

算法优化

用全排列即从1到5，减少了比较次数能，能减少程序的运行时间，时间复杂度由由O(n^n)降低为O(n!)。遍历速度上达到了一个新的高度，这种遍历大大减少了遍历的次数，极大的提升了效率。

#include void swapArgs(int* a, int* b) //交换函数 { int tmp; tmp = *a; *a = *b; *b = tmp; }void diveRank(int* p, int n) { for (int i = 0; i < 5; i++) //这个递归方式就完成了对1~5的全排列，方法是从后向前不停的执行交换。可以参考改进二和原代码，将这个递归程序写回成循环后，可以更好的理解。 { swapArgs(p + i, p ); for (int j = 1; j < 5; j++) { swapArgs(p + j, p + 1); for (int z = 2; z < 5; z++) { swapArgs(p + z, p + 2); for (int x = 3; x < 5; x++) { swapArgs(p + x, p + 3); 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) { printf("A B C D E\n"); for (int n = 0; n < 5; n++) { printf("%d ", p[n]); } putchar('\n'); }swapArgs(p + x, p + 3); } swapArgs(p + z, p + 2); } swapArgs(p + j, p + 1); } swapArgs(p + i, p); } }int main() { int a[5] = { 1, 2, 3, 4, 5 }; //当然由于是全排列，所以初值必须给好。 diveRank(a, 0); return 0; }

那有人可能就问了，那代码能不能再简化点？
没错让我们用递归来写。
递归优化

#include void swapArgs(int* a, int* b) //交换函数 { int tmp; tmp = *a; *a = *b; *b = tmp; }void diveRank(int* p, int n) { if (n >= 4) //此时的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第一 //由于此时是执行的全排列，所以查重也省了。 { printf("A B C D E\n"); 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; }