课题一joseph环 ………………………………………………1
1．1 问题的提出 …………………………………………………………… 1 1. 2概要设计 ………………………………………………………………… 1 1．3流程图 …………………………………………………………………… 2 1．4 源代码 …………………………………………………………………… 3 1．5 结果与分析 ……………………………………………………………… 6
课题二 拓扑排序 ……………………………………………… 7
2．1 问题的提出 …………………………………………………………… 7 2. 2 概要设计 ……………………………………………………………… 7 2．3 流程图 ………………………………………………………………… 8 2．4 源代码 ………………………………………………………………… 9 2．5 结果与分析 …………………………………………………………… 13
课题三 纸牌游戏 …………………………………………… 15
3．1 问题的提出 …………………………………………………………… 15 3. 2 概要设计 ……………………………………………………………… 15 3．3流程图 ………………………………………………………………… 16 3．4 源代码 ………………………………………………………………… 17 3．5 结果与分析 …………………………………………………………… 18
课程设计总结 ………………………………………………… 20 参考文献 ……………………………………………………… 21
课题一 joseph环
1．1 问题的提出1.1．问题的提出
1．任务：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每
个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
2．测试数据：输入（范围：整型数据）
总成员数：7
各成员密码：3 1 7 2 4 7 4 初始值m:6
输出（范围：大于等于1，小于等于n的整型数据） 出列成员序号：6 7 4 1 5 3 2
1.2 概要设计 2.1算法思想
利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。
joseph环的组成成员由密码（password）和序号(No)组成，循环链表的存储结构如下：
typedef struct LNode {
int password; //密码 int No; //序号
struct LNode *next; //下一成员指针 }member; //组成成员结构体
1．3流程图 根据算法思想，画程序流程图如下：
开始 输入m、n m>0且n>0的整数 建立含n个结点的链表且用head指向第一个元素，结点数据域包含password、No、以及指向下一结点的指head=>p n≥2 (m%n)==0?n:m%n=>1=>i 输出p→No 结束 i typedef struct LNode { int password; //密码 int No; //序号 struct LNode *next; //下一成员指针 }member; //组成成员结构体 typedef int status; #define OVERFLOW -2 #define OK 1 #define ERROR 0 #include status CreateList_Circle(member **,int); status DeleteNode(member **); status main() { int n,m; member *head=NULL,*p=NULL; //头指针即首成员地址，遍历指针p printf (\"Please enter number of people:\\n\"); scanf (\"%d\总成员数 while (n<=0) { printf (\"n must be positive, please enter again:\\n\"); scanf (\"%d\ } if(!CreateList_Circle(&head,n)) //创建循环链表，返回头指针head return OVERFLOW; printf (\"Please enter initial m:\\n\"); scanf (\"%d\初始值m while (m<=0) { printf (\"m must be positive, please enter again:\\n\"); scanf (\"%d\ } printf (\"\\nThe order is:\\n\"); p=head; while (n>=2) //寻找出列成员 { int i; m=(m%n==0)?n:m%n; //化简m值 for (i=1;i printf (\"%d\\n\输出出列成员序号 m=p->password; //修改m DeleteNode(&p); //删除链表中的出列成员 n--; //成员数自减 } printf (\"%d\\n\输出最后一个成员序号 return OK; } status CreateList_Circle(member **p_head,int n) { //此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址 int i; member *tail,*p; *p_head=(member *)malloc(sizeof(member)); if (!(*p_head)) return OVERFLOW; (*p_head)->No=1; //储存成员一序号 printf (\"Please enter password of No. 1:\\n\"); scanf (\"%d\储存成员一密码 tail=*p_head; tail->next=NULL; for (i=2;i printf (\"Please enter password of No. %d:\\n\ scanf(\"%d\储存成员密码 tail->next=p; tail=p; } tail->next=*p_head; return OK; } status DeleteNode(member **pp) { //此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其free member *temp; (*pp)->password=((*pp)->next)->password; (*pp)->No=((*pp)->next)->No; temp=(*pp)->next; (*pp)->next=(*pp)->next->next; free(temp); return OK; } 1．5 结果与分析.4 测试及性能分析 1．此程序的时间复杂度是O(m*n)。 2．本次设计主要用到了循环链表的相关知识，求joseph环的问题。调试过程中，一开始没有想到“指向指针数据的指针变量”，使得问题一直没有明朗。 3．是否需要化简m值的语句：m=(m%n==0)?n:m%n;可根据m与总成员数的值的大小来判断。 当m〈=n时，则此步是可以删除的； 当m>n时，则此步最好不删除，特别是当输入的m值很大，则化简m值的操作是很必要。 4. 遇到的问题主要是：指针的指向的边界问题，但根据运行程序时的出错提 示，很快也就解决了。 5.测试的结果如下： 课题二 拓扑排序 2．1 问题的提出2.1 问题的提出 任务：编写函数实现图的拓扑排序。 程序所实现的功能： 建立对应的邻接表，对该图进行拓扑排序，并显示排序 结果。 输入：顶点数, 边数及各顶点信息(数据格式为整形) 输出：拓扑排序结果。 2. 2 概要设计 1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。 2．解决拓扑排序的方法如下： （1）在有向图中选一个没有前驱的顶点且输出之。 （2）从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。 3．构造邻接表图：typedef struct{ AdjList vertices; int vexnum,arcnum; }Graph;//邻接表图 4. 为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedef struct stack{ int *base; int *top; int stacksize; }sqstack;//栈的结构，存储图的顶点序号 2．3 流程图2.根据算法思想，画流程图如下： 开始 建立一个栈，存储图的 顶点的序号 设辅助数组indegree记录图的各顶点的入度值，并 将indegree数组各变量赋初值。 输入图的顶点数、边数 用邻接表法建图，并计算出 indegree数组中各变量值 根据indegree数组将入度 为0的顶点入栈 count对输出顶点计数 0=>count 栈不空 删除栈顶元素,赋给i 输出第i个顶点值 输出“拓扑 排序成功” count++ 将与第i个顶点链接的各顶点入度减1 顶点序号入栈 顶点入度为0 count //采用尾插法创的邻接图 #include const int STACK_INIT_SIZE=100; const int ERROR=0; typedef struct stack{ int *base; typedef struct lnode { typedef struct node2 { typedef struct{ void Initstack(sqstack &s) { s.base=new int; AdjList vertices; int vexnum,arcnum; char data; ArcNode *fristarc; int adjvex; struct lnode *next; int *top; int stacksize; }sqstack;//栈的结构，存储图的顶点序号 }ArcNode;//弧结点 }VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧 }Graph;//邻接表图 } if(!s.base) exit(0); s.top=s.base; s.stacksize= STACK_INIT_SIZE; void Push(sqstack &s,int &e) { } int Emptystack(sqstack &s) { } int Pop(sqstack &s,int &e) { } void CreatGraph(Graph &G,int *indegree) { cout<<\"请输入图的顶点数和弧数(且顶点数不能超过\"< cout<<\"请输入顶点值:\"< return ERROR; e=*--s.top; if(s.base==s.top) return 1; return 0; else *s.top++=e; } } indegree[i]=0; for(i=0;i cout<<\"请输入第\"< exit(0); indegree[n-1]++;//求每个顶点的入度值 p->adjvex=n-1; p->next=G.vertices[m-1].fristarc; G.vertices[m-1].fristarc=p; int Toposort(Graph &G,int *indegree) { sqstack S; Initstack(S); for(int i=0;i while(!Emptystack(S)) { Pop(S,i); cout< Push(S,i); } { } //相邻接的顶点的入度 int k=p->adjvex; if(!(--indegree[k])) Push(S,k); if(count } { int main() Graph G; } int *indegree; indegree=new int; if(!Toposort(G,indegree)) { } else { } return 0; cout< 2．5 结果与分析2.4 测试及性能分析 1．它的时间复杂度是O(G.vexnum+G.arcnum)。 2. 整个程序的关键就是采用尾插法创的邻接表图，运用栈来实现各个数值 的输入输出及存储。 3．注意*的使用，并不是什么情况下都用*，它有时候会造成数据破坏，利 用破坏的值进行运算，结果可想而知，所以，如果没返回值时，一般不要用。 4．为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入 度为零的顶点，此程序段书写如下： InitStack(S); 栈 }//for }//while 5．测试的数据如下： 第一组结果（有向无环图）： for (i=0;i Pop(S,i);printf(i,G.vertices[i].data);++count; //输出i号顶点 for (p=G.vertices[i].firstarc;p;p=p->next){ k=p->adj; //对i号顶点的每个邻接点的if(!(--indegree[k])) Push(S,k); //一旦入度为0，则入 并计数 入度减1 第二组结果（有向有环图）： 第一组对应的图如下： 1 2 3 5 4 第二组对应的图如下： 1 2 3 5 4 课题三 纸牌游戏 3．1 问题的提出.1 问题的提出 任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 输出的纸牌号为： 1 4 9 16 25 36 49 3. 2 概要设计 1.当每个号码每次遇到是某个数的倍数时，都会相应的翻一次，这样，每张牌会翻的次数就各不一样，可能很多次，也可能只有一两次，结果就只是要输出在经过各个不同次数的翻牌后，正面向上的牌都有哪几个。举例说明一下，比如24，第一次它是2的倍数时要从正面翻到背面，当进行到3时，就又要从背面翻回来，而到4时还要在翻，同理呢，到6.8.12„它都要来回的翻。如果它在多次的翻牌后，正面还向上了，那么它就是要输出的结果之一。 2．用#define OPPOSITE(i) i = i?0:1这个宏将牌的状态标志求反,也即为翻牌操作。 将所有的牌建立一个数组，运用for的循环嵌套执行以下操作：把52张牌初始化成正面朝上、控制基数和翻牌次数，判断最终的纸牌朝向并打印出结果，具体实现算法参看详细设计。 3．3流程图 根据算法思想，画流程图如下： 开始 设一个一维数组card[52]，并将所有变量赋初值为0，表示牌正面朝上 2=>j j≤52 j=>k k≤52 j++ k%j=0 翻牌，如果card[k-1]为0，则变为1；如果为1，则变为0 k++ 输出card数组中正面朝上的牌的序号 结束 3．4 源代码 #include #define OBVERSE 0 //正面朝上 #define ADVERSE 1 //背面朝上 #define OPPOSITE(i) i = i?0:1 //这个宏是将牌的状态标志求反,也即为翻牌操作 void main() { int card[52];//52张牌 for (int i = 0; i < 52; i++) { card[i] = OBVERSE; //将52张牌初始化成正面朝上 } for (int j=2; j<=52; j++) //此层循环是控制基数的 { for (int k = j; k <= 52 ; k++)//此层循环是控制从第几张牌开始 { if (k%j == 0)//判断第k张牌除以基数j后的余数是否为0,如为0就是能整除 { OPPOSITE(card[k-1]);//翻牌 } } } for (int h = 0; h < 52; h++)//开始打印 { if (card[h] == OBVERSE)//判断牌的状态是否为正面朝上 { printf(\"第%d张牌正面朝上\\n\} } } 3．5 结果与分析 1．这题的时间复杂度是O(52)。 2．虽然本次程序的题目难度与其他问题相比不是很高，但仍有很多问题我们 是很容易忽视的，其一：在理解题目的要求时，注意翻牌的次数可能有多次；其二：for循环的嵌套使用在书写时很容易漏掉大括弧。 3．运用更多的基础算法，使得程序和算法思想得到更好的表现，为增强算法 的可读性，则算法改进如下： #include int i,j,card[52]; for(i=0;i<52;i++)//52张牌所有状态均为1，即均为正面 card[i]=1; for(j=2;j<=52;j++) //对52张牌（序号放在i里）对2，3...52（放在j里）按i+1是否是j的倍数进行状态翻转。 for(i=0;i<52;i++) if((i+1)%j==0) card[i]=card[i]?0:1; printf(\"positive card are:\"); for(i=0;i<52;i++)//对翻转处理后状态仍然是正面的（card保持为1）的将其编号输出。 { if(card[i]) printf(\"%d \ } } 4．测试的结果如下：
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- huatuo9.cn 版权所有 赣ICP备2023008801号-1
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务