C语言写类似于约瑟夫环的决斗问题,急,循环链表!1.决斗【问题描述】n个角斗士被要求进行生死决斗.规则是:所有人围成一圈,按照一定的顺序拉人,被拉出的角斗士就和紧靠其右的人决斗,失
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/18 12:01:34
![C语言写类似于约瑟夫环的决斗问题,急,循环链表!1.决斗【问题描述】n个角斗士被要求进行生死决斗.规则是:所有人围成一圈,按照一定的顺序拉人,被拉出的角斗士就和紧靠其右的人决斗,失](/uploads/image/z/8511370-34-0.jpg?t=C%E8%AF%AD%E8%A8%80%E5%86%99%E7%B1%BB%E4%BC%BC%E4%BA%8E%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF%E7%9A%84%E5%86%B3%E6%96%97%E9%97%AE%E9%A2%98%2C%E6%80%A5%2C%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8%211.%E5%86%B3%E6%96%97%E3%80%90%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0%E3%80%91n%E4%B8%AA%E8%A7%92%E6%96%97%E5%A3%AB%E8%A2%AB%E8%A6%81%E6%B1%82%E8%BF%9B%E8%A1%8C%E7%94%9F%E6%AD%BB%E5%86%B3%E6%96%97.%E8%A7%84%E5%88%99%E6%98%AF%EF%BC%9A%E6%89%80%E6%9C%89%E4%BA%BA%E5%9B%B4%E6%88%90%E4%B8%80%E5%9C%88%2C%E6%8C%89%E7%85%A7%E4%B8%80%E5%AE%9A%E7%9A%84%E9%A1%BA%E5%BA%8F%E6%8B%89%E4%BA%BA%2C%E8%A2%AB%E6%8B%89%E5%87%BA%E7%9A%84%E8%A7%92%E6%96%97%E5%A3%AB%E5%B0%B1%E5%92%8C%E7%B4%A7%E9%9D%A0%E5%85%B6%E5%8F%B3%E7%9A%84%E4%BA%BA%E5%86%B3%E6%96%97%2C%E5%A4%B1)
C语言写类似于约瑟夫环的决斗问题,急,循环链表!1.决斗【问题描述】n个角斗士被要求进行生死决斗.规则是:所有人围成一圈,按照一定的顺序拉人,被拉出的角斗士就和紧靠其右的人决斗,失
C语言写类似于约瑟夫环的决斗问题,急,循环链表!
1.决斗
【问题描述】
n个角斗士被要求进行生死决斗.规则是:所有人围成一圈,按照一定的顺序拉人,被拉出的角斗士就和紧靠其右的人决斗,失败者的尸体将被抬走(即退出圈子).
研究表明,最终的结果在相当程度上取决于决斗的顺序.可能出现A胜过B,B胜过C,而C又胜过A.因而史学家决定研究哪些角斗士有可能生还.
将这n个角斗士按照从1~n逆时针方向排成一圈,他们要决斗n-1场.其中第i个人与第i+1个人决斗.死者退出圈子,紧靠死者右边的人成为与赢者直接相邻的人.任意两人之间决斗的胜负通过一个矩阵给出——如果A[i][j]=1,表示i能战胜j;如果A[i][j]=-1则表示i打不过j;当i=j时值为0.
【基本要求】
生成胜负关系矩阵A.然后将n个角斗士随机放入一个循环链表中,注意,这n个角斗士有自己的代号,也有在链表中的编号,两者意义不同.若规定从链表的1号开始数数,自行决定一个数字用于从链表中选择角斗士,然后被选出的角斗士和右边的角斗士决斗.胜负关系根据矩阵A决定.之后继续数数,找出下一对需要决斗的对手.
模拟此过程,直到最后一个人.
【输入输出】
输入:角斗士总数fighters.通过随机函数生成胜负关系矩阵A.
输出:按照决斗场次输出决斗结果.
【实现提示】
基本要求降低了题目的难度,因此本题和经典的约瑟夫环基本类似.但如果按照原题的要求,则此题需要求出所有可能赢得整场决斗的人的序号,这就转化成为一个动态规划问题.有志于挑战此动态规划问题的同学可以做选做内容.
有具体模板和实验指导书可发你们!
C语言写类似于约瑟夫环的决斗问题,急,循环链表!1.决斗【问题描述】n个角斗士被要求进行生死决斗.规则是:所有人围成一圈,按照一定的顺序拉人,被拉出的角斗士就和紧靠其右的人决斗,失
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <conio.h>
struct FighterRing {
int id; // 链表编号
char code[32]; // 角斗士代号
struct FighterRing *next;
};
main()
{
int **A, i, j, k, fighters;
struct FighterRing *firstFighter=NULL, *lastFighter=NULL, *newFighter, *loser, *prevFighter;
printf("输入角斗士人数: ");
scanf("%d", &fighters);
srand((unsigned)time(NULL));
// 创建角斗士环
printf("将%d个角斗士加入链表中\n", fighters);
for(i = 0; i < fighters; i++) {
newFighter = (struct FighterRing *)malloc(sizeof(struct FighterRing));
newFighter->id = i+1;
// 随机生成角斗士代号
for(j = 0; j < 20; j++)
newFighter->code[j] = rand()%26+'a';
newFighter->code[j] = 0;
if(firstFighter == NULL) {
firstFighter = lastFighter = newFighter;
firstFighter->next = newFighter;
}
else {
lastFighter->next = newFighter;
lastFighter = newFighter;
newFighter->next = firstFighter;
}
}
printf("生成完毕,他们是:\n");
newFighter = firstFighter;
for(i = 0; i < fighters; i++) {
printf("%d %s\n", newFighter->id, newFighter->code);
newFighter = newFighter->next;
}
printf("开始生成胜负关系矩阵\n");
// 随机生成胜负关系矩阵
A = (int **)malloc(fighters*sizeof(int*));
for(i = 0; i < fighters; i++) {
A[i] = (int *)malloc(fighters*sizeof(int));
}
for(i = 0; i < fighters; i++) {
for(j = i; j < fighters; j++) {
if(i == j)
A[i][j] = 0;
else {
A[i][j] = rand()&1;
if(A[i][j] == 0)
A[i][j] = -1;
A[j][i] = -A[i][j];
}
}
}
for(i = 0; i < fighters; i++) {
for(j = 0; j < fighters; j++)
printf("%3d", A[i][j]);
printf("\n");
}
printf("开始战斗\n");
// 开始战斗
k = fighters;
while(k > 1) {
i = rand() % k;
newFighter = firstFighter;
for(j = 0; j < i; j++) {
prevFighter = newFighter;
newFighter = newFighter->next;
}
printf("%d与%d战斗,", newFighter->id, newFighter->next->id);
// newFighter与newFighter->next 进行角斗
if(A[newFighter->id-1][newFighter->next->id-1] == 1) {
prevFighter = newFighter;
loser = newFighter->next;
}
else {
loser = newFighter;
}
printf("%d死亡!\n", loser->id);
// 将失败者从链表中删除
if(loser == firstFighter) {
firstFighter = loser->next;
lastFighter->next = firstFighter;
}
else if(loser == lastFighter) {
lastFighter = prevFighter;
prevFighter->next = firstFighter;
}
else
prevFighter->next = loser->next;
free(loser);
k --;
}
printf("最终的获胜者是%d %s\n", firstFighter->id, firstFighter->code);
free(firstFighter);
for(i = 0; i < fighters; i++) {
free(A[i]);
}
free(A);
}