剑客决斗算法课设分享（三种方法）

题目

在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。n个人站成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A比B强，B比C强，C比A强。如果A和B先决斗，C最终会赢，但如果B和C决斗在先，则最后A会赢。显然，他们三人中的第一场决斗直接影响最终结果。

假设现在n个人围成一个圈，按顺序编上编号1~n。一共进行n-1场决斗。第一场，其中一人（设i号）和他右边的人（即i+1号，若i=n，其右边人则为1号）。负者被淘汰出圈外，由他旁边的人补上他的位置。已知n个人之间的强弱关系（即任意两个人之间输赢关系）。如果存在一种抽签方式使第k个人可能胜出，则我们说第k人有可能胜出，我们的任务是根据n个人的强弱关系，判断可能胜出的人数。

输入
第一行是一个整数N(1<=N<=20)表示测试数据的组数。
第二行是一个整数n表示决斗的总人数。(2<=n<=500)
随后的n行是一个n行n列的矩阵，矩阵中的第i行第j列如果为1表示第i个人与第j个人决斗时第i个人会胜出，为0则表示第i个人与第j个人决斗时第i个人会失败。
输出
对于每组测试数据，输出可能胜出的人数，每组输出占一行
样例输入
1
3
0 1 0
0 0 1
1 0 0
样例输出
3

变相动态规划代码

#include<stdio.h>
#include<string.h>
const int N = 100;
int victory[N][N];//A能否打败B
int flag[N];//A是否能赢到最后
int main()
{
	int k;
	int sum = 0;
	scanf_s("%d", &k);
	while (k--) {
		int n;
		scanf_s("%d", &n);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf_s("%d", &victory[i][j]);
			}
		}
		for (int i = 0; i < n; i++)
			flag[i] = 1;

		for (int i = 0; i < n; i++)
		{
			for (int j = i; j < n + i; j++)
			{
				if (i == j)
					continue;
				if (victory[i][j % n] == 1)
				{
					continue;
				}
				else
				{
					if ((victory[i][(j - 1 + n) % n] == 1 && victory[(j - 1 + n) % n][j % n] == 1) || (victory[i][(j + 1) % n] == 1 && victory[(j + 1) % n][j % n] == 1))
						victory[i][j % n] = 1;//假设此次循环的是B相关，B能打败C，但是B不能打败D，可C能打败D，所以在判断的时候B是否能打败D的时候，首先B不能打败D，其次B能打败C，再者C能打败D，所以得出结论B能打败D。

//另一种判断情况是，B能打败D，但是B不能打败C，可D能打败C，由此判断出B能打败C。

				}
			}
		}
//上面的循环判断的是B右边的情况，下面的循环判断的是B左边即A的情况
		for (int i = n/2; i < n; i++)
		{
			for (int j = i; j >=0; j--)
			{
				if (i == j)
					continue;
				if (victory[i][j % n] == 1)
				{
					for (int m = 1; j - m >= 0; m++) {
						if (victory[i][(j - m + n) % n] == 0 && victory[j % n][(j - m + n) % n] == 1)
							victory[i][(j - m + n) % n] = 1;
//假设D能打败C，C能打败A，B，可是A，B谁都打不过，仅依靠上面的循环并不能证明D能打败A，B，于是此刻判断D的左边，此时不断往前递推，由于D没有表示能打败B，D能打败C，C能打败B，所以D能打败B，同理，由于C也能打败A，递推回去D也能打败A。
					}
				}
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i != j && victory[i][j] != 1) flag[i] = 0;  //判断victory数组，如果一个人的victory数组除了自己本身以外都显示打得过，那么他就是有可能获胜的。
			}
		}
		for (int i = 0; i < n; i++)
		{
			if ((flag[i] == 0 && victory[i][(i + 1) % n] == 1 && flag[(i + 1) % n] == 1) || (flag[i] == 0 && victory[i][(i - 1) % n] == 1 && flag[(i - 1) % n] == 1))
				flag[i] = 1;//这里还有一种情况，那就是如果B没有判断出可能胜出，但是A或C判断出来可能胜出，且B打得过A或C，那么B就是也可能胜出的
		}


		for (int i = 0; i < n; i++)
		{
			if (flag[i] == 1) sum++;
		}
		printf("可能获胜的人数为：%d人", sum);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

递归代码

#include<stdio.h>
#include<string.h>
int f(int i, int j, int k);
int victory[500][500];
int dp[500][500][2];
int n;
int main()
{
	int k;
	scanf_s("%d", &k);
	while (k--)
	{
		int sum = 0;
		memset(dp, -1, sizeof(dp));
		scanf_s("%d", &n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				scanf_s("%d", &victory[i][j]);	
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < i + n; j++)
				if (victory[i][j % n] && f(i + 1, j, 1) && f(j, i - 1 + n, 0))
				{
					sum++; break;
				}
		printf("%d\n",sum);
	}
	return 0;
}
int f(int i, int j, int k)
{
	if (i == j)
		return 1;
	if (i + 1 == j)

		return k ? victory[j % n][i % n] : victory[i % n][j % n];
	if (dp[i % n][j % n][k] != -1)	
		return dp[i % n][j % n][k];
	dp[i % n][j % n][k] = 0;
	if (!k)
	{
		for (int m = i + 1; m <= j; m++)
			if (victory[i % n][m % n])
			{
				dp[i % n][j % n][k] = f(i + 1, m, 1) && f(m, j, 0);
				if (dp[i % n][j % n][k])	break;
			}
	}
	else
	{

		for (int m = i; m <= j - 1; m++)
			if (victory[j % n][m % n])
			{
				dp[i % n][j % n][k] = f(i, m, 1) && f(m, j - 1, 0);
				if (dp[i % n][j % n][k])	break;
			}
	}
	return dp[i % n][j % n][k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

AC代码（动态规划）

#include<stdio.h>
int victory[100][100];
int meet[100][100];
int main() {
	int t;
	scanf_s("%d", &t);
	while (t--)
	{
		int n;
		scanf_s("%d", &n);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf_s("%d", &victory[i][j]);
			}
		}
		for (int i = 0; i < n; i++)
		{
			meet[i][(i + 1)%n] = 1;//初始时刻相邻的两个人是可以遇见的
		}
		for (int distance = 2; distance <= n; distance++) {
			for (int i = 0; i < n; i++)
			{
				int j = i + distance;
				for (int k = i + 1; k < j; k++)
				{
					if (meet[i][k % n] && meet[k % n][j%n] && (victory[i][k % n] || victory[j][k % n])) {
						meet[i][j % n] = 1;
						break;
					}
				}
			}
		}
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			if (meet[i][i])
				sum++;
		}
		printf("%d", sum);
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

变相动态规划思路

首先设置了victory二维数组用于存储用户输入的剑客间的胜负信息，设置flag一维数组作为最后剑客是否胜利的判断标志，开始的是否flag数组全部置为1以便后期的更改。

此算法的思路是，从每一个剑客的角度，使他一一和其他剑客进行决斗，如果最后决斗结果表明他能够打败除了自己以外的其他所有人则证明他有可能赢到最后。

在比较的过程中，不断更改victory数组，即更改剑客们之间的胜负关系，如果剑客可以打败下一个剑客则继续循环，如果不可以我们就要开始进行判断，判断情况有以下几种：

首先，如果剑客A不能打败剑客B，但是剑客A可以打败剑客C，剑客C可以打败剑客B，那么我们就可以将A与B的关系更改为A可以打败B。

同样，如果剑客A不能打败剑客C，但是剑客B可以打败剑客C，剑客A可以打败剑客B，我们就可以将A与C的关系更改为A能够打败C。

还有，如果剑客D可以打败剑客C，但是不能打败剑客A和B，但是C可以打败A和B，由于A与B与D的关系都为D不能打败它们，所以仅靠上面两种情况的判断我们是无法得到D可以获胜的，因此我添加了反方向的递推，此刻不再是一个一个比较，就这个例子来说，C可以打败B，也可以打败A，那么便一直从B往左递推，直到C无法战胜为止，而C能够战胜的我们把它与D的关系都变为D能战胜它。

最后，还有一个判断，如果A能够打败B，而B有可能获胜，那么我们认为A也是有可能获胜的。

更改了所有的victory数组以后，我们进行循环判断，如果一个人的victory数组除了它本身以外都是1，那么我们就认定这个人有可能获胜，sum++，最终输出。

递归思路

递归法的原理相较于蛮力法和动态规划法来说是比较简单的，但是实现起来却是最困难的，它同样利用二维数组victory储存信息，dp三维数组用来记录剑客之间的胜负关系。

本算法的基本思想是针对每一个剑客进行遍历，如果其存在一个手下败将可以打败其他所有人，那么这个剑客就有可能获胜。

本算法着重于f条件的判断，f（i，j，0）表示i可以打败j，f（i，j，1）表示j可以打败i，如果i等于j，那么不管后面是0还是1都直接返回1，因为自己与自己的胜负是没有意义的，如果i+1=j，说明两人是相邻的，直接判断victory数组就好，此时为k赋值，为我们进行下一步判断。

F函数最终需要的是dp的值，我们为dp赋值为-1，在使用它的时候将它初始化为0，如果dp不为-1说明它已经被更改过，我们直接返回就好。

如果k=0，说明我们要判断i是否能战胜j，此时对i与j之间的数进行遍历，取中间值m，如果i能战胜m且m能够战胜直到j的所有剑客，我们就认为i是可以战胜j的。同理，如果k=1，说明我们要判断j是否能够战胜i，同样找中间数m使其等于i，一直遍历到j-1，判断j是否能战胜m，j一直可以战胜m，则返回1，否则返回0。

通过不断递归，最终我们可以得到理想的结果。

AC思路

设置了victory二维数组存储各剑客之间的胜负关系，再设置meet二维数组存储各剑客是否能够遇见。

此算法的思想是如果一个剑客能够战胜身边的人，就能够遇见下一个人，不断循环如果最后他能够遇见他自己，证明他打败了所有人，此时我们就可以认为这个人获胜了。

首先输入数据，设置循环为meet数组赋初值，开始的时候只有相邻的人之间的meet为1，其他人之间的meet都为0。依然是以个人为例，我们先设置剑客之间的距离，再对所有的剑客依次进行遍历，以距离为准判断他们能否与和自己相距这个距离的人遇见，最终距离设为n，如果这个时候还能遇见也就是和自己遇见。

我们判断是否能与跟自己相距这个距离的人遇见的标准是，第i个人和第j个人之间是否存在第k个人，使得i能遇见k，且k能遇见j，且i能打败k或者j能打败k，如果能找到这样的人的话，我们就把i与j的meet数组置为1，表示i和j是能够遇见的，然后所有的人都经过一次这样的遍历后，distance增加，继续遍历，最终我们可以得到正确的结果。

easyx界面代码

void menu() {
	initgraph(400, 600, EW_SHOWCONSOLE);
	ExMessage m;
	IMAGE img1, img2, img3, img4, img5;
	loadimage(&img1, _T("剑客决斗.png"), 400, 600);
	loadimage(&img2, _T("剑客决斗蓝.png"), 400, 600);
	loadimage(&img3, _T("说明.png"), 400, 600);
	putimage(0, 0, &img1);
	int flag = 0;
	int start = 0;
	while (!start) {
		m = getmessage(EM_MOUSE);
		if (m.x >= 40 && m.x <= 560 && m.y >= 250 && m.y <= 350) {
			flag = 1;
			if (m.message == WM_LBUTTONDOWN)
				start = 1;
		}
		else flag = 0;
		if(flag==1)
			putimage(0, 0, &img2);
		else 
			putimage(0, 0, &img1);
	}
	putimage(0, 0, &img3);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

界面效果

感想

通过这次课设，使自己的算法能力得到了提高，最后答辩的时候老师给的建议也很宝贵，继续加油吧！