首页 > 代码库 > 基础算法1——约瑟夫问题
基础算法1——约瑟夫问题
问题来历
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
分析1：
（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
C++代码：
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 bool a[101]={0}; 6 intn,m,i,f=0,t=0,s=0; 7 cin>>n>>m; 8 do 9 {10 ++t;//逐个枚举圈中的所有位置11 if(t>n)12 t=1;//数组模拟环状，最后一个与第一个相连13 if(!a[t])14 s++;//第t个位置上有人则报数15 if(s==m)//当前报的数是m16 {17 s=0;//计数器清零18 cout<<t<<‘‘;//输出被杀人编号19 a[t]=1;//此处人已死，设置为空20 f++;//死亡人数+121 }22 }while(f!=n);//直到所有人都被杀死为止23 return 0;24 }
C代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct node 5 { 6 int data; 7 struct node *next; 8 }Node; 9 10 Node *creat(int n)11 {12 Node *p, *head;13 head = (Node *)malloc(sizeof(Node));14 p = head;15 Node *s;16 int i = 0;17 18 if(0 != n)19 {20 while(i <= n)21 {22 s = (Node *)malloc(sizeof(Node));23 s->data = http://www.mamicode.com/i++;24 p->next = s;25 p = s; 26 }27 s->next = head->next; 28 }29 free(head);30 return s->next;31 }32 33 int main()34 {35 int n = 41, m = 3;36 int i;37 Node *p = creat(n);38 Node *temp;39 40 m %= n;41 42 while(p != p->next)43 {44 for(i = 1; i < m-1; i++)45 {46 p = p->next;47 }48 printf("%d ", p->next->data);49 temp = p->next;50 p->next = temp->next;51 52 free(temp);53 p = p->next;54 }55 printf("%d\n", p->data);56 57 return 0;58 }
基础算法1——约瑟夫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。