有趣的约瑟夫问题及解决办法

2015.03.31 | C/C++ | AilsonJack | 暂无评论 | 987 views

By: Ailson Jack
Date: 2014-05-24
个人博客: http://www.only2fire.com/

今天给大家讲讲约瑟夫问题是什么，并且我提供了一种约瑟夫问题的解决办法。对于不知道约瑟夫是谁的人来说，就更不用提什么是约瑟夫问题了。那么问题来了，约瑟夫是谁，约瑟夫问题又是个什么东西。首先来个解释吧，约瑟夫问题，有时也称为约瑟夫置换，是一个出现在计算机科学和数学中的问题。特别是对于学习过数据结构的人来说，在书上看到解决这个问题的题目，可能都不下5遍吧。在计算机编程的算法中，类似的问题又称为约瑟夫环或者丢手绢问题。约瑟夫(Josephus)是谁，约瑟夫是著名的犹太历史学家，那么约瑟夫问题又是个什么东西呢。其实我并不太清楚约瑟夫的什么生平经历，但是关于约瑟夫问题，倒是有一个小故事给大家讲一讲，这个故事就是约瑟夫问题的原型。好了，下面来个大家讲故事了<img src="/UEditor/dialogs/emotion/images/face/i_f29.gif"/>，据说在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。从上面的故事，大家至少可以知道，约瑟夫虽然是个历史学家，但是他的数学学的也不赖嘛<img src="/UEditor/dialogs/emotion/images/face/i_f07.gif"/>。约瑟夫问题并不难，求解的方法也非常的多，我这里提供一个循环链表的解决方法，为什么用循环链表，因为我看那个故事里面的人都是手拉手围成一个圆圈的嘛<img src="/UEditor/dialogs/emotion/images/face/i_f03.gif"/>。  这里是我用CodeBlocks编写的程序，什么是CodeBlocks，以及如何使用，大家可以参考我的博文：<a href="http://www.only2fire.com/archives/12.html" target="_blank">CodeBlocks 安装配置使用一条龙超详细</a>。CodeBlocks其实还是挺好用的。我的源代码下载地址：<a class="btn btn-success" href="https://pan.baidu.com/s/1jGj8YDg" target="_blank">点此下载</a>  密码：glf4。下面是我写的程序源代码，大家看看，就知道是怎么解决的了：注：可以通过修改main()函数中的Start，Count，length这3个参数来改变游戏的规则，大家可以试试。<pre class="brush:cpp;toolbar:false PrismJs">#include <stdio.h> #include <stdlib.h> /* *功能:约瑟夫问题解决办法(循环链表解决) *By:Ailson Jack *Date:2014.05.24 */ #define error    0 #define ok        1 typedef int ElementType; typedef struct CycleListNode Node; typedef struct CycleListNode *ptrNode; struct CycleListNode//循环链表结点 {     ElementType data;//数据区     ptrNode next;//指向下一个结点 }; //函数声明 //约瑟夫问题解决办法(循环链表解决) void Josephus(ptrNode list,int start,int count,int length); //创建循环链表头结点 int CycleList_CreateNode(ptrNode *list); //初始化循环链表,并且最后丢掉链表头结点,链表的数据为1 -> length void CycleList_Init(ptrNode *list,int length); //删掉循环链表中从表头数的第position个位置的数据 //最终将头结点变为删除前那个结点的下一个结点 void CycleList_Delete(ptrNode *list,int position); //查找循环链表中数据元素是Start的结点的位置,并且将该节点设为新的起始结点s void CycleList_Find(ptrNode *list,ElementType Start); //打印循环链表中的数据 void Prin_CycleList(ptrNode list,int length); int main(void) {     int Start=1;//起始计数位置     int Count=3;//第Count个位置的结点出局     int length=41;//循环链表的长度     ptrNode list;     CycleList_CreateNode(&list);     CycleList_Init(&list,length);     Prin_CycleList(list,length);     Josephus(list,Start,Count,length);     while (1)     {     }     return 0; } //约瑟夫问题解决办法(循环链表解决) void Josephus(ptrNode list,int start,int count,int length) {     int i=1;     CycleList_Find(&list,start);     printf("\r\n约瑟夫问题解决开始....\r\n");     while (i<=length)     {         CycleList_Delete(&list,count);         i++;     }     printf("\r\n约瑟夫问题解决结束\r\n"); } //创建循环链表头结点 int CycleList_CreateNode(ptrNode *list) {     *list=(ptrNode)malloc(sizeof(struct CycleListNode));     if(*list==NULL)     {         printf("Out of Space...\r\n");         return error;     }     (*list)->next=NULL;     return ok; } //初始化循环链表,并且最后丢掉链表头结点,链表的数据为1 -> length void CycleList_Init(ptrNode *list,int length) {     int i=1;     ptrNode newNode;     ptrNode FirstNode;     FirstNode=*list;     while(i<=length)//i从1到 length     {         newNode=(ptrNode)malloc(sizeof(struct CycleListNode));         newNode->data=i;         (*list)->next=newNode;         (*list)=newNode;         i++;     }     (*list)->next=FirstNode->next;     *list=FirstNode->next; } //删掉循环链表中从表头数的第position个位置的数据 //最终将头结点变为删除前那个结点的下一个结点 void CycleList_Delete(ptrNode *list,int position) {     int i=1;     ptrNode tmp;     if (position==1)     {         tmp=*list;         while (tmp->data!=(*list)->next->data)         {             *list=(*list)->next;         }         printf("%d ",(*list)->next->data);         (*list)->next=tmp->next;         *list=tmp->next;         free(tmp);         tmp=NULL;     }     else     {         while (i<position-1)         {             (*list)=(*list)->next;             i++;         }         tmp=(*list)->next;         printf("%d ",tmp->data);         (*list)->next=(*list)->next->next;         free(tmp);         tmp=NULL;         *list=(*list)->next;     } } //查找循环链表中数据元素是Start的结点的位置,并且将该节点设为新的起始结点 void CycleList_Find(ptrNode *list,ElementType Start) {     while ((*list)->data!=Start)     {         *list=(*list)->next;     } } //打印循环链表中的数据 void Prin_CycleList(ptrNode list,int length) {     int i=1;     printf("打印循环链表...\r\n");     while (i<=length)     {         printf("%d ",list->data);         list=list->next;         i++;     }     printf("\r\n结束打印\r\n"); }</pre>下面是程序的运行结果：<img src="/uploads/AilsonJack/2018.08.17/1534498116478304.png" onclick="preview_image('/uploads/AilsonJack/2018.08.17/1534498116478304.png')"/>以上就是对约瑟夫问题的解决方法啦，大家有不明白的可以留言哟。

欢迎关注博主的公众号呀，精彩内容随时掌握：

热情邀请仔细浏览下博客中的广告,万一有对自己有用或感兴趣的呢｡◕ᴗ◕｡。
如果这篇文章对你有帮助，记得点赞和关注博主就行了^_^，当然了能够赞赏博主，那就非常感谢啦！
注：转载请注明出处，谢谢！^_^

编程语言 C C++ 数据结构算法

转载请注明来源: 本文链接: By: AilsonJack
有趣的约瑟夫问题及解决办法 | 说好一起走

你可能也喜欢：