- 浏览: 157520 次
- 性别:
- 来自: 昆明
文章分类
最新评论
-
北月与南安:
感谢楼主,通过这个,我学会了 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 948#include<stdio.h> int ... -
零幺串
2014-03-17 21:07 856我们称用1和0组成的串为“零幺串”,称只用1组成的串为“幺串 ... -
从两个文件读入字母,合并排序后输出到另一个文件
2014-03-17 16:20 881没啥多说的。。。 #include<stdio.h& ... -
删除第一个链表中与第二个链表重复的节点
2014-03-14 21:32 2704有两个链表a和b,设结点中包含学号、姓名。从a链表中删去与b链 ... -
链表逆序(链表倒置)
2014-03-14 21:25 897将一个链表按逆序排列,即将链头当链尾,链尾当链头 #in ... -
合并两个有序链表
2014-03-14 16:00 954两个已经按照从小到大的排序的链表,合并成一个链表,仍然保持从小 ... -
链表按序插入节点
2014-03-14 11:07 891在一个有序的链表上插入一个节点,使得插入节点后的链表仍然有序 ... -
两个乓乓球队比赛问题
2014-03-08 11:26 1088题目:两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙 ... -
十进制十六进制互转、数字转字符、日期转总天数
2014-03-07 21:35 1813#include<stdio.h> /* ... -
二分查找
2014-03-05 13:00 805#include<stdio.h> /* ... -
两个矩阵相乘
2014-03-04 21:54 810#include<stdio.h> #def ... -
寻找鞍点(行最大,列最小)
2014-03-04 11:00 1295#include<stdio.h> void ... -
strcmp函数的实现
2014-02-26 11:39 975如果两个字符串相等,返回0,如果不相等,返回它们不想等的字符的 ... -
指向指针的方法对n个字符串排序
2014-02-26 11:12 1839说实话前面的对整数的指向指针的排序真没看出有什么意思,但是这个 ... -
指向指针的方法对n个整数排序
2014-02-26 10:54 4444#include"stdio.h" ... -
猴子吃桃问题
2014-02-24 12:27 857猴子第一天摘了若干个桃子,当即吃了一半,还不解馋,又多吃了一个 ... -
编辑距离
2014-01-11 19:44 756直接递归形式的编辑距 ... -
非递归汉诺塔(使用栈)
2013-12-23 12:10 4902/** * 栈方式非递归汉诺塔 * @author ... -
Java去除源代码注释
2013-12-22 18:35 8199总体思路是对待分析的带注释段的字符串进行遍历,声明一个缓冲字符 ... -
递归方程求解
2013-12-13 17:15 699...
相关推荐
这个问题描述如下:一群编号从1到m的猴子围成一圈,从第1号开始数数,每数到第n号的猴子就离开圈子,然后从下一只继续数,直到圈中只剩下一个猴子,这个猴子即为大王。本篇将探讨如何使用C++语言,通过数组和链表两...
“猴子选大王”问题在计算机科学领域通常被称为约瑟夫环问题。该问题源自古罗马历史学家约瑟夫斯的一个故事,讲述了一群人围成一圈,按照特定规则决定谁将被处决或存活下来。在编程领域中,这个问题被广泛用来考察...
问题的基本设定是:一群猴子围成一个圈,从某一只猴子开始按顺时针方向编号,然后从第一只开始数数,数到特定数值的猴子出圈,然后继续从下一只猴子开始数,如此循环,直到只剩最后一只猴子,这只猴子就被选为大王。...
在这个问题中,假设一群猴子围成一个圈,每次从圈中按顺序剔除一只猴子,直至只剩下最后一只,这只猴子即为大王。问题的关键在于如何高效地模拟这个过程。 首先,我们要理解数据结构的选择。由于猴子们围成一个圈,...
有M只猴子,依次按1到M的顺序坐好,然后从第一只猴子开始报数,数到N(N)的那只猴子就出局,从下一只猴子开始重新开始数....依次...直到只剩下最后一只猴子,则那只猴子就是大王。 要求:只输入M N值,就可以得到...
约瑟夫环问题描述如下:假设有一群人围成一个圈,从某个人开始按顺时针或逆时针顺序报数,每次数到特定数值的人会被排除出圈,然后从下一个人继续报数,直到只剩下最后一个人为止,这个人被称为“大王”。...
环形链表,猴子选大王,数到几出去,从几开始数,由用户输入决定
在这个问题中,一群猴子围成一个圈,每一轮从一只猴子开始按顺时针方向数数,数到特定数值的猴子会被淘汰,这个过程会持续到只剩下最后一只猴子,这只猴子就被选为“大王”。此问题在C++编程中可以运用基本的数据...
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个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
该算法模拟了m个猴子排成圈,数到n就出去,最后一个为猴王的过程。该算法的实现需要使用链表这种数据结构来存储猴子的信息。 链表是一种基本的数据结构,它是一种线性的数据结构,通过链式结构将数据元素连接起来。...
首先,猴子选大王的算法描述如下:假设有一群猴子,它们围成一圈,从某只猴子开始,按顺时针方向依次报数。每当报到特定数字(在这个例子中是3)的猴子就会被排除出去,然后从下一只猴子继续报数,直到只剩下一只...
本文将深入探讨一个基于Java数据结构链表实现的经典问题——“猴子选大王”,也称作约瑟夫环问题。该问题源于一个古老的传说,一群猴子围成一个圈,从某一只开始按顺时针方向依次报数,数到特定数值的猴子会被淘汰,...
根据给定的信息,我们可以分析并总结出以下与“C++ 编写的猴子选大王的程序”相关的知识点: ### C++ 程序设计基础 #### 1. 基本语法结构 - **预处理指令**:如 `#include`、`#define` 等,用于引入头文件或定义...
里面包含了我的博客‘’算法 -- 猴子选大王的四种方法,并对其时间与内存消耗的分析和对比&PHP;‘’里的全部内容。
任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1--m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求: 输入...
任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求:输入...