约瑟夫环
实习报告
题目：编制一个程序求出约瑟夫环问题的出列顺序。
班级：06计算机A班姓名：林树地学号：0615111044 完成日期：2008-05-01
顺序表实现
一、需求分析
1. 本程序需要由用户在键盘上输入程序中的相关数据。
2. 先输入初始密码m (m>0)和环中人的个数n（n<50），再依次输入每个人的密码。
输
入形式是以“回车”为结束标志的整型数。
3. 依次输出约瑟夫环中的出列者的编号。
4. 测试数据：
初值m=20，n=7，7个人的密码依次为：3，1，7，2，4，8，4。
出列顺序应为6，1，4，7，2，3，5。
二、概要设计
以顺序表表示环中的人：
1.顺序表数据类型定义为：
ADT sqlist{
数据对象：D={ a i|a i∈Elemtype,i=1,2,……n；n≥0}
数据关系：R1={<a i-1,a i>| a i-1,a i∈D,i=2,……,n}
基本操作：
initlist_sq(&l)
操作结果：构造一个空的顺序表
}ADT sqlist
2．本程序包含两个模块
①主程序模块
void main(){
接受命令；
处理命令；
}
②顺序表单元模块——实现顺序表抽象数据类型；
各模式块之间的调用关系如下；
主程序模块→顺序表单元模块
三、详细设计
1．顺序表类型
typedef struct{
int elem[50];//存密码
int length;
}sqlist;
2．主函数和其他函数的伪码算法
void main()
{
int m,n;//m为密码，n为小孩个数
cout<<"请输入初始密码m和人数n(n不大于50):";
while(n<1||n>50)
{
cin>>m>>n;
if(n<1||n>50) cout<<"人数不合法，请重输"<<endl;
}
sqlist Jos;
initlist_sq(Jos);// 初始化线性表
cout<<"请依次输入"<<n<<"个密码:";
for(;Jos.length<n;Jos.length++)
cin>>Jos.elem[Jos.length];//存密码
cout<<"出列顺序为：";
int i=-1;//i为数组下标（下一值为0）
for(int k=0;k<n;k++)
{
for(int j=0;j<m;)
{
i=(i+1)%n;//对下标加1求模
if(Jos.elem[i]!=0)//判断是否已出列
j++;
}
cout<<i+1<<" ";
m=Jos.elem[i];//输出已出列的编号
Jos.elem[i]=0;//标识已出列
}
cout<<endl;
}
void initlist_sq(sqlist &l){
l.length=0;
}
3.函数调用关系：
main
InitList
四、调试分析
1.刚开始忽略了对输入数据合法性的判断，可能造成存储空间不足。
2.算法时空分析
主函数中，时间复杂度为O(n*m)。
五、测试结果
循环链表实现
一、需求分析
1. 本程序需要由用户在键盘上输入程序中的相关数据。
2. 先输入初始密码m (m>0)和环中人的个数n (n>0)，再依次输入每个人的密码。
输入
形式是以“回车”为结束标志的整型数。
3. 依次输出约瑟夫环中的出列者的编号。
4. 测试数据：
初值m=20，n=7，7个人的密码依次为：3，1，7，2，4，8，4。
出列顺序应为6，1，4，7，2，3，5。
二、概要设计
以循环链表存储结构表示环中的人。
1．本程序包含两个模块
①主程序模块
void main(){
初始化；
接受命令；
②顺序表单元模块——实现循环链表抽象数据类型；
各模式块之间的调用关系如下；
主程序模块→循环链表单元模块
三、详细设计
1．元素类型、节点类型和指针类型
typedef struct Lnode
int data;
int secret;
struct Lnode* next;
}*p,*q,*t,h,*head，*linklist;//p为当前指针，head为头指针，q为跟随指针，h 为头节点
2. 主函数的算法
void main()
{
cout<<"请输入人数n，报数上限值m和这n个人的密码:"<<endl;
int m,n,i;
string s;vector<int>a;
getline(cin,s);
istringstream sin(s);
for(int b;sin>>b;a.push_back(b));
cout<<"您输入这n个人的密码是：";
for(i=2;i<a.size();i++)
cout<<a[i]<<",";
cout<<endl;
h.next=NULL;
head=&h;
p=head;
n=a[0];
//创建循环链表
for(i=1;i<=n;i++)
{
p->next=(Lnode*)malloc(sizeof(Lnode));
p=p->next;
p->data=i;
p->secret=a[i+1];
if(i!=n)
p->next=NULL;
else
{
p->next=head->next;
p=p->next;
}
}
//小孩出列
q=head;
m=a[1];
w hile(p->next!=p)
for(i=1;i<m;i++)
{
p=p->next;
q=q->next;
}
cout<<p->data<<" ";
m=p->secret;
q->next=p->next;
t=p;
p=p->next;
free(t);
}
cout<<p->data<<endl;
}函数调用关系
main
四、调试分析
1.算法的时空分析：
主函数中时间复杂度为O(n*m)。
五、测试结果。