免费建站自助建站网站建设教程网站建设教程,百度公司招聘岗位,交互做的不好的网站,廊坊网站关键词排名目录
前言
故事背景
约瑟夫问题
环形链表解决 数组解决 前言 今天我们来玩一个有意思的题目#xff0c;也就是约瑟夫问题#xff0c;这个问题出自于欧洲中世纪的一个故事#xff0c;下面我们就去通过编程的方式来解决这个有趣的问题#xff0c;一起来看看吧#xff01… 目录
前言
故事背景
约瑟夫问题
环形链表解决 数组解决 前言 今天我们来玩一个有意思的题目也就是约瑟夫问题这个问题出自于欧洲中世纪的一个故事下面我们就去通过编程的方式来解决这个有趣的问题一起来看看吧 故事背景 据说著名犹太历史学家Josephus有过以下的故事在罗马人占领乔塔帕特后39 个犹太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到于是决定了一个自杀方式41个人排成一个圆圈由第1个人开始报数每报数到第3人该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始越过k-2个人因为第一个人已经被越过并杀掉第k个人。接着再越过k-1个人并杀掉第k个人。这个过程沿着圆圈一直进行直到最终只剩下一个人留下这个人就可以继续活着。问题是给定了和一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从他将朋友与自己安排在第16个与第31个位置于是逃过了这场死亡游戏。 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事15个教徒和15 个非教徒在深海上遇险必须将一半的人投入海中其余的人才能幸免于难于是想了一个办法30个人围成一圆圈从第一个人开始依次报数每数到第九个人就将他扔入大海如此循环进行直到仅余15个人为止。问怎样排法才能使每次投入大海的都是非教徒。 约瑟夫问题 从键盘获取两个数据n和sn是表示人数s是表示从第一个人开始数数到第s个的时候那个人就出局问最后剩下的最后一个人是第几个 环形链表解决 这里我们可以去通过环形链表的形式来解决这个问题 过程图如下所示 先根据当前输入的人数去创建一个相对应的环形链表依次把每个人的位置存入进去 然后就去从第一个人开始数当数到第三个人的时候就进行删除操作如下所示后面就从第四个节点开始新的一轮…… 代码如下所示
#include stdio.h
#includestdlib.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) { //当n1时候结束循环此时剩下最后一个人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)不需要去一个一个遍历代码如下 //数组实现
#includestdio.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] i1;function(num, sizeof(num) / sizeof(int), s, 0);
}
以上就是今天的内容我们下次见
分享一张壁纸
