这里提供约瑟夫环问题的c++代码和思路，其实这个问题用数组解决足矣，但是为了应用数据结构的顺序表，这里给出两种顺序表的代码。
c++1：
/*
约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针
方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针方
向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下一
个人开始重新从1报数，报到m时停止并且报m的人出列。如此下去，
直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给
定的m和n，求出出列编号序列。实验要求：用顺序表实现。
*/
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct
{
int *a;//这里想让数组成员长度是可变的，可以把它先写成一个指针。
// 实例化成一个结构体变量时再对其进行动态分配空间
int length;
}list;//命名为list类
void Creatlist(list *&L,int *p,int n)//这里我们需要对指针变量L进行操作（赋值等），所以要引用L的地址
{
L=(list*)malloc(sizeof(list));/*为结构体指针申请空间。这里L是一个指针，
为什么要分配空间呢？因为这个指针指向的
结构体需要空间，我们要创造这样一个空间
*/
L->a=(int*)malloc(sizeof(int)*n);//为可变数组成员申请空间
int i=0,k=0;
printf("队列序号为：\n");
while(i<n)
{
L->a[k]=p[i];//把数组中的数值转移到顺序表list中
printf("%d ",L->a[k]);
k++;i++;
}
printf("\n");
L->length=k;
}
void chose(list *&L,int m)//这是选择出列序号的函数，m是给定出列序号
{
int k=0;//这是数组下标
printf("出列序号为：\n");
for(int i=1;L->length>0;i++)//循环查找，每m个元素就输出这个元素，实际上也可以用模除来实现，但这样更直观。
{ //循环条件是长度要大于零
if(k+1>L->length)//当循环到最后一个元素时，回到第一个元素
{
k=0;
}
if (i==m)//当找到
{
printf("%d ",L->a[k]);
for(int j=k;j+1<=L->length;j++)//后面所有元素整体向前挪一个单位
{
L->a[j]=L->a[j+1];
}
L->length--;//元素拿出来长度要减一
i=0;//找到这个元素后序号要从1开始重新计数，循环每次加一，所以这里赋0
continue;//找到后重新开始
}
k++;//这里数组下标要一直加一，但是当找到后后面的元素回向前挪，此时角标不能加一
//，当前元素就是序号1所以不能放到循环括号里
}
printf("\n");
}
int main()
{
int *p;
int n,m,j=1;
printf("请输入人数：");
scanf("%d",&n);
p=(int*)malloc(n*sizeof(int));//创建一个数组用来存放1到n,这里没有指定大小，我们动态分配空间
while(j<=n)
{
p[j-1]=j;
// printf("%d",p[j-1]);
j++;
}
list *l1;//定义一个结构体指针，按理要进行分配内存空间，这样也可以，但是我们也可以在调用的函体数里作这件事
Creatlist(l1,p,n);
printf("请输入要出列的序号:\n");
scanf("%d",&m);
chose(l1,m);
system("pause");
}
c++2：
#include<stdio.h>
#include<stdlib.h>
#define Maxsize 30
struct SqList
{
int Data[Maxsize];
int length;
};
typedef struct SqList SqList;
void InitList(SqList *&L)
{
L = (SqList *)malloc(sizeof(SqList));
L->length = 0;
}
void CreateList(SqList *&L)
{
int i;
int people;
printf("请输入队列总人数:\n");
scanf("%d",&people);
printf("\n");
printf("队列序号是：\n");
for (i=0; i<people; i++)
{
L->Data[i] = i + 1;
printf("%d ", L->Data[i]);
}
printf("\n");
L->length = people;
}
void DisplayList(SqList *L)
{
int m, i, j;
int k=0;
printf("\n");
printf("请输入第几个报数的人出列: \n");
scanf("%d", &m);
printf("\n");
printf("出列次序依次是:\n");
for (i=L->length; i>0; i--)
{
k=(k+m-1)%i;
printf("%d ",L->Data[k]);
for (j=k;j<i-1; j++)
{
L->Data[j] = L->Data[j+1];
}
L->length = L->length - 1;
}
printf("\n");
}
int main()
{
SqList *L;
InitList(L);
CreateList(L);
DisplayList(L);
}
0 条评论