零、效果展示
一、题目要求
有n个加里森敢死队的队员要炸掉敌人的一个军火库，谁都不想去，队长加里森决定用轮回数数的办法来决定哪个战士去执行任务。规则如下：如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个编号为x的战士开始计数，当数到y时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第y时，此战士接着去执行任务。以此类推，直到任务完成为止。
加里森本人是不愿意去的，假设加里森为1号，请你设计一程序为加里森支招，求出n,x,y满足何种条件时,加里森能留到最后而不用去执行任务。
要求：
（1）主要数据结构采用链式结构存储。
（2）自拟实验实例验证程序正确性，并讨论n,x,y之间的关系。
二、需求分析
任务描述
设计一个程序解决加里森的任务问题。该问题要求根据给定的条件（n、x、y），找出使加里森不用去执行任务的组合。具体规则如下：
- 有 n 个加里森敢死队的队员要炸掉敌人的一个军火库。
- 每个队员都有一个编号，编号从 1 到 n。
- 以编号为 x 的战士为起始点，从1开始循环数数，每数到第 y 个战士，该战士将去执行任务。
- 如果某个战士执行任务失败，则会重新开始数数，直到任务完成为止。
- 加里森本人是不愿意去执行任务的，他的编号永远为1。
输入要求
- 输入形式：通过命令行或交互界面输入 n、x、y 的值。
- 输入值的范围：n、x、y 均为正整数，且满足 1 <= x <= n，1 <= y <= 2*n（自定义）。
输出要求
- 输出形式：输出符合条件的 x 和 y 的组合。
- 输出内容：程序将输出满足条件的 x 和 y 值，使得加里森不用去执行任务。
功能描述
- 程序能够根据输入的 n、x、y 值，计算出使加里森不用去执行任务的组合。
- 程序能够处理正确的输入，并输出符合条件的 x 和 y 值。
- 程序能够处理错误的输入，并给出相应的错误提示或处理方式。
测试数据
- 正确的输入数据：例如 n=5，y=2，期望输出为 x=6。
- 错误的输入数据：例如 n=0，期望输出为错误提示或处理方式。
二、 概要设计
思路概述
- 使用链表结构模拟加里森的任务问题，每个节点代表一个队员，节点之间通过指针连接成环形链表。
- 设计函数来初始化链表、删除节点、打印链表等操作，根据规则模拟任务执行过程，找出符合条件的 x 和 y 的组合。
数据结构定义
- 定义链表节点结构体
LinkNode，包含数据data和指向下一个节点的指针next。
主程序流程
- 提供交互式界面，让用户输入 n、x、y 的值。
- 根据用户输入的值调用相应的函数进行计算和处理。
- 输出符合条件的 x 和 y 的组合，或者输出错误提示信息。
程序模块层次关系
- 主程序模块：负责处理用户输入、调用相应函数、输出结果。
- 初始化链表模块：负责创建空链表和添加节点。
- 模拟模块：根据规则进行模拟运行并删除节点。
- 输出结果模块：根据计算结果输出符合条件的 x 和 y 的组合，或者输出错误提示信息。
三、详细设计
主体思路
主函数 main
|
|--> function//面向用户的交互模块
|
|--> Garrison_x//基于(n,y)求解(x)
| |--> x++
| |--> CreateHeadNode + InitList//初始化n人链表
| |--> DeleteNode
| |--> PrintList
|
|--> Garrison_x_y//基于(n)求解(x,y)
| |--> x++
| |--> y++
| |--> CreateHeadNode + InitList//初始化n人链表
| |--> DeleteNode
| |--> PrintList
结构体定义
//定义节点结构体
typedef struct linknode {
int data;
struct linknode* next;
}LinkNode;函数定义
LinkNode* CreateHeadNode(void);//创建头结点
void CreateNewNode(LinkNode* H,int data);//创建元素节点
void PrintList(LinkNode* H);//打印链表
void DeleteNode(LinkNode* H, int num);//删除节点
void InitList(LinkNode* H,int num);//初始化链表
void Garrison_x(int n, int y, int isPrt);//固定n,y求x
void Garrison_x_y(int n, int isPrt);//固定n求x,y
void function();//面向用户的交互模块执行函数
void Garrison_x(int n, int y, int isPrt)//固定n,y求x
{
for (int x = 1; x <= n; x++)
{
//根据n值初始化链表
LinkNode* H = CreateHeadNode();
pre = H;
InitList(H, n);
if (isPrt) PrintList(H);//打印初始化后的链表
for (int j = 0; j < x-1; j++)//将pre指向上次执行者的前一个人
pre = pre->next;
while (H->data > 1)//当前链表剩余元素个数>1?继续进行删除操作:退出
{
DeleteNode(H, y);
if (isPrt) PrintList(H);
}
if (H->next->data == 1)//如果1号(加里森)活了下来
printf("\n*** x = %d ***\n\n", x);
else//似了
if (isPrt) printf("x = %d is wrong\n", x);
}
}
void Garrison_x_y(int n, int isPrt)//固定n求x,y
{
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= 2 * n; y++)//设置y的上限是2n，可根据需求进行修改
{
LinkNode* H = CreateHeadNode();
pre = H;
InitList(H, n);
if(isPrt) PrintList(H);
for (int j = 0; j < x-1; j++)
pre = pre->next;
while (H->data > 1)
{
DeleteNode(H, y);
if (isPrt) PrintList(H);
}
if (H->next->data == 1)
printf("\n*** x = %d y = %d***\n\n", x,y);
else
if (isPrt) printf("x = %d y = %d is wrong\n", x,y);
}
}
}交互模块
void function()
{
int func = 0;
int isPrt = 0;
int n, x, y;
printf("\n请输入想要执行的功能('1'表示(n,y)->(x),'2'表示(n)->(x,y),'0'表示退出程序):" );
scanf_s("%d", &func);
switch (func) {
case 0:
exit(0);
case 1:
printf("\n请输入n=");
scanf_s("%d", &n);
printf("\n请输入y=");
scanf_s("%d", &y);
if (n <= 0 || y <= 0)
{
printf("输入不合法，请重新输入");
break;
}
printf("\n请选择打印模式('1'表示'全过程','0'表示'精简'):");
scanf_s("%d", &isPrt);
Garrison_x(n, y, isPrt);
break;
case 2:
printf("\n请输入n=");
scanf_s("%d", &n);
if (n <= 0)
{
printf("输入不合法，请重新输入");
break;
}
printf("\n请选择打印模式('1'表示'全过程','0'表示'精简'):");
scanf_s("%d", &isPrt);
Garrison_x_y(n, isPrt);
break;
default:
printf("\n输入错误！请检查输入");
break;
}
}四、 调试分析报告
时间复杂度
对于(n,y)->x，当固定n与y时，对于每一个x，删除节点操作执行n-1次，每次删除会移动工作指针y次，时间复杂度为O(n^2*y)。
对于(n)->(x,y)，当固定n，再固定x时，对于每一个y，删除节点操作执行n-1次，每次删除会移动工作指针y次，时间复杂度为O(n^4)。
空间复杂度
链表操作的空间复杂度为O(n)
发现
当(n)->(x,y)时，xy的对数与y的取值范围相同。换句话说，当n一定时，对于任意的y，都能找到唯一确定的x与之对应。
五、用户使用说明
- 运行程序后，程序将会显示如下提示信息：
请输入想要执行的功能('1'表示(n,y)->(x),'2'表示(n)->(x,y),'0'表示退出程序):-
根据提示输入想要执行的功能对应的数字，例如输入 1表示执行 (n,y)->x 的功能。
-
根据程序提示依次输入相关参数：
- 对于功能
1，需要依次输入 n 和 y 的值，确保输入的值大于 0。 - 对于功能
2，需要输入 n 的值，确保输入的值大于 0。
- 对于功能
-
如果输入的值不合法（小于等于 0），程序将会提示重新输入。
-
程序会根据输入的参数执行相应的功能，并输出结果或过程。
-
如果需要继续测试或执行其他功能，可以重复上述操作进行。文章来源：https://www.toymoban.com/news/detail-848608.html
-
如果需要退出程序，可以输入
0并按回车键退出。文章来源地址https://www.toymoban.com/news/detail-848608.html
六、 测试结果
mode:(n,y)->(x) simply
input:n=-1,y=3
output:
输入不合法，请重新输入mode:(n,y)->(x) simply
input:n=10,y=3
output:
*** x = 7 ***
mode:(n,y)->(x) all
input:n=3,y=1
output:
List: 1 2 3
List: 1 3
List: 1
*** x = 1 ***
List: 1 2 3
List: 1 2
List: 2
x = 2 is wrong
List: 1 2 3
List: 2 3
List: 3
x = 3 is wrongmode:(n)->(x,y) simply
input:n=6
output:
*** x = 1 y = 3***
*** x = 1 y = 5***
*** x = 2 y = 1***
*** x = 3 y = 2***
*** x = 3 y = 4***
*** x = 3 y = 7***
*** x = 3 y = 9***
*** x = 4 y = 6***
*** x = 4 y = 11***
*** x = 5 y = 8***
*** x = 5 y = 12***
*** x = 6 y = 10***到了这里，关于【数据结构】实践作业：加里森的任务的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
