问题:
据说着名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,
39个犹太人决定宁愿死也不要被敌人找到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到
第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,Josephus
要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
解法:
约瑟夫问题可用代数分析来求解,将这个问题扩大好了,假设现在您与m个朋友不幸参与了这个游戏,您要如何保护您与您的
朋友?其实只要将阵列当作环状来处理就可以了,在阵列中由计数1开始,每找到第三个就填入一个计数,直到计数达41为止,
然后将阵列由索引1开始列出,就可以得知每个位置的自杀顺序,这就是约瑟夫排列,41个人而报数3的约琴夫排列如下所示:
14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 316 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 1222
33 13 29 23
由上可知,最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的
人都死光了,所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。
#include <stdio.h>
#include <stdlib.h>
#define N 41
#define M 3
int main(void)
{
int man[N] = {0};
int count = 1;
int i = 0, pos = -1;
int alive = 0;
while(count <= N)
{
do
{
pos = (pos+1) % N; //环状处理
if(man[pos] == 0)
i++;
if(i == M)
{ // 报数为3了
i = 0;
break;
}
} while(1);
man[pos] = count;
count++;
}
printf("\n约瑟夫排列");
for(i = 0; i < N; i++)
printf("%d ", man[i]);
printf("\n\n您想要救多少人");
scanf("%d", &alive);
printf("\nL表示这%d人要放的位置:\n", alive);
for(i = 0; i < N; i++)
{
if(man[i] < 41-alive+1)
printf("D");
else
printf("L");
}
printf("\n");
return 0;
}
//测试结果:
分享到:
相关推荐
数据结构 链表 约瑟夫问题 KMP 模式匹配 二叉排序树 llink-rlink 关键路径 堆排序
数据结构课程设计--排序和约瑟夫环
#约瑟夫问题,c#排序算法,C#非递归回溯法.pdf
用C语言对约瑟夫问题进行编程,从而解决最终的排序问题
第一个程序:实现将两个二叉排序树合并为一个二叉排序树的算法; 第二个程序:N个人围成一圈,从第一个人开始计数,凡是数到1,2,4,8,也就是2的N次方的退出圈子。编写程序,把这些人退出的顺序输出,要求用链表。
已知n个人围坐在圆桌周围,从编号为k的人开始报数,数到m的人出列,他的下一个人从一开始报数,数到m的人出列,依次重复,直到所有人都出列,求出列顺序
1、 线性结构基本算法实现(指导老师根据题目指定); 2、 树型结构基本算法实现(指导老师根据题目指定); 3、 图型结构基本算法实现(指导老师根据题目指定); 4、 查找基本算法实现 5、 排序基本算法实现
选择用单循环链表来解决约瑟夫问题。首先,根据输入的人数n,将这n个人依次按照0.1.2……n的编号顺序构造成一个单循环链表,并且头指针中也存放信息。再根据输入的数据 m,每数到第m个人的时候就将该节点所存储的编号...
主要介绍了php约瑟夫问题解决关于处死犯人的算法,实例分析了php关于约瑟夫问题的实现与应用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
约瑟夫问题.cpp 1-2.验证表.cpp 1-3.循环小数.cpp 2-1.双向约瑟夫问题.cpp 2-2.综教楼后的那个坑.cpp 2-3.孤独的运货员.cpp 2-4.一元多项式相加.cpp 2-5.一元多项式相乘.cpp 3-1.括号匹配.cpp 3-2.出栈序列.cpp 3-3....
(2)建立数据文件,数据文件按关键字(姓名、学号或房号)进行排序(冒泡、选择、插入排序等任一种)。查询菜单为:(用折半查找实现以下操作)(1)按姓名查询;(2)按学号查询;(3)按房号查询。2. 约瑟夫环...
约瑟夫环 leetcode leetcode 每日一题 8 字符串转换整数 (atoi) 42 接雨水 289 生命游戏(未操作表示状态) 820 字典树 892 数组 正方体表面积 912 数组排序 914 数字分组 999 二维数组 1111 有效货号字符串 1162 地图...
排序 直插 Straight Insertion Sort 希尔 Shell's Sort 简单选择 Simple Selection Sort 冒泡 Bubble Sort 鸡尾酒 Cocktail Sort 堆 Heap Sort 归并 Merge Sort 快速 Quick Sort 桶 Bucket Sort 查找 顺序 ...
约瑟夫环 leetcode leetCode 刷题经验 难题 序列号 题目名称 关键解法 4 Median of Two Sorted Arrays 要求O(logN) 5 实现 strStr() kmp算法 30 串联所有单词的子串 不懂 36 有效的数独 不懂 37 解数独 不懂 109 ...
利用动态循环单链表解决排序问题,简洁明了
C++语言解决排序系统问题实现单循环链表的各项功能,从而解决约瑟夫问题。各模块的调用关系:主程序调用各功能模块。
约瑟夫环 leetcode leetcode_github 为快速刷leetcode,将此项目分为两部分: 给的多种tag,按照题解降序,选择性刷5-10题。 75题 1 官网tag分类 tag分类_栈&队列 225 20 42 232 946 面试题09 面试题30 面试题59 - I...
约瑟夫问题(Josephus Problem) 集合问题 排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 ...
约瑟夫问题(Josephus Problem) 集合问题 排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 ...
约瑟夫问题(Josephus Problem) 集合问题 排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - ...