实验一报告
姓名：
学号：
完成日期：
2015年4月7日
题目：设有n 个人坐在一个圆桌周围，现从第s 个人开始报数，数到第m 的人出列，然后从出列的下一个人重新开始报数，数到第m 的人又出列，如此反复直到所有的人全部出列为止。Josephus 问题是：对于任意给定的n 、s 、m ，求出按出列次序得到的n 个人员的序列。试在计算机上模拟Josephus 问题的求解工程。
1、 需求分析
输入形式、输入值的范围：输入的值必须为正整数
输出形式：输出为一组正整数
程序功能：对于任意给定的n 、s 、m ，求出按出列次序得到的n 个人员的序 列。
测试数据：正确的输入：6 3 2
正确的输出：4 6 2 5 3 1
错误的输入：6 3 2
错误的输出：1 2 3 4 5 6
2、 概要设计
主程序流程：
否
3、 调试分析
调试中并遇到的问题：运行结果少一个数
解决方案：在while 循环的限制条件中，是循环次数加1 算法时空分析：O(n)
4、 用户使用说明
运行程序后，用户按照提示顺序输入3个正整数，然后按回车可得到结果
5、 测试结果
输入：6 3 2
输出：4 6 2 5 3 1
6、 源程序
以顺序表实现：
#include
using namespace std;
void JJ(int n,int s,int m)
{
int *a=new int [10000];
int i;
int count=0;
int t=0;
for(i=0;i
a[i]=i+1;
}
i=s-1;
cout
while(count
{
if(a[i]!=0)
t++;
if(t==m){
t=0;//记数归0
couta[i]=0;//给删除的数组赋0
count++;//退出人数加1
}
i++;
if(i==n)
i=0;//报数到末尾后i 恢复为0
}
cout
}
void main()
{
int n,s,m;
cout
cin>>n;
cout
cin>>s;
cout
cin>>m;
JJ(n,s,m);
}
以链表实现：
#include
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
void JJ(int n,int s,int m)
{
LinkList p,r,list=NULL;
int i;
//建立一个循环链表
for(i=0;i
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i+1; //存放第i 个结点的编号
if(list==NULL)
list=p;
else
r->next=p;
r=p;
}
p->next=list;
p=list;
for(i=1;i
{
r=p;
//当m!=1,但s=1时如果没有这条语句，此时删除动作无法完成 p=p->next;
}//此时p 指向第1个出发结点
cout
while(p->next!=p)
{
for(i=1;i
{
r=p;
p=p->next;
} //p指向第m 个结点,r 指向第m-1个结点 r->next=p->next; //删除第m 个结点
coutdata
delete p;
p=r->next;
}
coutdata;
cout
}
void main()
{
int n,s,m;
cout
scanf("%d",&n);
cout
scanf("%d",&s);
cout
scanf("%d",&m);
JJ(n,s,m);
}
实验一报告
姓名：
学号：
完成日期：
2015年4月7日
题目：设有n 个人坐在一个圆桌周围，现从第s 个人开始报数，数到第m 的人出列，然后从出列的下一个人重新开始报数，数到第m 的人又出列，如此反复直到所有的人全部出列为止。Josephus 问题是：对于任意给定的n 、s 、m ，求出按出列次序得到的n 个人员的序列。试在计算机上模拟Josephus 问题的求解工程。
1、 需求分析
输入形式、输入值的范围：输入的值必须为正整数
输出形式：输出为一组正整数
程序功能：对于任意给定的n 、s 、m ，求出按出列次序得到的n 个人员的序 列。
测试数据：正确的输入：6 3 2
正确的输出：4 6 2 5 3 1
错误的输入：6 3 2
错误的输出：1 2 3 4 5 6
2、 概要设计
主程序流程：
否
3、 调试分析
调试中并遇到的问题：运行结果少一个数
解决方案：在while 循环的限制条件中，是循环次数加1 算法时空分析：O(n)
4、 用户使用说明
运行程序后，用户按照提示顺序输入3个正整数，然后按回车可得到结果
5、 测试结果
输入：6 3 2
输出：4 6 2 5 3 1
6、 源程序
以顺序表实现：
#include
using namespace std;
void JJ(int n,int s,int m)
{
int *a=new int [10000];
int i;
int count=0;
int t=0;
for(i=0;i
a[i]=i+1;
}
i=s-1;
cout
while(count
{
if(a[i]!=0)
t++;
if(t==m){
t=0;//记数归0
couta[i]=0;//给删除的数组赋0
count++;//退出人数加1
}
i++;
if(i==n)
i=0;//报数到末尾后i 恢复为0
}
cout
}
void main()
{
int n,s,m;
cout
cin>>n;
cout
cin>>s;
cout
cin>>m;
JJ(n,s,m);
}
以链表实现：
#include
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
void JJ(int n,int s,int m)
{
LinkList p,r,list=NULL;
int i;
//建立一个循环链表
for(i=0;i
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i+1; //存放第i 个结点的编号
if(list==NULL)
list=p;
else
r->next=p;
r=p;
}
p->next=list;
p=list;
for(i=1;i
{
r=p;
//当m!=1,但s=1时如果没有这条语句，此时删除动作无法完成 p=p->next;
}//此时p 指向第1个出发结点
cout
while(p->next!=p)
{
for(i=1;i
{
r=p;
p=p->next;
} //p指向第m 个结点,r 指向第m-1个结点 r->next=p->next; //删除第m 个结点
coutdata
delete p;
p=r->next;
}
coutdata;
cout
}
void main()
{
int n,s,m;
cout
scanf("%d",&n);
cout
scanf("%d",&s);
cout
scanf("%d",&m);
JJ(n,s,m);
}