约瑟夫斯问题求解.doc

实验一：约瑟夫斯问题求解
一、 问题描述
1． 实验题目：约瑟夫斯问题的一种描述是：编号为1，2，……n的n个人按顺时针方向围坐一圈，每人持有一个密码9(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按照顺时针方向自1开始报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。
2． 基本要求：利用单向循环链表模拟此过程，按照出列的顺序印出各人编号。
3． 测试数据：n=7,7个人的密码依次为3，1，7，2，4，8，4.m的初始值为6（正确的出列顺序应为6，1，4，7，2，3，5。
二、 需求分析
1． 程序所能达到的基本可能：本程序能够按出列顺序印出各人编号，程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，程序需自动考虑重复的，用户输入完毕后，程序自动输出运算结果。
2． 输入的形式及输入值范围 ：输入人数n,初始报数值m，n个人的密码，所有值均为正整数int型。
3． 输出的形式： 输出的是按出列顺序印出各人编号，为正整数int型。
4． 测试数据要求 ：测试数据要求为int型
三、 概要设计
1. 所用到得数据结构及其ADT
为了实现上述功能，应以单向循环链表有序链表表示集合
数据类型。
1. 单向循环链表抽象数据类型定义：
typedef struct node
{
ElemType data;
ElemType num;
struct node *next;
}SLNODE;
基本操作：
struct node *create_sl(int n);//创建单向循环链表
2. 主程序流程及其模块调用关系
1）创建循环链表的流程图

2） 约瑟夫问题求解流程图

3） 主函数流程图

四、 详细设计
1. 实现每个操作的伪码，重点语句加注释
主程序：
void main()
{
SLNODE *head;
int n,m;
head=(SLNODE *)malloc(sizeof(SLNODE));
printf("/*************************************/\n"); //初始界面
printf(" 学号：031350102\n");
printf(" 姓名：王亚文\n");
printf(" 约瑟夫斯问题求解\n");
printf("/*************************************/\n");
printf("输入总人数n=\n");
scanf("%d",&n);
printf("输入初始报数值m=\n");
scanf("%d",&m);
head=create_sl(n);
Josephus(head,n,m);
}
2.创建循环单链表
struct node *create_sl(int n)
{
SLNODE *p,*s,*head;
ElemType x;
int a;
head=(SLNODE *)malloc(sizeof(SLNODE));
p=head;
head->next=head;
for(a=1;a<=n;a++) //循环直到输入n个密码值跳出循环
{
s=(SLNODE *)malloc(sizeof(SLNODE));
printf("请输入第%d个人的密码值\n",a);
scanf("%d",&x);
s->data=x;
s->num=a;
if(head->next==head) head=s;
else p->next=s;
p=s;
}
p->next=head;
return head;
}
3.约瑟夫斯问题求解：
void Josephus(SLNODE *head,int n,int m)
{
SLNODE *p,*q;
int i;
p=head;
printf("出列序列:");
while(p->next!=p)
{
for(i=1;i<m;i++) //报数报的m时跳出循环
{
q=p;
p=p->next;
}
m=p->data; //读取新的密码值
printf("%4d",p->num);
q->next=p->next; //删除p节点
free(p);
p=q->next;
}
printf("%4d\n",p->num);
}
4. 函数调用关系图
主函数中调用了struct node *create_sl(int n);
void Josephus(SLNODE *head,int n,int m);两个函数

五、 调试分析
1. 设计与调试过程中遇到的问题分析、体会
1）创建单链表时，一开始写的程序是void create_sl(SLNODE *head ,int n),并没有没有报错，但最后运行时却不是想象的结果，然后尝试在主函数中写一个printf函数看一下创建表是否创建成功，事实证明并没有，后来改成了struct node *create_sl(int n);解决了这个问题，再次就是建表的时候发现最后一个数并不是我输入的数，然后就是开始改那个循环=函数，发现我虽然是读了7个数，但第7个数并没有赋值给链表，原错误函数：
p=head;
head->next=head;
printf("请输入密码值\n");
scanf("%d",&x);
for(a=1;a<n;a++) //循环直到输入n个密码值跳出循环
{
s=(SLNODE *)malloc(sizeof(SLNODE));
printf("请输入密码值\n");
scanf("%d",&x);
s->data=x;
s->num=a;
if(head->next==head) head=s;
else p->next=s;
p=s;
}
经过修正后的函数：p=head;
head->next=head;
for(a=1;a<=n;a++) //循环直到输入n个密码值跳出循环
{
s=(SLNODE *)malloc(sizeof(SLNODE));
printf("请输入第%d个人的密码值\n",a);
scanf("%d",&x);
s->data=x;
s->num=a;
if(head->next==head) head=s;
else p->next=s;
p=s;
}
2）建表成功之后开始解决本次的主问题约瑟夫斯求解问题，本问题主要考虑循环终止条件，一开始写的是head->next=head;发现经常运行错误，后来修正用p->next!=p，然后最后一个p值单独写一句输出printf("%4d\n",p->num);中间的句子就是找到报数值然后删除，注意保留要删除节点的密码值，并没有什么大问题。还有一个问题，就是在开始的时候创建单链表并没有想到要用序号值num，最开始定义单链表的语句：
typedef struct node
{
ElemType data;
struct node *next;
}SLNODE; 然后就会在创建链表赋值时和解决约瑟夫斯问题时都要重新定义一个变量x进行计数，增加了程序的复杂度最后修正为：
typedef struct node
{
ElemType data;
ElemType num;
struct node *next;
}SLNODE;
3) 剩下的还有一些小问题，比如少打了一个字母，打错一个字母，这些程序会报错，不属于逻辑错误，所以解决起来也比较快，
2. 主要算法的时间复杂度分析
创建单链表的时间复杂度为O（n）;
约瑟夫斯问题的时间复杂度与n值有关，也与每个人的密码值有关,时间复杂度O（mn）;空间复杂度为O（n）;
六、 使用说明
程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，用户按照提示输入完毕后，程序自动输出运算结果。
七、 测试结果

八、 附录
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct node
{
ElemType data;
ElemType num;
struct node *next;
}SLNODE; //单链表的定义
struct node *create_sl(int n);
void Josephus(SLNODE *head,int n,int m);
int main() //主函数
{
SLNODE *head;
int n,m;
time_t rawtime;
struct tm * timeinfo;

time (&rawtime);
timeinfo = localtime (&rawtime);

head=(SLNODE *)malloc(sizeof(SLNODE));
printf("/*************************************/\n"); //初始界面

printf(" 学号：031350102\n");
printf(" 姓名：王亚文\n");
printf(" 约瑟夫斯问题求解\n");
printf("/*************************************/\n");
printf("输入总人数n=\n");
scanf("%d",&n);
printf("输入初始报数值m=\n");
scanf("%d",&m);
head=create_sl(n); //创建单链表
Josephus(head,n,m);
printf ("Current local time and date: %s", asctime(timeinfo));
return 0;
}
struct node *create_sl(int n)
{
SLNODE *p,*s,*head;
ElemType x;
int a;
head=(SLNODE *)malloc(sizeof(SLNODE));
p=head;
head->next=head;
for(a=1;a<=n;a++) //循环直到输入n个密码值跳出循环
{
s=(SLNODE *)malloc(sizeof(SLNODE));
printf("请输入第%d个人的密码值\n",a);
scanf("%d",&x);
s->data=x;
s->num=a;
if(head->next==head) head=s;
else p->next=s;
p=s;
}
p->next=head;
return head;
}
void Josephus(SLNODE *head,int n,int m)//约瑟夫斯问题求解
{
SLNODE *p,*q;
int i;
p=head;
printf("出列序列:");
while(p->next!=p)
{
for(i=1;i<m;i++) //程序运行到第m个人跳出循环
{
q=p;
p=p->next;
}
m=p->data; //读取新的密码值
printf("%4d",p->num);
q->next=p->next; //删除p节点
free(p);
p=q->next;
}
printf("%4d\n",p->num);
}
九、 实验收获和感想
通过本实验首先是解决了约瑟夫斯问题，利用计算机快速解决这个问题，其次在程序编写过程中慢慢掌握了循环单链表的一些用法以及注意事项，因为距离上次学习c语言已经有很长一段时间，这次确实遇到了很多障碍，不仅仅是对链表的生疏，也包含以前基础的薄弱环节，通过一个程序的设计，慢慢回忆起程序的编写，加强自己的逻辑性，编程是一个很麻烦的事，一个小错误的出项，程序就不会出现预想的结果，如果报错还可以按照提示找到，若有逻辑错误还得一行一行检查，最后发现如果程序需要解决多个问题，最好还是分模块解决，解决完一个问题再去解决另一个问题，如果一个模块有错误及时发现，也比较好改。这个程序是第一个设计的程序，不论是程序的编写还是报告的书写，都明显有不足地方，也希望在之后的报告中能逐步完善，争取一个比一个写得好。