汉扬编程 C语言入门 自杀逃生算法!C语言算法之约瑟夫环问题

自杀逃生算法!C语言算法之约瑟夫环问题

约瑟夫问题更多C/C++学习资料,请私信我“代码”,即可获取

自杀逃生算法!C语言算法之约瑟夫环问题

据说着名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹 太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人到,于是决定了 一个自杀方式,41个人排成一个圆圈,由第1个人 开始报数,每报数到第3人该人就必须自杀, 然后再由下一个重新报数,直到所有人都自杀身亡为止。

自杀逃生算法!C语言算法之约瑟夫环问题

然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排 在第16个与第31个位置,于是逃过了这场死亡游戏。 解法约瑟夫问题可用代数分析来求解,将这个问题扩大好了,假设现在您与m个朋友不幸参

自杀逃生算法!C语言算法之约瑟夫环问题

与了这个游戏,您要如何保护您与您的朋友?只要画两个圆圈就可以让自己与朋友免于死亡游 戏,这两个圆圈内圈是排列顺序,而外圈是自杀顺序,如下图所示:

自杀逃生算法!C语言算法之约瑟夫环问题

更多C/C++学习资料,请私信我“代码”,即可获取

自杀逃生算法!C语言算法之约瑟夫环问题

使用程式来求解的话,只要将阵列当作环状来处理就可以了,在阵列中由计数1开始,每找到三 个无资料区就填入一个计数,直而计数达41为止,然后将阵列由索引1开始列出,就可以得知每 个位置的自杀顺序,这就是约瑟夫排列,41个人而报数3的约琴夫排列如下所示: 14 14 14 36 36 361 1 1 38 38 38 15 15 15 2 2 2 24 24 2430 30 30 3 3 3 16 16 1634 34 34 4 4 4 25 25 25 17 17 175 5 5 40 40 40 31 31 31 6 6 6 18 18 1826 26 26 7 7 7 37 37 3719 19 19 8 8 8 35 35 35 27 27 279 9 9 20 20 20 32 32 32 10 10 1041 41 41 21 21 21 11 11 1128 28 28 39 39 39 12 12 12 22 22 2233 33 3313 13 1329 29 2923 23 23

自杀逃生算法!C语言算法之约瑟夫环问题

由上可知,最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的 人都死光了,所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

更多C/C++学习资料,请私信我“代码”,即可获取

代码实现准备过程

更多C/C++学习资料,请私信我“代码”,即可获取

环状处理

更多C/C++学习资料,请私信我“代码”,即可获取

结果分析

更多C/C++学习资料,请私信我“代码”,即可获取

更多精彩C语言多关卡推箱子实战视频教学

1000+代码用C语言结合win32写2048

「C语言程序设计」约瑟夫环问题

编号为 1,2,3,…,n 的 n 个人围坐一圈,任选一个正整数 m 作为报数上限值,从第一个人开始按顺时针方向报数,报数到 m 时停止,报数为 m 的人出列。

自杀逃生算法!C语言算法之约瑟夫环问题

从出列人的顺时针方向的下一个人开始又从 1 重新报数,如此下去,直到所有人都全部出列为止。

算法思想每个人的编号存放在一个数组 a 中,主函数中决定人数的个数以及报数的上限值 m,设计一个函数实现对应的操作。函数的形参有整型数组 a、整数 n 和 m,n 用来接收传递的人数,m 用来接收报数上限,函数的返回值为空;函数体中输出出列人的顺序。

函数中利用循环访问数组中 n 个元素,每次访问元素,设定内循环连续访问 m 个元素,元素访问的下标为 k,访问到第 m 个元素时,如果元素不是 0,此时输出元素 a[k],再设定 a[k] 为 0,继续访问后面的元素。

主函数中设定数组 a,从键盘输入 n 和 m,利用循环产生 n 的位置序号存放到数组 a 中,调用函数实现相应的操作。

程序代码:#include <stdio.h>#define N 100int josef(int a[],int n,int m){    int i,j,k=0;    for(i=0;i<n;i++)    {        j=1;        while(j<m)        {            while(a[k]==0)            k=(k+1)%n;            j++;            k=(k+1)%n;        }        while(a[k]==0)        k=(k+1)%n;        printf("%d ",a[k]);        a[k]=0;    }    return 0;}int main(){    int a[100];    int i,j,m,n;    printf("input n and m:");    scanf("%d%d",&n,&m);    for(i=0;i<n;i++)        a[i]=i+1;    printf("\\n output:\\n");    josef(a,n,m);    printf("\\n");    return 0;}

调试运行结果:15 个人围坐在一起,报数上限为 4 时的出列顺序如下所示:

input n and m:15 4

output:

4 8 12 1 6 11 2 9 15 10 5 3 7 14 13

——————————

100 个人围坐在一 起,报数上限为 9 时的出列顺序如下所示:

input n and m:100 9

output:

9 18 27 36 45 54 63 72 81 90 99 8 19 29 39 49 59 69 79 89 100 11 22 33 44 56 67

78 91 2 14 26 40 52 65 77 92 4 17 32 47 61 75 88 5 21 37 53 70 85 1 20 38 57 74

94 12 31 51 73 95 15 41 62 84 7 34 60 86 13 43 71 98 30 66 97 35 76 10 50 93 42

83 28 87 48 6 68 46 23 3 96 16 25 64 55 58 24 80 82

总结: ① 程序由 main() 函数和 josef() 函数组成,main() 函数调用 josef() 函数,用数组名作为函数参数,在主函数和被调用函数中分别定义数组。

主函数执行到 josef(a,n,m) 语句时,将数组 a 的首元素的地址传递给形参数组 a,程序转去执行 josef(),形参数组 a 中的元素发生逆序排列,则实参数组 a 也随之改变,当 josef() 执行完后,返回到主函数中继续执行被调函数后面的语句。

② 实例中定义函数 josef() 解决问题的难点有两个:一是如何求下一个出圈的人的位置;二是此人出圈后对这个人的位置如何处理。

从第一个人开始报数,报到 m 时,此人出圈,设定变量 j,每次统计出圈的人数,当出圈人数到 m 时,重新开始统计。n 个人围坐一圈,可看作环状,设定 k 表示出圈人的下标,则出圈人的下标的计算可用“(k+l)%n”表示。

对于第二个问题,首先将出圈人的位置打印输出,然后将其位置元素设置为 0。

③ 数组名作函数参数时,要求在被调用函数和调用函数中分别定义数组,且形参和实参必须是类型相同的数组。

实参和形参数组是指向同一段地址空间的,当主函数执行时,这段空间由实参数组控制,当被调用函数执行时,这段空间由形参数组使用,被调函数执行结束后,该空间又交回给实参数组。

用数组名作为函数参数时,形参与实参之间的传递方式为地址传递,因此,形参数组的改变会影响实参数组的内容。

④ 一维数组名、多维数组名都可以作为函数的参数,进行地址传递。

不管你是转行也好,初学也罢,进阶也可,如果你想学编程,进阶程序员~

【值得关注】我!

全栈程序员正在等你加入~

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6076.html

C/C++编程笔记:什么时候在C++中使用初始化列表?

C++编程实战入门:斐波那契(Faibonacci)数列

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部