当前位置:文档之家› 约瑟夫环问题课程设计报告

约瑟夫环问题课程设计报告

数据结构

课程设计报告设计课题:约瑟夫问题

院系:计算机科学与技术学院专业班级:计算机网络技术1102班

学生姓名:张利

学号: 1 1 0 8 0 4 0 2 1 1

指导教师:王昱哲

目录

1.需求分析 (3)

1.1问题描述 (3)

1.2功能分析 (4)

2.概要设计 (5)

3.详细设计 (6)

4.调试与操作说明 ............... 1错误!未定义书签。总结.. (16)

一.需求分析

1.1问题描述

约瑟夫环问题描述的是:设编号为1,2,…,n的n(n>0)个人按顺时针方向围坐一圈,每个人持有一正整数密码。开始时选择一个正整数作为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的

人出圈,将他的密码作为新的m 值,从他在顺时针方向上的下一个人起重新从1报数。如此下去,直到所有人都出圈为止。令n 最大值为100。要求设计一个程序模拟此过程,求出出圈的编号序列。如下图分析:

1 2

3

4

5

6

7

8

9

这是第一个人,他的密码是“1”,个他输一个m 值,如果m=3,则从他开始向下走3

这就是第二步的位置,这时他的密码作为新的m 值,即m=4,同时

得到的第一个密码为

4;4号出去向下走4,到9这儿;(这这一步完了剩余的为:1,2,3,5,6,,7,8,9,0,)

这就是第三步的位置,这时他的密码作为新的m 值,即m=9,同时得到的第二个密码为9;9号出去向下走9,到0这儿;继续走就行了(这儿剩余的就是:1,2,3,5,6,7,8,0)

图1约瑟夫环问图解

1.2功能分析

约瑟夫环问题是一个古老的数学问题,本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表,同样也能方便地解决。

在建立双向循环链表时,因为约瑟夫环的大小由输入决定。为方便操作,我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时,用一个指针current 指向当前的结点,指针front 始终指向头结点。然后建立双向循环链表,因为每个人的密码是通过rand()函数随机生成的,所以指

3 2 7 1 4

8 4

约瑟夫环原理演示图

1 2 3 4 5 6 7

第二部:第一次停下的位置,此时6号出列,并将他的值作为新的m 值,即:新的m=8;从7好开始继续向下走8次,到1号

的位置

最后排序后的密码序列: (本图只演示前两步)

8

第三步: 第二次,1号出列

第四步:第三次,4号出列

3 第一步:给第一个人赋初始密码为:20则从它开始向下走20次,到6号位置

2 4 1 7 4

6

1

4

7

2

3

5

图2 约瑟夫环原理演示图

定第一个人的顺序号,找到结点,不断地从链表中删除链结点,直到链表剩下最后一个结点,通过一系列的循环就可以解决改进约瑟夫环问题。

二、概要设计

1、循环链表抽象数据类型定义

typedef struct LNode//定义单循环链表中节点的结构

{

int num;//编号

int pwd;//password

struct LNode *next;//指向下一结点的指针

}LNode;

2、本程序包含一下几个模块

(1)构造结点模块

LNode *createNode(int m_num,int m_pwd)

{

LNode *p;

p=(LNode *)malloc(sizeof(LNode));//生成一个结点

p->num=m_num;//把实参赋给相应的数据域

p->pwd=m_pwd;

p->next=NULL;//指针域为空

return p;

}

(2)创建链表模块

void createList(LNode *ppHead,int n) (3)出队处理模块

void jose(LNode *ppHead,int m_pwd) (4)约瑟夫环说明输出模块

void instruction()

(5)菜单模块

void menu()

(6)主函数模块

int main()

函数的调用关系图如下:

三、详细设计

1. 主函数

Case 2:建立的约瑟夫环,并输出已建立的约瑟夫环:

createList(LNode **ppHead,int n)

输出该约瑟夫环的每个人的出列顺序: jose(LNode *ppHead,int

m_pwd)

图 3 约瑟夫环函数调用关系图

菜单函数; void menu()

主函数调用函数; main()

Case 1:一个简单的输出函数,用于说明约瑟夫环; void instruction()

Case 0:default : 输入0,退出 exit(0);

根据流程图,主函数程序如下:

int main()

{

int n,m,x;

LNode *ppHead=NULL;

menu();

for(;;){

printf("\n请选择要执行的操作:"); Main()开始

Menu()功能菜单

功能1:约瑟夫环说明

功能2:按要求求解

约瑟夫环

功能3:退出系统输入总人数n

输入开始上线数:m

输入每个玩家的密码

调用:createList(&ppHead,n);

jose(ppHead,m);函数求解所需的密码序列选择要执行的

操作

程序运行完,自动返

回到功能菜单

图4 主函数数据流程图

scanf("%d",&x);

system("cls");

switch(x){

case 1:

printf("****************************************************************\n");

printf("约瑟夫环:\n");

printf(" 编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n");

printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n");

printf("按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列,将他的密码\n");

printf("m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n");

printf("直到所有人全部出列为止.编程打印出列顺序.\n");

printf("****************************************************************\n");

main();

break;

case 2:

printf("\n请输入总人数n:");

scanf("%d",&n);

printf("请输入开始上限数m:");

scanf("%d",&m);

createList(&ppHead,n);

printf("\n");

printf("出队顺序:\n");

jose(ppHead,m);

printf("\n约瑟夫环游戏结束!\n");

main();

break;

case 0:

exit(0);

default:

system("cls");

printf("\n您选择的操作有误,请重新选择...\n\n\n");

main();

}

}

return 0;

}

2.链表的创建

/*创建单向循环链表ppHead ,人数个数为n ,并输入每个人的密码值,若建立失败则生成头结点,让cur 指向他,若建立成功则插入结点P ,cur 指向的数据元素为p,后续为"空"的节点,再把P 插入循环链表ppHead 中*/ 根据流程图,创建链表函数程序如下: void createList(LNode **ppHead,int n) { int i,m_pwd;

LNode *p,*cur;//cur:浮标指针

for(i=1;i<=n;i++)

createList ();

从主函数中获取玩家信息n

如果n>0 创建循环单链表,储存各个玩家密码

退出

创建链表完成返回主函数main()

创建储存玩家密码的循环单链表的方法

Main()函数 图5 创建链表函数的数据流程图

{

printf("输入第%d个人的密码:",i);

scanf("%d",&m_pwd);//输入持有密码

p=createNode(i,m_pwd);//调用构造结点函数

if(*ppHead==NULL)//如果头结点为空

{

*ppHead=cur=p;//生成头结点,让cur指向他

cur->next=*ppHead;//cur的指针域指向自身}

else//如果不为空,则插入结点

{

p->next = cur->next;

cur->next = p;

cur= p;//cur指向新插入结点

}

}

printf("完成创建!\n"); //提示链表创建完成

}

3.出队处理

/*p 指向要删除节点的前一个节点,ppHead 指向要删除的节点,使p=ppHead ,ppHead 再指向要删除节点的下一个节点,使p 和ppHead 链接,输出p 指向节点的编号和密码值,释放ppHead ,如此循环,直至把所有节点都打印和删除为止!*/

根据流程图,出队函数程序如下: void jose(LNode *ppHead,int m_pwd) {

Main()函数 从循环链表中按初始密码依次扫描,找出对应的玩家序列

输出其持有的密码i=ppHead->pwd; j=ppHead->num;

移动浮标指针

m_pwd=ppHead->pwd;

输出密码后,删除相应的结点,并释放所占的储存空间free(ppHead); ppHead=p->next;

执行完后返回主函数

jose();出队函数

出队处理的方法

图6 出队函数的数据流程图

int i,j;

LNode *p,*p_del;//定义指针变量

for(i=1;p!=ppHead;i++){

for(j=1;j

p=ppHead;//p赋值为ppHead,p指向要删除结点的前一个结点

ppHead=ppHead->next;//ppHead指向下一个元素

}

p->next = ppHead->next;//p结点与头结点链接

i=ppHead->pwd;//i赋值为ppHead->pwd

j=ppHead->num;//j赋值为ppHead->num,j为要删除的密码值

printf("第%d个人出列,密码:%d\n",j,i);

m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd

free(ppHead);//释放头结点

ppHead=p->next;//ppHead重新赋值给p->next,即释放前的ppHead->pwd指针//删除报数结点

}

i=ppHead->pwd;//i赋值为ppHead->pwd

j=ppHead->num;//j赋值为ppHead->num

printf("最后一个出列是%d号,密码是:%d\n",j,i);

free(ppHead);//释放头结点

}

4. 约瑟夫环说明模块

void instruction()

{

printf("****************************************************************\n");

printf("约瑟夫环:\n");

printf(" 编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n");

printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n");

printf("按顺时针方向自1开始顺序报数,报到时停止.报m的人出列,将他的密码\n");

printf("m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n");

printf("直到所有人全部出列为止.编程打印出列顺序.\n");

printf("******************************************************\n");

return 0;

}

5. 菜单模块

void menu(){

printf("**************************约瑟夫环*****************************\n");

printf("

\n");

printf(" [1]约瑟夫环问题的阐述\n");

printf(" [2]按要求求解约瑟夫环\n");

printf(" [0]退出\n");

printf("************************** 欢迎使用!****************************\n"); }

四、程序调试与测试

1. 调用模块时,结点结构的调用与其他模块产生冲突,导致每一行都出现两次错误,加入子函数的声明后错误消失。

2 . 刚开始时曾忽略了一些变量参数的标识"&"和“*”,使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。

3. 本次课程设计采用数据抽象的程序设计方法,将程序划分为三个层次结构:元素节点、单向循环链表,主控制模块。思路较为清晰,实现调用顺利。经过本次实验,使我对数据结构这门课程有了进一步的了解,每一个程序经过需求分析、概要设计、详细设计之后,思路即清晰呈现,程序也很快就出来了,最后经过调试、运行又有新的体验。

<测试用例>

这是一个使用循环链表的经典问题。本程序开始运行界面如下:

选择1进入约瑟夫环问题阐述。

①选择2,输入下列数据测试:

图7 约瑟夫环开始运行界面

图8 约瑟夫环问题阐述

请输入总人数n:7

请输入开始上限数m:20;

请依次输入每个人的密码:3 1 7 2 4 8 4

6 1 4

7 2 3 5

出队顺序:

图9 约瑟夫环测试1 ②继续选择2,输入下列数据测试:

请输入总人数n:5

请输入开始上限数m:30

请依次输入每个人的密码:3 4 5 6 7

出队顺序:5 3 1 2 4

测试完成,选择0退出。

设计总结

我的这次数据结构课程设计的题目是:《约瑟夫环》,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构,尤其是对单循环链表上基本运算的实现,

图11 约瑟夫环测试3

汇编语言课程设计

沈阳大学

2.3 MASM的介绍 MASM是微软公司开发的汇编开发环境,拥有可视化的开发界面,使开发人员不必再使用DOS环境进行汇编的开发,编译速度快,支持80x86汇编以及Win32Asm是Windows下开发汇编的利器。它与windows平台的磨合程度非常好,但是在其他平台上就有所限制,使用MASM的开发人员必须在windows下进行开发,历经二三十年的发展,目前MASM的版本已升至6.15,支持MMX Pentium、Pentium II、Pentium III及Pentium 4等指令系统。 2.4总体设计功能 本次课程设计的内容是采用汇编语言设计一个运行于计算机的“霓虹灯”的模拟显示 程序,由$及*字符相间,从两侧向中间螺旋汇聚直至形成一个矩形,这就要求该霓虹灯能够动态地进行变化;霓虹灯模拟显示程序主要是进行程序循环调用,可以通过CMP、JMP、JZ、RET等命令进行跳转。由于是霓虹灯的模拟显示,因此在进行程序循环调用前需要进行数据段定义,以使子程序在进行调用时能够根据数据段的定义来执行,最后显示结果。 定时器中断处理程序:计数器中断的次数记录在计数单元count中,由于定时中断的引发速率是每秒18.2次,即计数一次为55ms,当count计数值为18时,sec计数单元加一(为1秒)。 视频显示程序设计:一般由DOS 或BIOS调用来完成。有关显示输出的DOS功能调用不多,而BIOS调用的功能很强,主要包括设置显示方式、光标大小和位置、设置调色板号、显示字符、显示图形等。用INT 10H中断即可建立某种显示方式。用DOS功能调用显示技术,把系统功能调用号送至AH,把程序段规定的入口参数,送至指定的寄存器,然后由中断指令INT 21H来实现调用。 键盘扫描程序设计:利用DOS系统功能调用的01号功能,接受从键盘输入的字符到AL寄存器,以及检测键盘状态,有无输入,并检测输入各值。 2.5详细功能设计 2.5.1主程序功能 主程序通过调用各个子程序来实现清屏,改变图形等功能,具体调用过程如图1所示。 沈阳大学

约瑟夫环课程设计实验报告

《数据结构》 课程设计报告 课程名称:《数据结构》课程设计课程设计题目:joseph环 姓名: 院系:计算机学院 专业: 年级: 学号: 指导教师: 2011年12月18日

目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 (1)熟练使用C++编写程序,解决实际问题; (2)了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; (3)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2、需求分析 1、问题描述: 编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求: 利用不带表头结点的单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。 3、测试数据: m的初值为20,n=7 ,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么? 输出形式:建立一个输出函数,将正确的输出序列

3、课程设计报告内容 概要设计: 在理解了题目后,我先想到的是我们所学的单链表,利用单链表先建立循环链表进行存贮,建立完循环链表后,我将所要编写的函数分为了两块,一块是经过学过的单链表改编的循环链表的基本操作函数,还有一块是运行约瑟夫环的函数。 详细设计: 我先建立一个结构体,与单链表一样,只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时(不知道为什么我写程序里总是编译出现错误){ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果:

汇编语言-课程设计1

) 汇编语言课程实验报告 实验名称 课程设计1 实验环境 硬件平台:Intel Core i5-3210M 操作系统:DOSBox in Windows 软件工具:Turbo C , Debug, MASM 实验内容 《 将实验7中的Power idea公司的数据按照下图所示的格式在屏幕上显示出来。 实验步骤 1.要完成这个实验,首先我们需要编写三个子程序。第一个子程序是可以显示字符串到屏 幕的程序,其汇编代码如下: ;名称:show_str

;功能:在屏幕的指定位置,用指定颜色,显示一个用0结尾的字符串 ;参数:(dh)=行号,(dl)=列号(取值范围0~80),(cl)=颜色,ds:si:该字符串的首地址 ;返回:显示在屏幕上 ¥ show_str: push ax push cx push dx push es push si push di mov ax,0b800h - mov es,ax mov al,160 mul dh add dl,dl mov dh,0 add ax,dx mov di,ax mov ah,cl . show_str_x: mov cl,ds:[si] mov ch,0 jcxz show_str_f mov al,cl mov es:[di],ax inc si inc di 【 inc di jmp show_str_x show_str_f: pop di pop si pop es pop dx pop cx } pop ax ret 2.第二个程序是将word型数据转换为字符串,这样我们才能调用第一个程序将其打印出

约瑟夫问题数据结构实验报告汇总.

中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称:数据结构 年级: 专业:信息管理与信息系统 指导教师: 实验地点:管理学院综合实验室 完成日期: 小组成员: 2012 学年至2013 学年度第1 学期

一、实验目的 (1)掌握线性表表示和实现; (2)学会定义抽象数据类型; (3)学会分析问题,设计适当的解决方案; 二、实验内容 【问题描述】:编号为1,2,…,n的n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自 1 开始顺序报数,报到m 时停止报数。报m 的人出列,将他的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从1 报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】:利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 【测试数据】:m 的初值为20;密码:3,1,7,2,4,8,4(正确的结果应为6,1,4,7,2,3,5)。 三、实验步骤 (一)需求分析 对于这个程序来说,首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列,也即删除这个节点,同时建立这个节点的前节点与后节点的联系。由于是循环计数,所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据(即n个人的编码等),模拟约瑟夫的显示过程,按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值 m,从第一个人开始按顺时针方向自1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 值,从他在顺时针方向上的下一个人开始重新从 1 报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 程序执行的命令(1)构造单向循环链表。 (2)按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20;密码:3,1,7,2,4,8,4(正确的结果应为 6,1,4,7,2,3,5) (1)、插入:在把元素插入到循环链表中时,由于是采用的头插法,所以我保留了front头结点。在每加入一个节点时,都会直接连接在front后面,从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下:

约瑟夫环实验报告

一.需求分析 1.约瑟夫环(Joseph)问题的一种描述是:编号为1,2……,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,有用户在键盘上输入演示程序中规定的运算命令,相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括: 1)输入初始密码和人数2)输入所有人的密码3)显示输入的所有人的编号及相应的密码4)输出出列密码及编号5)结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3,1,7,2,4,8,4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据,后面两组为边缘数据 二、概要设计 为实现上述功能,应以有序单向循环链表表示约瑟夫环。为此,需要有一个抽象数据类型。该抽象数据类型的定义为: ADT LinkList { 数据对象:D={ ai | ai ∈termset,i=1,2,……n,n>=0}, termset中每个元素包含编号,密码,和一个指向下一节点的指针数据关系:R1={ | ai-1, ai ∈D , i=2,……n} 基本操作: LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值 int size(LinkList L);//求链表的节点个数 Status ScanList(LinkList L);//遍历单向循环链表 Status Joseph(LinkList &L,int m);//约瑟夫环的实现 } 此抽象数据类型中的一些常量如下:#define TRUE 1 #define FALSE 0 #define OK 1

汇编课程设计

燕山大学 汇编语言课程设计说明书 题目:计算机钢琴程序 交通灯控制系统 学院(系):信息科学与工程学院 年级专业: 10级计算机科学2班 学号: 100104010113 学生姓名:马强 学号: 100104010116 学生姓名:夏洋 指导教师:何海涛、邹晓红 完成日期: 2013年7月3日

目录 1.课程设计的目的和意义........................................................................................................... - 2 - 1.1课程设计目的................................................................................................................ - 2 - 1.2课程设计的意义............................................................................................................ - 2 - 2.题目一:计算机钢琴程序....................................................................................................... - 2 - 2.1系统的主要功能............................................................................................................ - 2 - 2.2总体设计方案................................................................................................................ - 2 - 2.2.1扬声器驱动方式................................................................................................. - 2 - 2.2.2延时原理............................................................................................................. - 3 - 2.2.3键盘控制发声程序............................................................................................. - 4 - 2.2.4设计总结............................................................................................................. - 5 - 2.3作品使用说明................................................................................................................ - 6 - 3.题目二:交通灯控制系统....................................................................................................... - 6 - 3.1系统的主要功能............................................................................................................ - 6 - 3.2 系统工作原理............................................................................................................... - 6 - 3.2.1 8259的工作原理................................................................................................ - 6 - 3.2.2 8255A的工作原理:...................................................................................... - 7 - 3.2.3 8253的工作原理:............................................................................................ - 7 - 3.3总体设计方案................................................................................................................ - 7 - 3.3.1程序流程图......................................................................................................... - 8 - 3.3.2接口电路图....................................................................................................... - 11 - 3.4交通灯的设计总结...................................................................................................... - 11 - 4.课程设计心得体会................................................................................................................. - 12 - 5.参考文献................................................................................................................................. - 12 - 6.附录:程序代码..................................................................................................................... - 12 - 6.1计算机钢琴程序代码.................................................................................................. - 12 - 6.2交通灯控制系统代码.................................................................................................. - 14 -

约瑟夫问题算法及数据结构课程设计报告

线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构,有顺序和链式两种存储结构,在实际中应用十分广泛,而链表又分为单链表和循环链表,队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题,是顺序编号的一组n个人围坐一圈,从第1个人按一定方向顺序报数,在报到m时该人出列,然后按相同方法继续报数,直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构,建立线性表; 2、利用顺序存储结构求解约瑟夫环问题; 3、利用单链表和循环链表分别求解约瑟夫环问题; 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7,报数为1至3。 四、算法思想 由于用到四种不同的存储结构,它们的算法思想依次是: 1、首先建立一个顺序表模拟整个约瑟夫环,手动输入顺序表长(即参加约瑟夫循环的人数)和循环的次数和表元素。用已经输出总人数和顺序表长作比较,作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环,首先检查顺序表此次是不是我们设立的标记,如果不是则循环次数加1,当达到要求的循环次数时就将循环次数设置为0,输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置,作为新的判断条件,每次报到表尾的时候,我们都将重新设置到表尾,作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环,手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头,并将该指针是否为空作为外层循环条件。做一个内层循环,将判断指针移动到循环要输出的数,并设立一个前指针指向该指针的前一个位置,输出该元素后,将循环次数重新赋值成该元素。接着判断前指针和判断指针比较,如果相等说明整个表已经输出完毕,否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环,手动输入人数,第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列,根据第一次循环次数,建立一个for循环,每一次循环都出队列,如果达到要求的循环次数就输出,否则进队列,这样这个数字就出现在队尾。第一个数输出后,以队列的非空作为循环条件,判断方式如上。 4、用循环队列建立约瑟夫环,将1-7个元素依次进入循环队列,以队列的长度作为与已输出的元素作为判断条件,对每一个输出后的元素重新赋值以为标记。对于每次循环,首先检查该该位置的元素是不是我们设立的标记-1,如果不是则循环次数加1,将队首指针移

数据结构实验报告(约瑟夫环)

《数据结构》课程实验 实验报告 题目:Joseph问题求解算法的设计与实现专业:计算机科学与技术 班级: 姓名: 学号: 完成日期:

一、试验内容 约瑟夫(Joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作:插入、删除、查找等运算,能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--

四、源程序代码 //Joseph问题求解算法的设计与实现 #include #include struct list { int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数 . list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { key=rand() % 100; printf("第%d个人的密码:%d\n",i,key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; do{ printf("\n第%d号成员的密码为:%d",p->num,p->code); //输出链表. p=p->next; }while(p!=head); printf("\n\n输入第一个报的数:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do

课程设计(约瑟夫环)[1]

课程设计报告 课程名称:数据结构课程设计课程设计题目:约瑟夫环问题 姓名:余明旭 系:计算机科学与技术专业:计算机科学与技术年级:2010级 学号:100310236 指导教师:陈老师 职称:学生

一、需求分析 1、输入的形式和输入值的范围: 本程序中,输入报数上限值n,初始报数者s,初始报数者携带的密码m1,n-2个人携带的密码m(最后一人携带的密码没用),均限定为正整数,输入的形式为一个以“回车符”为结束标志的正整数。 2、输出的形式: 从屏幕显示出列顺序。 3、程序所能够达到的功能: 提供用户从键盘输入,Joseph约瑟夫环的必要数据,并显示出列顺序。4、测试数据: 输入 8 1 4 4 4 4 4 4 4 输出 4 8 5 2 1 3 7 6 一、详细设计 以单向循环链表实现该结构: 1、抽象数据类型的定义为: struct LNode { ElemType data; LNode* next; }; 2、本程序包含以下模块: 主程序模块: Void main() { 初始化; 输入数据; 执行功能; 显示结果; } 各功能模块:实现单链表的各项功能。 Void fun() { } 3、各模块的调用关系:

三、调试分析 程序的编写和调试基本正常,遇到的问题主要是:指针的指向的边界问题,如何每次正确找到出列的人的位置。 解决方法: for(int j=1;jnext; if(cp==HL) { ap=HL; cp=HL->next; } } a[i]中存储了每个人的密码,就可以准确知道每个人的位置。 通过约瑟夫环算法的课题设计让我理解了循环队列,不单单只是书本上文字的循环队列的概念,更多是自己能够通过实际的操作对循环队列有了更深的了解。上机的编程的过程是对数据结构的基础的进一步的巩固。学习过程体验到了学习的乐趣,实验课题使我认识到平时学习的漏洞和知识的缺乏,为以后的学习敲了一下警钟,数据结构是门基础,要学习扎实才行。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。 数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安 排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。数据结构课程的主要目的是介绍一些常用的数据结构,阐明数据结构内在的逻辑关系,讨论它们在计算机中的存储表示,并结合各种数据结构,讨论对它们实行的 各种运算的实现算法。很多算法实际上是对某种数据结构施行的一种变换,研究算法也就是研究在实施变换过程中数据结构的动态性质。 学习的过程需要合作,而且在合作中提到自己的编程水平,借鉴他人好的地方,改掉原先自己不足,书本知识的与实际的联系,使自己的编程不在局限于原来的纸上谈兵,更多的是积累了经验,培养了能力。 四、用户手册 如何使用,详细步骤,根据提示输入。 示例: 主程序 Void main() 模块 Viod fun()

(新)汇编语言课程设计四则运算

计算机与信息工程学院《汇编语言》课程设计四则运算器的设计 专业:计算机科学与技术 班级:控制11-2班 姓名: 倪天天 学号:2011025745 指导教师:郝维来 2013年6月28日

摘要 计算器是最简单的计算工具,简单计算器具有加、减、乘、除四项运算功能。想要用汇编语言实现简单的计算器,就必须通过对数据存储,寄存器的使用,加减乘除相关指令以及模块的调用等汇编语言知识进行运用,以实现一个基本功能完善,界面友好,操作简便易行的计算器。用汇编语言实现简单计算器还涉及到输入输出模块的设计,加减乘除运算的判断以及退出程序的判断的设计。通过对各种指令的合理使用,设计各个功能模块。当实现各个程序模块后,通过程序的调用最终实现一个简单的计算器。 关键词:计算器,汇编语言,四则运算,功能模块

Abstract Calculator is the easiest calculation tools, a simple calculator with addition, subtraction, multiplication, division four arithmetic functions. Want to use assembly language to achieve a simple calculator, you must pass on the data storage, register usage, addition, subtraction, and related instructions such as assembly language module calls the use of knowledge in order to achieve a basic functional, user-friendly, easy to operate easy calculator. Using assembly language to achieve a simple calculator also involves the design of input and output modules, the judgment of arithmetic operations and exit the program to judge design. Through the rational use of various commands, design various functional modules. When implementing various program modules, through a call to the ultimate realization of the program a simple calculator. Keyword:Calculator, assembly language, four arithmetic, functional modules

数据结构实验报告—约瑟夫问题求解

《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目:编号 1,2,....,n的n个人顺时针围坐一圈,每人持有一个密码(正整数)。 开始选择一个正整数作为报数上限m,从第一个人开始顺时针自 1 报数,报到m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新从 1 报数,直至所有人全部出列。 2. 基本要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序印出个人的编号。 3. 测试数据: n=7,7 个人的密码依次为:3,1,7,2,4,8, 4.m初值为6(正确的出列顺序 应为 6,1,4,77,2,3)。 二、需求分析 1. 本程序所能达到的基本可能: 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈,用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m,对该链表进行遍历,直到第 m个结点,令该结点的密码值作为新的密码值,后删除该结点。重复上述过程,直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围: 程序运行后提示用户输入总人数。输入人数 n 后,程序显示提示信息,提示用户输入第 i个人的密码,在输入达到预定次数后自动跳出该循环。程序显示提示信息,提示用户输入 初始密码,密码须为正整数且不大于总人数。 3.输出形式 提示用户输入初始密码,程序执行结束后会输出相应的出列结点的顺序,亦即其编号。 用户输入完毕后,程序自动运行输出运行结果。 4.测试数据要求: 测试数据 n=7,7 个人的密码依次为:3, 1, 7, 2, 4, 8, 4。 m初值为 6(正确的出列 顺序应为6, 1, 4,7, 2, 3, 5)。 三、概要设计 为了实现上述功能,应用循环链表来模拟该过程,用结构体来存放其相应的编号和密码

数据结构课程设计——约瑟夫环报告(含代码)

#include #include typedef struct LNode { //数据域 int cipher; //密码 int number; //编号 struct LNode *next; //指针域 }LNode,*LinkList; void InitList(LinkList &L) //创建一个只有头结点链表{ L = (LinkList)malloc(sizeof(LNode)); if(!L) { exit(1); printf("/n/nError!/n/n"); } L->next = L; } void CreateList(int n,LinkList &L) //初始化循环单链表 { LinkList p,q; q = L; printf("分别输入每个人的密码:"); for(int i = 1;i <= n;i++) { int k; scanf("%d",&k); if(k <= 0) { printf("\n\n密码有误!\n\n"); exit(1); } p = (LinkList)malloc(sizeof(LNode)); if(!p) { exit(1); printf("/n/nError!/n/n"); } p->cipher = k; p->number = i;

L->next = p; L = p; } L->next = q->next; free(q); } void PrintList(int x,int n,LinkList L) //输出出列顺序 { LinkList p,q; p = L; for(int i = 1;i <= n;i++) { for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf("%d ",q->number); p->next = q->next; free(q); } } int main() { printf("=============约瑟夫环==============\n\n\n"); int n,x; LinkList L; L = NULL; InitList(L); //构造空链表 printf("输入初始密码:"); scanf("%d",&x); //初始密码为x printf("\n"); printf("输入参与总人数:"); scanf("%d",&n); //总共的人数n printf("\n"); CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n"); printf("出列编号为:"); PrintList(x,n,L); //输出出列顺序 printf("\n\n"); return 0; }

汇编语言课程设计报告

农林大学金山学院 课程设计报告 课程名称:汇编语言课程设计 课程设计题目:动画设计“我爱大自然”姓名: 系:信息与机电工程系 专业:电子信息工程 年级:2008级 学号:082230066 指导教师:\ 职称:助教 2009~2010学年第二学期

目录 1 课程设计的目的 (2) 2 课程设计的要求 (2) 3课程设计报告容 (2) 3.1设计思路 (2) 3.2程序流程图 (2) 3.3设计源程序 (5) 3.4动画示意图 (19) 4 总结 (20) 5参考文献 (20) 6评分标准 (21)

动画设计“我爱大自然” 一、课程设计的目的 《汇编语言课程设计》是电子信息工程专业集中实践性环节之一,是学习完《汇编语言》课程后进行的一次全面的综合练习。其目的是: 培养学生熟练掌握汇编语言指令系统,深化和巩固指令系统和编程方法,提高学生的编程应用能力。为将来从事专业工作打下基础,培养良好的职业道德和严谨的工作作风。 二、课程设计的要求 1)具备初步的独立分析和解决问题的能力; 2)初步掌握问题分析、系统设计、程序编码、测试等基本方法和技能; 3)提高综合运用所学的理论知识和方法的能力; 4)训练用系统的观点和软件开发一般规进行软件开发,培养科学的工作方法和作风; 5)设计的题目要求达到一定工作量,并具有一定的深度和难度; 6)编写出课程设计说明书。 三、课程设计报告容 (一)设计思路 “我爱大自然”这个程序中包含了比较多的景物,既有静态的也有动态的,其中还有一段音乐。为了节省存储空间,提高程序设计的效率和质量,使程序简洁、清晰,便于阅读,同时也为了便于修改和扩充,采用子程序设计技术和宏定义,根据程序要实现的若干主要功能及个功能块要调用的公共部分,将程序划分为若干个相对独立的模块,为每个模块编制独立的程序段,最后将这些子程序根据调用关系连成一个整体。 这样,整个程序就被分为几个子程序的有机统一。根据BIOS中断调用原理,设置80×25彩色文本显示方式,分别编写一个子程序显示“I LOVE NATURE,LET US GO AIRING”和一个子程序在屏幕上“画”树。这两个子程序所体现出来的事物都是的。为了实现小鸟

约瑟夫环-joseph环-数据结构与算法课程设计报告

合肥学院 计算机科学与技术系 课程设计报告 2009~2010学年第二学期 课程数据结构与算法 课程设计名称joseph环 学生姓名朱玉庭 学号0804012029 专业班级08计本(2) 指导教师王昆仑、张贯虹 2010 年06月08号

一、问题分析和任务定义: 约瑟夫环是一个数学游戏,根据游戏内容的描述,能够很容易的看出,游戏中的玩家顺时针围坐一圈,能够很容易的发现,这跟本课上的单循环链表非常相似,所以可以通过单循环链表存储结构模拟此过程,当游戏中的玩家出列时,可以通过删除单循环链表中的结点来实现。 二、数据结构的选择和概要设计: 选择带为指针的单循环链表来解决这个问题,先建立一个空链表,然后根据人数生成具有相应结点的单循环链表,知道密码后,通过循环来找到对应的结点,然后将该结点的编号输出,改变密码,最后删除结点,以此类推,知道编码全部输完,即可得到结果序列。 三、详细设计和编码: 本题目是通过单循环链表存储结构来模拟此过程的,首先要先明确该单循环链表中结点的结构类型,定义如下: typedef struct Node { int key; //每个人持有的密码 int num; //这个人的编号 struct Node *next; //指向下一个结点 }Link; 当生成单循环链表时,就需要用到课本上创建单循环链表的有关内容了,可以先通过子函数Link *InitList()建立一个空链表,返回指针L,然后将返回的指针代入子函数Link *Creater(Link *L,int n)的形参中,对循环链表进行初始化,并且也返回一个指针,然后再将这个返回的指针代入到输出函数void Output(Link *L,int n,int m)的形参中,要想根据题目要求完成序列的输出,需要通过两个for循环来实现,第一个循环for(i=1;i<=n;i++) ,因为一个用n个人,所以结果要输出n个编号,这个循环每循环一次输出一个编号即printf("%d ",q->num),并将该编号下的密码赋值给m 即m=q->key,当循环完毕时正好将编号全部输出,第二个循环for(j=1;jnext; q=p->next; 用以找到相应的结点,并用指针q指向它,当完成了编号的输出和密码的赋值后,删除q指向的结点,将两个循环适当结合,即可输出正确的结果序列,其中的人数n和初始密码在主函数中确定。 四、上机调试: (1)有2个玩家,初始密码为21; (2)有3个玩家,初始密码为5:

汇编语言课程设计-学生成绩管理系统

1、课程设计的目的、任务 《汇编语言》课程设计对于巩固汇编语言理论知识,加强学生的实际动手能力和提高学生综合素质十分必要。课程设计的目的主要是通过程序设计方法和技能的基本训练,巩固在课堂上学到的有关程序设计的基本知识和基本方法,通过实际动手能力的培养,进一步熟悉汇编语言的结构和使用方法,达到能独立阅读、编制和调试一定规模的汇编语言程序的水平。 2、软件需求分析和设计 2.1学生成绩管理系统是对学生成绩的管理,其中包括以下几个模块: (1).插入一个数据(插入学生学号以及语数外三个成绩)。 (2)修改一个数据。 (3)删除学生成绩数据。 (4)查找学生成绩。 (5)查看学生成绩的排名 (6)查看学生成绩分布 (7)按esc键退出系统 2.2学生成绩管理系统应该包含以下信息:学号,语文成绩,英语成绩,数学成绩。因此,系统应该提供以下功能: (1)输出显示菜单。 (2)输入学生的成绩 (3)修改学生成绩 (4)删除学生成绩 (5)查询学生成绩 (6)显示学生成绩排名 (7)显示成绩分布统计 (8)按esc键退出系统

2.3依据程序的功能需求,该系统的功能结构图如下 系统功能结构图 2.4 程序流程图:

主程序流程图查找学生成绩

插入学生学号及成绩修改学生的成绩 显示各个学科各分数段的人数 3、程序实现说明

3.1学生管理系统中各子程序如下: (1).输入全部学生学号以及语文,英语,数学三科的成绩。 子程序名:insert 子程序描述:该子程序为输入字程序。系统在开始的时候是没有数据的,通过该子程序可以初始化系统,将学生的学号及成绩输入系统。 代码: insert proc near ;定义进程子程序:插入学生,学号及 成绩 call input ;调用input add n,1 ret insert endp (2).修改输入的成绩。 子程序名:modify 子程序描述:通过子程序修改学生的成绩 代码: modify proc near ;定义进程子程序:修改学生学号,成绩 md1:output mess1 ;输出mess1 shuru ;调用宏shuru:二位数据输入 mov bl,n mov bh,0 mov al,dl mov si,0 md: cmp al,xh[si] ;先查找输入的学生是否存在 je qq1_1 ;查到的话,就跳转到qq1_1输入修改的值, 也就是重新输入。;结果相等则跳转到qq1_1 add si,1

数据结构课程设计报告约瑟夫环完整版

******************* 实践教学 ******************* 兰州理工大学 软件职业技术学院 2011年春季学期 算法与数据结构课程设计 题目:约瑟夫环 专业班级: 姓名: 学号: 指导教师: 成绩:

摘要 约瑟夫环问题是典型的线性表的应用实例,其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备,易使用等特点。 经过分析,我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具,利用其提供的各种面向对象的开发工具,尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象,首先在短时间内建立系统应用原型,然后,对初始原型系统进行需求迭代,不断修正和改进,直到形成用户满意的可行系统。 关键词:单循环链表;c语言;约瑟夫环;

序言 数据结构是研究数据元素之间的逻辑关系的一门课程,以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练,培养分析和编程等实际动手能力,系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题,循环链表是一种首尾相接链表,其特点是无须增加存储容量,仅对表的链接方式稍作改变,使表处理更加灵活,约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例,了解单链表和单循环链表的相同与不同之处,进一步加深对链表结构类型及链表操作的理解。 通过该课程设计,能运用所学知识,能上机解决一些实际问题,了解并初步掌握设计、实现较大程序的完整过程,包括系统分析、编码设计、系统集成、以及调试分析,熟练掌握数据结构的选择、设计、实现以及操作方法,为进一步的应用开发打好基础。

相关主题
相关文档 最新文档