- 浏览: 155468 次
- 性别:
- 来自: 昆明
文章分类
最新评论
-
北月与南安:
感谢楼主,通过这个,我学会了 Ajax与后台,项目的交互
基于JQuery+JSP的无数据库无刷新多人在线聊天室 -
吴维兴:
ddddd
基于JQuery+JSP的无数据库无刷新多人在线聊天室 -
飞行官肥皂:
赞一个,基础不好的都学会了,么么
MyBatis,Spring整合简易教程 -
cnm493:
w6889037 写道大神,问一下,如果不是测试,是实际开发中 ...
MyBatis,Spring整合简易教程 -
w6889037:
大神,问一下,如果不是测试,是实际开发中需要分层,那么impl ...
MyBatis,Spring整合简易教程
几个人围成一圈||猴子选大王(约瑟夫环)
- 博客分类:
- 算法代码收藏
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3。最后剩下1号。
一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
数组方式
链表方式
为了方面在链表中删除节点,前面的方法查找的节点实际上找的是待删除的节点的前面一个节点,然后删除的时候就通过这个节点指针将后面一个节点删除,这样的做法很简单,但是感觉很奇怪。昨天看了一下《编程之美》,被里面的一种方法吸引了,果断重写,现在咱这个链表中的节点就是直接找到所在的节点,并且直接把这个节点“删”了^_^,不多说,show code~
一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
数组方式
#include<stdio.h> #define N 5 //总人数 #define M 3 //报数最大值(1-M) #define R 1 //留下的人数 void main() { //声明一个数组代表N个人 int r[N]; //游戏开始之前所有的人都还在,所以当前人数为N int size = N; int remain = R; //设定报数起始值 int count = 1; int i,j; //给每个人加上编号 for(i=0; i<N; i++) r[i] = i+1; printf("%d个人从1报数,报到%d的出列,求最后剩余的%d个人\n", N, M, R); //循环到当前人数为指定的数目的剩余人数时终止 while(size != remain) { //对当前剩余人数进行循环报数 for(i=0; i<size; i++) { //报数到3,去掉当前这个人,将后面的人全部往前挪一个位置,当前人数减1,并保持这个for循环停留一次(因为后面一个人挪过来了,所以应该再次在这个位置上重新报数) if(count == M) { printf("第%d个人报数%d,%d号选手出列\n", r[i], count, r[i]); for(j=i; j<size-1; j++) { r[j] = r[j+1]; } i--; size--; count = 1; } else { printf("第%d个人报数%d\n", r[i], count); //继续报数 count++; } } } printf("############剩余的%d个选手############\n", remain); for(i=0; i<remain; i++) { printf("第%d个人报数%d\n", r[i], count, r[i]); } }
链表方式
#include<stdio.h> #define M 10 #define N 3 #define LEN sizeof(struct Node) struct Node { int data; struct Node *next; }; //创建一个循环链表 struct Node *create() { int i; struct Node *head,*p1,*p2; //创建一个头节点 head = p1 = p2 = (struct Node *)malloc(LEN); //头节点赋值 head->data = 1; //使用p1,p2的叉开移动继续创建后面的节点 //(1)p2指向新节点 (2)p1的next指向p2 (3)p1和p2都指向新节点位置,repeat for(i=1; i<M; i++) { p2 = (struct Node *)malloc(LEN); p2->data = i+1; p1->next = p2; p1 = p2; } //将最后一个节点的next指向head p1->next = head; //返回头指针 return head; } //找到待删除的元素的前一个元素的位置(方便后续的删除和重连接操作) struct Node *find(struct Node *start,int n) { struct Node *find = start; int i; for(i=0; i<n-2; i++) { find = find->next; } return find; } //删除find所指的后面的节点,并将find和find的后后面的节点连接起来 struct Node *del(struct Node *find) { //后后面的节点 struct Node *temp = find->next->next; printf("删除了%d\n", find->next->data); free(find->next); find->next = temp; return temp; } void main() { //每一次开始报数的位置 struct Node *startNode = create(); //每一次报到N要被删除的数的位置 struct Node *findNode; int i; //进行M-1次报数后就只剩下随后一个人 for(i=0; i<M-1; i++) { //找一个报数为N的所在的位置 findNode = find(startNode, N); //删掉它并返回下一个继续点的位置 startNode = del(findNode); } //输出最后一个人的信息 printf("#####剩下%d\n", startNode->data); }
为了方面在链表中删除节点,前面的方法查找的节点实际上找的是待删除的节点的前面一个节点,然后删除的时候就通过这个节点指针将后面一个节点删除,这样的做法很简单,但是感觉很奇怪。昨天看了一下《编程之美》,被里面的一种方法吸引了,果断重写,现在咱这个链表中的节点就是直接找到所在的节点,并且直接把这个节点“删”了^_^,不多说,show code~
#include<stdio.h> #define N 10 #define M 3 struct Node { int data; struct Node *next; }; //创建循环链表(1-10) struct Node *create() { int i; struct Node *head,*p1,*p2; head = p1 = p2 = (struct Node*)malloc(sizeof(struct Node)); head->data = 1; for(i=1; i<N; i++) { p1 = (struct Node*)malloc(sizeof(struct Node)); p1->data = i+1; p2->next = p1; p2 = p1; } p2->next = head; return head; } //寻找报数为num的数字(报数范围1-num),返回指向它的指针 struct Node *find(struct Node *start, int num) { struct Node *p = start; int i; for(i=1; i<num; i++) { p = p->next; } return p; } //删除p所指向的节点(实际删除的是p后面一个节点) //基本思想:将p后面一个节点的数据复制到p上,然后让p指向p后后面的节点,然后删掉p后面的节点 //返回的是保存了p后面节点数据的节点 struct Node *del(struct Node *p) { struct Node *pt = p->next; p->data = pt->data; p->next = pt->next; free(pt); return p; } void main() { int i; struct Node *start = create(); for(i=0; i<N-1; i++) { start = find(start, M); printf("删除%d\n", start->data); start = del(start); } printf("最后剩下%d\n", start->data); }
发表评论
-
编辑距离(递归)
2014-03-23 21:54 911#include<stdio.h> int ... -
零幺串
2014-03-17 21:07 811我们称用1和0组成的串为“零幺串”,称只用1组成的串为“幺串 ... -
从两个文件读入字母,合并排序后输出到另一个文件
2014-03-17 16:20 853没啥多说的。。。 #include<stdio.h& ... -
删除第一个链表中与第二个链表重复的节点
2014-03-14 21:32 2655有两个链表a和b,设结点中包含学号、姓名。从a链表中删去与b链 ... -
链表逆序(链表倒置)
2014-03-14 21:25 863将一个链表按逆序排列,即将链头当链尾,链尾当链头 #in ... -
合并两个有序链表
2014-03-14 16:00 914两个已经按照从小到大的排序的链表,合并成一个链表,仍然保持从小 ... -
链表按序插入节点
2014-03-14 11:07 859在一个有序的链表上插入一个节点,使得插入节点后的链表仍然有序 ... -
两个乓乓球队比赛问题
2014-03-08 11:26 1051题目:两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙 ... -
十进制十六进制互转、数字转字符、日期转总天数
2014-03-07 21:35 1766#include<stdio.h> /* ... -
二分查找
2014-03-05 13:00 761#include<stdio.h> /* ... -
两个矩阵相乘
2014-03-04 21:54 782#include<stdio.h> #def ... -
寻找鞍点(行最大,列最小)
2014-03-04 11:00 1267#include<stdio.h> void ... -
strcmp函数的实现
2014-02-26 11:39 923如果两个字符串相等,返回0,如果不相等,返回它们不想等的字符的 ... -
指向指针的方法对n个字符串排序
2014-02-26 11:12 1800说实话前面的对整数的指向指针的排序真没看出有什么意思,但是这个 ... -
指向指针的方法对n个整数排序
2014-02-26 10:54 4404#include"stdio.h" ... -
猴子吃桃问题
2014-02-24 12:27 820猴子第一天摘了若干个桃子,当即吃了一半,还不解馋,又多吃了一个 ... -
编辑距离
2014-01-11 19:44 725直接递归形式的编辑距 ... -
非递归汉诺塔(使用栈)
2013-12-23 12:10 4874/** * 栈方式非递归汉诺塔 * @author ... -
Java去除源代码注释
2013-12-22 18:35 8140总体思路是对待分析的带注释段的字符串进行遍历,声明一个缓冲字符 ... -
递归方程求解
2013-12-13 17:15 662...
相关推荐
有M只猴子,依次按1到M的顺序坐好,然后从第一只猴子开始报数,数到N(N)的那只猴子就出局,从下一只猴子开始重新开始数....依次...直到只剩下最后一只猴子,则那只猴子就是大王。 要求:只输入M N值,就可以得到...
C语言,数据结构作业 约瑟夫环 猴子选大王
C++猴子选大王问题(可以从任意位置开始),得到猴子的大王所在位置
经典C题目猴子选大王,即约瑟夫环,是一个经典的问题,此为模拟法实现。
环形链表,猴子选大王,数到几出去,从几开始数,由用户输入决定
C语言课程设计之猴子选大王(约瑟夫问题)有详细流程,有源代码,希望对你有帮助
计算机 电子信息工程 通信工程 实验 课程设计 工程项目 资源 必过 已过 好用 答辩简单 按着来就行 大学生关注我 以后所有我的课设都会更新 所需积分很低 签一次到就能得不用去桃宝买 多支持 个人主页有更多课设实验...
任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1--m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求:(注:...
一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
约瑟夫问题是一个经典问题(猴子选大王) 有循环链表等多种解法,这里提供的是最简单的数学解法数学解法。
任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1--m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求: 输入...
python猴子选大王 #!/usr/bin/python # -*- coding: utf-8 -*- N=int(input()) ls=[i for i in range(1,N+1)] step=2 #步长 ptr=1 while len(ls) > 1: #ptr表示列表中第几个元素,没有第0个元素,只有下标为0的...
利用数组实现猴子选大王问题 输入猴子的个数以及报的数得出大王的编号
这是实现对猴子进行选大王,是一个很好玩的猴子选王游戏,
利用猴子选大王随约瑟夫问题进行探究,用多种方式进行完成 迅速 简洁
任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求:输入...
猴子选大王问题,用链表解决,最后用c语言编程实现,本体是数据结果中的重要实验之一。很有用
n只猴子围成一圈,从1到n顺序编号。从第q只猴子开始,从1到m报数,凡报到m的猴子退出竞选,下一次又从退出的那只猴子的下一只开始从1到m报数,直至剩下的最后一只为大王。请问最后哪只猴子被选为大王。 【输入形式】...
猴子选大王(C++)带报告,这是一个很好的程序,绝对能运行!请需要的人下载!