约瑟夫问题,大神们,这个怎么理解啊???

#include
#include

#define n 11
#define m 3

struct node{
int no;
node *next;
};

int main() {
int k = 0;
node p, *q, *r;
p = q = (node
)malloc(sizeof(node));//创建第一个节点
p ->no = 1;
for(int i = 2; i <= n; i++){ //建立链表
r = (node*)malloc(sizeof(node));
r ->no = i;
q ->next = r;
q = r;
}
q->next = p; //构成一个环
q = p;
while(q->next != q){
k++;
if(k == m){
p->next = q->next;
free(q);
q = p->next;
k = 0;
} else {
p = q;
q = q->next;
}
}
printf("最后一个获胜者的编号是:%d\n", q->no);
}

1个回答

#include
#include
#define n 11
#define m 3
typedef struct _node{
int no;
struct node *next;
}node;

void print(node* front)
{
node* tmp = front->next;
while(tmp != front)
{
printf("%d\t",tmp->no);
tmp = tmp->next;
}
puts("");
}

int main()
{

int k = 0,i=0;
node* p, *q, *r;
p = q = (node*)malloc(sizeof(node));//创建第一个节点
p->no = 1;
for(int i = 2; i <= n; i++)
{ //建立链表 
    r = (node*)malloc(sizeof(node));
    r ->no = i; 
    q ->next = r;
    q = r;
}
q->next = p; //构成一个环 
q = p; 
while(q->next != q)
{
    k++;
    if(k == m)
    {
        printf("%d:",i++);
        print(q);

        p->next = q->next;
        free(q);
        q = p->next;
        k = 0;          
    } 
    else 
    {
        p = q;
        q = q->next;
    }
} 
printf("最后一个获胜者的编号是:%d\n", q->no);  

}

直接运行,可看到整体流程

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
约瑟夫环问题递归解法的一点理解
约瑟夫环递归解法代码的一点理解。 约瑟夫生者死者游戏 约瑟夫游戏的大意:30个游客同乘一条船,因为严重超载, 加上风浪大作,危险万分。因此船长告诉乘客,只有将全船 一半的旅客投入海中,其余人才能幸免于难。无奈,大家只 得同意这种办法,并议定 30 个人围成一圈,由第一个人数起,依次报数,数到第9人,便把他投入
博客园里的大神们
做IT码农的这段时间里,我就像一个拾荒者,在网络上寻找着各种技术的踪迹。发现它们,揣测它们,理解它们,最终驾驭它们。在这期间,总会碰见这样几个人,你总能在各个地方看到他们的文章,他们的影子。 他们被菜鸟称之为大神,其实单论技术,他们或许并不是最强的,但是他们已经能够把技术描述的非常通俗易懂。像我之前做eclipse插件开发的时候,菜鸟期基本上是看着八进制的博客度过的,直到自己开始看eclipse
约瑟夫退圈问题
小学期作业,题目找不到了 N个人围成一圈,从第一个人开始按顺序报数并编号1,2,3,……N,然后开始从第一个人转圈报数,凡是报到3的退出圈子。则剩下的最后一个人编号是多少。 定义一个类,然后在类前定义一个结构体  2、在类中定义一个链表,输入人数确定链表的长度,对链表的信息进行初始化
约瑟夫问题与递归思想
今天看了一道算法问题:n个人(编号0~(n-1)),从0开始报数,报到m-1的退出,剩下的人继续从0开始报数,求胜利者的编号。 其实这是一个约瑟夫( Josephus problem)问题,原始的想法是采用数组或者链表结构模拟整个过程,总的时间复杂度为O(mn)。后来看到更好的解法,采用递归思想,它是这样描述的(引用:http://baike.baidu.com/view/213217.htm)
循环链表:约瑟夫问题(非常详细易理解)
约瑟夫问题来源 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始,越过
如何在大学里成为IT技术大神
总是有同学问我怎么学很多技术,好奇如何成为所谓的大神。 事实上,这篇文章是结合我的一些经历,讲述应该怎么学习技术,并不是要讲怎么成为大神。没有所谓的成功学,只有充满智慧的思考,脚踏实地的实干,和越来越近的理想,还有机遇和运气。之所以用这个标题,无非是吸引更多人、尤其是很多对成为大神抱有不切实际的幻想的人来看。希望读者能从中得到一些东西,没有浪费看这篇文的时间。这篇文章也只是我的看法,并不是什
约瑟夫环的问题---最后剩下哪一个
题意描述:0,1,……,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里面删除第m个数字。求这个圆圈中最后剩下的一个数字 解题思路一:模拟一个环,然后每次删除第m个数字 解题思路二:上述思路可行,但明显时间复杂度O(mn)。因此还是希望找找删除数字有什么规律。         递归公式:  0  ,                 n = 1
细数那些值得我们学习的大神们
学习编程是一个循序渐进的过程,没有人能够万丈高楼平地而起;可能你在学校或者培训机构里有老师教你写程序,但是这仅仅只是一个开始,师傅领进门,修行靠自身;你可以把学习编程的过程看作是一个习武的过程,如果你只有一点三脚猫的拳脚功夫,那出门你一定会“死”的很惨,所以在这个过程中你一定要通过研修一些武林秘籍(编程进阶书籍),与高手交流过招(阅读源码),这样你的功力才会慢慢积累,到最后变成武林高手。今天就和大家
约瑟夫环的数学推导、数学方法求最后出圈的数字、循环单链表求所有出圈数字顺序
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围;从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 前几天,在一篇文章中得知了约瑟夫环的问题。然后,就涉及了解决办法。这个问题,在许多计算机或者关于数据结构的书中都有提及,而其中的解决办法便是使用循环链表——无论这
这段代码看了让你怀疑人生 网友:不愧是大神写的
先说一下,我是干前端方向的,文章的这个游戏这个是javascript代码写的。 今天逛论坛看到了一位程序员大佬,真的是大佬,写了一个街头霸王游戏,我很早学JavaScript的时候自己也想过写游戏,但是那时候思维技术什么都不是很到位,所以一直没有去写,现在也没有那个闲情去写这个了,当然对于刚学好JavaScript的确是是一个锻炼思维和技术的最好案例,博主写了三天搞定的,这技术,我觉得已经很牛逼...
大神们的微博
邦:(iOS图片加载速度极限优化—FastImageCache解析)         http://blog.cnbang.net/tech/2578/?from=timeline&isappinstalled=1   李明杰老师(传智播客iOS学院院长):         http://weibo.com/exceptions#_rnd1426225075083  
约瑟夫环问题--递归解法的理解
转自:点击打开链接这里还有一篇思路简单清晰的文章:http://blog.csdn.net/wusuopubupt/article/details/18214999先来看这个类型的某个题目描述:约瑟夫生者死者游戏约瑟夫游戏的大意:30个游客同乘一条船,因为严重超载, 加上风浪大作,危险万分。因此船长告诉乘客,只有将全船 一半的旅客投入海中,其余人才能幸免于难。无奈,大家只 得同意这种办法,并议定3...
大神们 求解啊
银号卡以前绑定的那个手机号丢了     然后现在人在外地   不知道
大神如何阅读源码
以下是我搜集的各种方法,我将一一尝试,会根据尝试结果,做个总结,与大家一起分享: 1、腾讯IMWEB负责人说: 首先,搞清楚自己要读懂他们的原因和动机。 其次,可以先看下这些优秀框架或者库的设计文档和架构图,这样会让你宏观上对一些概念有些认识。  然后,从你最感兴趣的一个点,开始设置断点,跟进去看发生了哪些事情。 和架构设计哪一块是match的。 有人补充:最快,最易懂方法。
约瑟夫问题(Java实现)
一、简介约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.)例子: len个人围成一个圈,玩丢手绢游戏。从第k个人开始,从1开始数数,当数到m时,数m的人就退出圈子,当圈子只剩下一个人为止。问题分析与算法设计约瑟夫问题并不难,但求解的方法很多;题目的变化形式也很多。这里给出一种实现方法。 题目中l
西普实验吧CTF-约瑟夫环
题目描述: 总共有2 * k个人报数,前面k个是好人,后面k个是坏人,从第一个好人开始报数,报道m的人要死去。然后从死人的下一个活人继续从头开始报数,报道m的人死去,以此类推。当k = 12时,问m为何值时,坏人全部死去之前不会有好人死去。 这题之前做过,就是一个循环数组的遍历,之前打表了,代码: #include int main(){ int n; int a[15]={0,
基本约瑟夫环问题详解
基本问题描述: 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。通常,我们会要求输出最后一位出列的人的序号。那么这里主要研究的是最后一个出列的人的序号要怎么确定。 当
经典问题之约瑟夫问题的快速解决
此问题非常经典,在网上即可找到原题,在此不做描述。 对于原问题模型,一有链表法解决问题,效率极低,在此描述一种用树状数组完成问题的超快速做法。 首先,我们可以有这样递推的思路:不断加k模n,并减去其数字前走了的人即为当前人的真实编号(即是这一轮应踢走的人的编号),如何快速维护每个人其前走了的人的和,答案为树状数组。 现在模拟一下过程,假设有6个人,k=3(每报3个,走一个人)。 初
约瑟夫问题直接求取结果的思路
本人比较笨,约瑟夫问题的求解方法想了好久才想通,在这里留一篇文章,记录一下。 约瑟夫问题:n个人,数m,列出顺序。 1,用算法模拟数数过程,通过一个一个的排除,最后得到最终的结果: 首先解决思路问题,每次数数m个,一共数出 2.用递推的方法求解:
约瑟夫问题(c++)
今天花几小时完成了数据结构的实验题,里面实现了循环单链表的构建,节点的删除。            但说句实话,里面的执行函数我写的时候就有点别扭,觉得不太好,有点混乱,虽然最终还是实现出来了,供大家参考,也希望有朋友指点改进一下!            编译结果:                             源代码:            #include using n
牛的速记 题解
奶牛们误解了速记的含义。他们是这样理解的: 给出一个少于250个字母的小写字母串。 找到一个出现次数最多的字母,将该字母从字母串中统统删去,如果出现次数最多的字母不止一个,就删去在字母表中靠前的一个,即序号小的那个,已知a的序号为97,b的序号为98,c的序号为99,以此类推。 然后输出这个字符串。重复上面的操作,直到字符串中没有字符。当然,你不应该输出最后的空串。 虽然他们误解了,但是这却是一个
约瑟夫问题 C++ 解决
用C++解决约瑟夫问题啊,解决约瑟夫问题u,C++
约瑟夫环问题的Java版解法
详细推导了约瑟夫环问题的Java版实现方法,从包含两个参数拓展到四个参数。最后给出了常规链表法的Java实现代码,以供参考。
约瑟夫环的问题,python3实现
#encoding=utf-8def josephus(n,m):    &quot;&quot;&quot;        环的问题,        共有n个人围成一圈,从1开始报数,数到m时退出,再从1开始,直到所有人退出    &quot;&quot;&quot;    people = list(range(1,n+1))    index = 0    #给n个人编号放到表people中,从下标为0的人开始    for i in range(n...
这个怎么解析啊,求大神指点
"root": [ {          "title": "QQQQ",          "crl": "http://www.baidu.com/2007.html",          "time": "2014/12/10",           "img":            [          {"url":"http://uploads/allimg/1412/1-14121
这个怎么解决啊!!!求大神指导
&amp;lt;%@page import=&quot;java.sql.SQLException&quot;%&amp;gt;&amp;lt;%@page import=&quot;java.sql.ResultSet&quot;%&amp;gt;&amp;lt;%@page import=&quot;java.sql.Statement&quot;%&amp;gt;&amp;lt;%@page import=&quot;java.sql.Connection&quot;%&amp;gt;&amp;lt;
约瑟夫环的问题解决方法与分析
约瑟夫环的问题 相信大家都听过约瑟夫环的问题,据说著名犹太历史学家 Josephus有过以下的故事: 在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹 太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈, 由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到 所有人都自杀身亡为止。然而Jo
约瑟夫环问题的公式推导
题目:有n个人围成一个圈,将他们编号1~n从第k个人开始报数,每次报到m的人退出,问:最后留下的那个人编号为多少。
约瑟夫环 (队列实现)
#include "stdio.h" #include #define MAXQSIZE 100 #define TRUE 1 #define OK 1 #define FALSE 0 #define OVERFLOW 0 typedef struct{ int *elem; int front; //队头指针 int rear; //队尾指针 }SeQueue
约瑟夫环出圈问题三种求解方法
#coding=utf-8 # 递归直接求出 def fun_recursion(m,k): """ f[1]=0; f[i]=(f[i-1]+k)%i = (f[i-1] +m%i) % i = (f[i-1] + m) % i ; (i>1) :param m: 长度 :param k: 第k数出环 :return: """
简单约瑟夫环【队列实现】
问题描述: 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,
约瑟夫环问题 java代码实现(高效率)
问题来历编辑 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。一开始要站在什么
这样的数据格式如何打开???
1066、1069、1059都是有问题的,其他是正常的不知道怎么打开,兄弟姐妹们帮忙啊
约瑟夫环问题--递归推导
本文为学习《剑指offer》的记录。因其原理在原作者博客上找不到,所以,只能自己编写记录,如有不当之处,欢迎指正。题目描述: n个数,编号为 0 , 1, ……, n-1 排成一个圆圈,从数字 0 开始,每次从这个圆圈中删除第 m 个数,请问最后一个剩下的数是多少?推导过程 定义一个函数 f(n, m) 为 n 个数中取 m 最后剩下的编号。 第一个被删除的数是 (m-1)%n, 记为 k 。
10行Python代码解决约瑟夫环(模拟)
写这篇文章是因为看到别人博客里用了很长一个篇幅(超过50行)去解决一个约瑟夫环问题,而且还是用以简洁著称的python,另外,如果你用X度搜索python 约瑟夫,看到得前几条都是错的,真是好悲剧。 总的来说,就是误人子弟。 虽然,用模拟去解决这个约瑟夫环问题效率是很低的,但是,这更容易理解。 先上代码。 def josephus(n,k): link=range(1,n+1)
约瑟夫环的问题与应用(JAVA)
[编程题] 删数 有一个数组a[N]顺序存放0-N,要求没隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:{0,1,2,3,4,5,6,7},0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。 输入描述: 每组数据为一行一个整数n(小于等于1000),为数组成员
约瑟夫环问题详解
在牛客网上做到一道题,是约瑟夫环的变型,所以借此学习一下新知识,并且巩固一下对题目意思的理解,这一篇仅作约瑟夫环问题的解释,下一篇再写题目: 1.首先,我们先来了解一下什么是约瑟夫环问题: 讲一个比较有意思的故事:约瑟夫是犹太军队的一个将军,在反抗罗马的起义中,他所率领的军队被击溃,只剩下残余的部队40余人,他们都是宁死不屈的人,所以不愿投降做叛徒。一群人表决说要死,所以用一种策略来先后杀...
数据结构(二)java解决约瑟夫环的两种方法
使用组数解决约瑟夫环问题 使用队列解决约瑟夫环问题
约瑟夫环的问题编程C++实现
已知 n 个人(以编号1, 2, 3 ,4, 5 ,6  ... .. .n)围坐一张圆桌周围。从编号为k 的人开始报数,数到m 的那个人出列;他的下一个人又从 1开始报数,数到m的那个人又出列;依次规律重复下去,直到圆桌周围的人全部出列。请用C++编程。 整个程序分为3个步骤: 第一步:建立一个有n个元素的循环链表,链表是从1的编号开始的。 第二步:是从链表的表头数到第 k 个值。 第三
java 数组 解决 约瑟夫问题 算法
N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。
相关热词 c#panel增加滚动条 c#中生成的dll文件 c# 模板类 c# 截取txt文本内容 c# 内存 占用 c#时间格式化 不带- c#替换字符串中指定位置 c# rdlc 动态报表 c# 获取txt编码格式 c#事件主动调用