经典算法-----约瑟夫问题（C语言）

 目录

前言

故事背景

约瑟夫问题

环形链表解决

 数组解决

---

前言

        今天我们来玩一个有意思的题目，也就是约瑟夫问题，这个问题出自于欧洲中世纪的一个故事，下面我们就去通过编程的方式来解决这个有趣的问题，一起来看看吧！

故事背景

        据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

        17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

约瑟夫问题

从键盘获取两个数据，n和s，n是表示人数，s是表示从第一个人开始数，数到第s个的时候那个人就出局，问：最后剩下的最后一个人是第几个？

环形链表解决

        这里我们可以去通过环形链表的形式来解决这个问题 ，过程图如下所示：

先根据当前输入的人数去创建一个相对应的环形链表，依次把每个人的位置存入进去

 然后就去从第一个人开始数，当数到第三个人的时候就进行删除操作，如下所示，后面就从第四个节点开始新的一轮……

代码如下所示： 

#include <stdio.h>
#include<stdlib.h>
//节点
typedef struct node {int num;struct node* next;
}Node;//创建一个环形链表
Node* create_list(int n) {Node* head, * tail;head = tail = NULL;for (int i = 0; i < n; i++) {Node* p = (Node*)malloc(sizeof(Node));p->num = i + 1;    //依次标记当前位置if (head == NULL) {head = p;tail = p;head->next = NULL;}else{tail->next = p;tail = p;}tail->next = head;}return head;  //返回头结点
}int main() {int n, s;printf("请输入:");scanf("%d %d", &n, &s);Node* cur = create_list(n);int count = 1; //此时cur指向的是第一个节点，所以count为1while (n != 1) {	//当n=1时候，结束循环，此时剩下最后一个人count++;//先进行count统计if (count == s) {n--;	//进行删除节点操作Node* del_node = cur->next;	cur->next = del_node->next;free(del_node);//释放掉这个节点//此时count回归到1，也就是重新开始新的一轮count = 1;}cur = cur->next;}printf("最后剩下的是：%d\n", cur->num);
}

 数组解决

         不同与链表的是，数组不能去自定义人的数量，也就是说这里数组的数量是提前写好了的，还有就是数组的执行效率更加高，环形链表要去通过遍历执行，时间复杂度为O(n),而数组可以去直接找到这个位置时间复杂度为O(1)，不需要去一个一个遍历，代码如下：

//数组实现
#include<stdio.h>
void function(int* num, int length, int s, int start) {int count = 0;int i = start - 1;//标记起始位置int n = length;	//当前人数while (n != 1) {i = (i + s - 1) % n;	//下一个出局人的位置for (int j = i + 1; j < length; j++)num[j - 1] = num[j];	//进行删除操作，把要删除的数字后面的依次往前移动，覆盖掉这个要删除的数字n--;//删除操作完成，减少一个人if (i == n) {	//当i超出数组范围的时候，i就回归到第一个为止i = 0;}}printf("最后一个 :%d", num[i]);return;
}int main() {int num[6];//这里就已经定义好了6个人int s;	//每次数到s，出局一个printf("请输入:");scanf("%d", &s);for (int i = 0; i < sizeof(num) / sizeof(int); i++)num[i] = i+1;function(num, sizeof(num) / sizeof(int), s, 0);
}

以上就是今天的内容，我们下次见！

分享一张壁纸：