大学数据结构实验(一.顺序表的应用二)

大学程序实验.数据结构.顺序表的应用一.约瑟夫环问题

• ​​0 目录​​
• ​​1 顺序表的应用​​

• ​​1.2 约瑟夫环问题​​

• ​​1.2.1 题目​​
• ​​1.2.2 源码​​
• ​​1.1.3 下载​​

• ​​2 下一章​​

0 目录

1 顺序表的应用

1.2 约瑟夫环问题

1.2.1 题目

问题描述：有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第s个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。
实验要求: 采用顺序存储结构实现。

1.2.2 源码

// 约瑟夫环.cpp : Defines the entry point for the console application.
//
/***********************************************************************
* 头文件包含
***********************************************************************/
#include "stdlib.h"
#include "stdio.h"

/***********************************************************************
* 本地宏定义
***********************************************************************/
#define N 5
#define S 3
#define M 3
#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct
{
ElemType key[N];
ElemType num[N];
ElemType length;
}SqList;


/*********************************************************************
* 函 数 名 : main
* 函数功能 : 主函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status main()
{
SqList *L;

Status ListMenu();
Status ListCheck();
Status ListCreate(SqList *&L);

int result;
ListMenu();
result=ListCheck();

if(result)
{
printf("检测完成!\n");

ListCreate(L);
int k=S-1;
printf("最终出列的顺序为 : \n");
int value=M;
for(int i=L->length;i>0;i--)
{
k=(k+value-1)%i;
printf("%3d",L->num[k]);
value=L->key[k];

for(int j=k;j<=i-1;j++)
{
L->num[j]=L->num[j+1];
}
L->length=L->length-1;
}
printf("\n");
}
else
{
printf("请输入正确的M或N值!");
}

return OK;
}

/*********************************************************************
* 函 数 名 : ListMenu
* 函数功能 : 目录函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status ListMenu()
{
printf("***********约瑟夫环*********** \n");

return OK;
}

/*********************************************************************
* 函 数 名 : ListCheak
* 函数功能 : 检测函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status ListCheck()
{
printf("数据检测：\n");

if(N<=1)
{
printf("输入的总人数有误!\n");
return ERROR;
}
if((S<1)||(S>N))
{
printf("输入初始值有误!\n");
return ERROR;
}
if(M<0)
{
printf("输入上限值有误!\n");
return ERROR;
}
else
{
printf("参加人数：%d\n",N);
printf("开始位次：%d\n",S);
printf("上报数值：%d\n",M);
printf("\n");
}
return OK;
}

/*********************************************************************
* 函 数 名 : ListCreate
* 函数功能 : 创建函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status ListCreate(SqList *&L)
{
L=(SqList*)malloc(sizeof(SqList));
L->length=0;

printf("正在随机生成%d个同学的整数密码：\n",N);
for(int i=0;i<N;i++)
{
printf("第 %d 个人的密码 : ",i+1);
L->key[i]=rand()%N+1;
L->num[i]=i+1;
L->length++;
printf("%d",L->key[i]);
printf("\n");
}
printf("\n");

return OK;
}

1.1.3 下载

链接地址: ​​1.2_约瑟夫环.CPP​​

2 下一章

博客地址: ​​大学数据结构实验(二.链表的应用一)​​