C语言写类似于约瑟夫环的决斗问题,急,循环链表!
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/10/02 19:15:13
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.
输出:按照决斗场次输出决斗结果.
【实现提示】
基本要求降低了题目的难度,因此本题和经典的约瑟夫环基本类似.但如果按照原题的要求,则此题需要求出所有可能赢得整场决斗的人的序号,这就转化成为一个动态规划问题.有志于挑战此动态规划问题的同学可以做选做内容.
有具体模板和实验指导书可发你们!
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.
输出:按照决斗场次输出决斗结果.
【实现提示】
基本要求降低了题目的难度,因此本题和经典的约瑟夫环基本类似.但如果按照原题的要求,则此题需要求出所有可能赢得整场决斗的人的序号,这就转化成为一个动态规划问题.有志于挑战此动态规划问题的同学可以做选做内容.
有具体模板和实验指导书可发你们!
#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);
}
再问: 非常感谢,请问能给我添多点儿注释吗
再答: 由于有字数限制,没法贴完整的,其中角斗士环的生成是一个重点:
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;
}
}
再问: 能给我解释下这一段吗,还有prevfighter指什么?
再答: // 为胜负关系矩阵分配空间,A是一组维度是fighters的整型指针
A = (int **)malloc(fighters*sizeof(int*));
// 每一个指针指向一组维度是fighters的整型数组,从而组成一个fighters X fighters的二维矩阵
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; // 生成0或1的两个随机数,为0则作为-1
if(A[i][j] == 0)
A[i][j] = -1;
A[j][i] = -A[i][j]; // A[j][i]是A[i][j]的相反数
}
}prevFighter用来记录参与决斗的角斗士的上一节点,如果当前角斗士输了,从环中删除它时需要知道它的上一节点是谁,通过将它的上一节点的下一节点指向它的下一节点,可以将其从环中删除,即:prevFighter->next = loser->next;,loser就被从环中去掉了
再问: 开始决斗以后的那点还可以解释下吗?
再答: // 开始战斗,开始角斗士数量是fighters
k = fighters;
while(k > 1) { // 直到最后只剩一个角斗士结束循环
i = rand() % k; // 随机生成0到fighters-1之间的随机数i,i+1即为参加决斗的人的编号
newFighter = firstFighter;
for(j = 0; j <= i; j++) { // 循环i次,找到环中参与决斗的角斗士
prevFighter = newFighter; // 记录参与决斗的角斗士的前一节点,如果当前角斗士输了,从环中删除时需要将它的前一节点的下一节点指向它的下一节点
newFighter = newFighter->next;
}
// newFighter与newFighter->next 进行角斗
if(A[newFighter->id-1][newFighter->next->id-1] == 1) {
// 当前节点的角斗士赢了,则它的下一节点是失败方
prevFighter = newFighter;
loser = newFighter->next;
}
else {
// 当前节点是失败方
loser = newFighter;
}
// 将失败者从链表中删除
if(loser == firstFighter) {
// 如果是环的头部失败,则将它的下一节点做为环的头部,令尾部的下一节点指向新的头形成闭环
firstFighter = loser->next;
lastFighter->next = firstFighter;
}
else if(loser == lastFighter) {
// 如果环的尾部失败,则它的上一节点做为环的尾部,并且新的尾部的下一节点指向环的头部形成闭环
lastFighter = prevFighter;
prevFighter->next = firstFighter;
}
#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);
}
再问: 非常感谢,请问能给我添多点儿注释吗
再答: 由于有字数限制,没法贴完整的,其中角斗士环的生成是一个重点:
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;
}
}
再问: 能给我解释下这一段吗,还有prevfighter指什么?
再答: // 为胜负关系矩阵分配空间,A是一组维度是fighters的整型指针
A = (int **)malloc(fighters*sizeof(int*));
// 每一个指针指向一组维度是fighters的整型数组,从而组成一个fighters X fighters的二维矩阵
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; // 生成0或1的两个随机数,为0则作为-1
if(A[i][j] == 0)
A[i][j] = -1;
A[j][i] = -A[i][j]; // A[j][i]是A[i][j]的相反数
}
}prevFighter用来记录参与决斗的角斗士的上一节点,如果当前角斗士输了,从环中删除它时需要知道它的上一节点是谁,通过将它的上一节点的下一节点指向它的下一节点,可以将其从环中删除,即:prevFighter->next = loser->next;,loser就被从环中去掉了
再问: 开始决斗以后的那点还可以解释下吗?
再答: // 开始战斗,开始角斗士数量是fighters
k = fighters;
while(k > 1) { // 直到最后只剩一个角斗士结束循环
i = rand() % k; // 随机生成0到fighters-1之间的随机数i,i+1即为参加决斗的人的编号
newFighter = firstFighter;
for(j = 0; j <= i; j++) { // 循环i次,找到环中参与决斗的角斗士
prevFighter = newFighter; // 记录参与决斗的角斗士的前一节点,如果当前角斗士输了,从环中删除时需要将它的前一节点的下一节点指向它的下一节点
newFighter = newFighter->next;
}
// newFighter与newFighter->next 进行角斗
if(A[newFighter->id-1][newFighter->next->id-1] == 1) {
// 当前节点的角斗士赢了,则它的下一节点是失败方
prevFighter = newFighter;
loser = newFighter->next;
}
else {
// 当前节点是失败方
loser = newFighter;
}
// 将失败者从链表中删除
if(loser == firstFighter) {
// 如果是环的头部失败,则将它的下一节点做为环的头部,令尾部的下一节点指向新的头形成闭环
firstFighter = loser->next;
lastFighter->next = firstFighter;
}
else if(loser == lastFighter) {
// 如果环的尾部失败,则它的上一节点做为环的尾部,并且新的尾部的下一节点指向环的头部形成闭环
lastFighter = prevFighter;
prevFighter->next = firstFighter;
}