内容简介:python是世界上最好的语言
艾玛,起这个标题真不怕被人捶的(ノへ ̄、)
通过《数据结构》课程上的作业——(拓展)约瑟夫环问题的 C语言 版本和 python 版本来比较一下python是多么的简洁优雅。
Josephus来历:
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
平常的Josephus问题这里不再啰嗦了,以后看心情可能会补充~
直接看我们数据结构的作业吧!
题目:约瑟夫环(Joseph)
① 问题描述 :编号为1到n的n个人,按顺时针方向围成一个环(循环单链表),每人都持有一个密码(正整数)。任选一个正整数作为报数的上限(设为m),从第一个人开始按顺时针方向从1开始顺序报数,当报到m时,暂停报数并输出其标识(位序),同时将报数为m的人删除,并将他的密码作为新的m值,继续从1开始重新报数,直到m并输出。如此重复,直到全部人员都从队列中输出。编写程序,求出该出列顺序。
② 利用循环单链表实现 这个过程,单链表的结点约定如下:
Typedef struct LNode {
int IDCode; // 人员标识
int PWD; // 人员密码
struct Lnode *next; // 指针域
} LNode, *LinkList;
其中,L为不带头结点的单链表的头指针,mi是第i个人的密码(1≤i≤n)。请按这个约定编程。
③ 测试数据 :20≤n≤30
要求:参数n和m从键盘上输入,同时输入每个人的密码,存放在数组PWD中,利用这些参数构建单链表并完成出列顺序的输出。输入的次序为人员标识(位序)。
④ 主程序约定 如下:
main () { //以下仅仅是描述,请大家按照要求完善代码
int PWD[30]; //定义密码数组
printf(“输入人员数n”);
scanf(%d,n);
printf(“输入初始密码m”);
scanf(%d,m);
p=createJoseph( int n , int PWD); //建立Joseph环,返回指向最后一个结点的指针p
printIDCode(LinkList P , int m); //输出每个人员的编号,当m大于n时,应该取n的模
printf(“以上是张三的运行结果。”);
}
⑤ 提升练习
- 构造顺序文件存放人员密码,根据n读取前n个数据作为密码,实现以上功能;
- 最后建立的p结点的指针,指向了前面的某一个元素结点(未必是第一个),请按上述要求,输出环中的所有人员标识符。
人丑话不多,直接上代码,如有疑问,请在最下方留言,一定尽力回复!
C语言版:
#include<stdio.h> #include<stdlib.h> typedef struct LNode{ int IDCoder; int PWD; struct LNode *next; }LNode,*LinkList; int PWD[100],n,m; void initpwd(){ FILE * r=fopen("data.txt","r");//把data和编译出来的应用程序放在同一个文件夹中 if(r==NULL){ printf("\nFailed to open the file"); exit(1); } int i=0; while(fscanf(r,"%d",&PWD[i])!=EOF&&i<n){ //printf("\n%d",PWD[i]); i++; } fclose(r); } LinkList createJoseph(int n,int PWD[]){ //创建Josephus int i=0; LinkList pHead=NULL; pHead=(LinkList)malloc(sizeof(LNode)); //头节点 pHead->PWD=PWD[i]; pHead->IDCoder=i+1; pHead->next=NULL; LinkList pCurr=NULL,pPrev=NULL; pPrev=pHead; while(--n){ pCurr=(LinkList)malloc(sizeof(LNode)); i++; pCurr->PWD=PWD[i]; pCurr->IDCoder=i+1; pPrev->next=pCurr; pPrev=pCurr; } pCurr->next=pHead; return pCurr; } /*void printLink(LinkList pTail){ LinkList pCurr; LinkList pHead=pTail->next; printf("%d ",pHead->IDCoder); pCurr=pHead->next; while(pCurr!=NULL){ if(pCurr->IDCoder==1){ break; } printf("%d",pCurr->IDCoder); pCurr=pCurr->next; } printf("\n"); }*/ /*void printIDCode(LinkList pTail,int m,int tot){//这是我第一次写的,虽然通过了老师的测试,但是还是觉得挺烦(其实一开始如果m=1会有bug--)。 LinkList pCurr,pPrev,pHead; pHead=pTail->next; int i=1,outNum=m; pCurr=pPrev=pHead; while(pCurr!=NULL){ if(i==outNum){ i=1; tot--; outNum=(pCurr->PWD-1)%tot+1; printf("\n%d",pCurr->IDCoder); pPrev->next=pCurr->next; free(pCurr); pCurr=pPrev->next; while(outNum==1&&tot>1){ i=1; tot--; outNum=(pCurr->PWD-1)%tot+1; printf("\n%d",pCurr->IDCoder); pPrev->next=pCurr->next; free(pCurr); pCurr=pPrev->next; } } pPrev=pCurr; pCurr=pCurr->next; if(pPrev==pCurr){ printf("\n%d",pCurr->IDCoder); free(pCurr); break; } i++; } } */ void printIDCode(LinkList pTail,int m,int tot){//这个是问了室友之后改的 int outNum=m; LinkList pCurr,pPrev,pHead; pHead=pTail->next; pCurr=pPrev=pHead; while(n>0){ if(m==1){ for(int i=1;i<n;i++){ pPrev=pPrev->next; } } for(int i=1;i<m-1;i++){ pPrev=pPrev->next; } pCurr=pPrev->next; pPrev->next=pCurr->next; printf("\n%d",pCurr->IDCoder); m=pCurr->PWD;//懒得优化了~ free(pCurr); pPrev=pPrev->next; n--; } } int main(){ LinkList pTail; printf("please input the number of people:"); scanf("%d",&n); printf("\nplease input pwd:"); scanf("%d",&m); initpwd(); pTail=createJoseph(n,PWD); printIDCode(pTail,m%n,n); printf("\nAuthor:KISS"); return 0; }
Python版:
#!coding:utf-8 circle=[]#人环,每个人密码在下面列表中 第n个人对应 txt[n-1] txt=[3,4,5,2,1,6,4,3,2,1,5,1,12,45,3,4,5,9,88,64,1,6,5,2,3,2,5,6,7,1,5,1,3,2,54,4,54,44,55,87,3,6,5,2,6,1,5,6,7,602,5,1,3,2,54,4,88,44,55,44,1,8,5,2,4,6,4,3,2,1,5,23,12,45,3,4,5,9,23,64,3,9,5,2,1,6,5,6,7,342,5,6,3,2,54,4,88,44,44,77] n,m=raw_input('n,m:').split(' ') class person():#人的属性 def __init__(self,n,p):#构造函数 self.number=n self.password=p for i in range(int(n)):#构造人 circle.append(person(i+1,txt[i])) curindex=0#从第一个人开始 for i in range(int(n)):#开始杀人了 curindex=(curindex+int(m)-1)%len(circle)#循环列表 print str(circle[curindex].number)#显示被杀的人 m=circle[curindex].password#根据人的密码修改m del circle[curindex]#杀人ing
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 最好的Julia语言
- “Python才是世界上最好的语言”
- 我才是世界上最好的编程语言
- “最好的语言“ 25 岁了,PHP说要走向安全和开放!
- Scala是世界上最好的语言(一):Type Bound
- PHP 是世界上最好的语言?黑客偏爱用 Python
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。