【C语言程序设计】约瑟夫环问题！

Dear 丶 2022-10-22 12:53 115阅读 0赞

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

从出列人的顺时针方向的下一个人开始又从 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 100
    
    int 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。

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

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

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

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

![fc2477a01039694a7c8e0d1028f7a6a7.gif][]

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

【值得关注】我的 **[编程学习交流俱乐部][Link 1]**！【点击进入】

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

![1857cbc19cab869312521de965e92e12.png][]

[fc2477a01039694a7c8e0d1028f7a6a7.gif]: /images/20221022/1db26b61847f49dd85f79e1a00310d05.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=teZNipK1
[1857cbc19cab869312521de965e92e12.png]: /images/20221022/978271b456ba44a9a37fdeb7ceefa7a0.png