2025年约瑟夫环问题,n个人围成一圈,依次按1、2.....m来报数,报数值为m的人出圈,求最后出圈的人和出圈的序列

约瑟夫环问题,n个人围成一圈,依次按1、2.....m来报数,报数值为m的人出圈,求最后出圈的人和出圈的序列约瑟夫环问题 有时也称为约瑟夫斯置换 是一个出现在计算机科学和数学中的问题 在计算机编程的算法中 类似问题又称为约瑟夫环 又称 丢手绢问题 也就是如下图这个样子 简单来讲就是 n 个人围成一圈 依次按 1 2 m 来报数 报数到 m 的出圈

大家好,我是讯享网,很高兴认识大家。

约瑟夫环问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.),也就是如下图这个样子:

在这里插入图片描述
讯享网
简单来讲就是n个人围成一圈,依次按1、2…m来报数,报数到m的出圈,当第一个人出圈后,那么出圈的下一个人则又按1、2…m来报数,如此在一个圈内循环报数,直到全部的人都出去圈。

#include <stdio.h> #define N 100 int main() { 
    int num[N]; int n, m; printf("请输入总人数和报数值:"); scanf("%d%d", &n, &m); //给每个数组赋上编号的值 for(int i = 0; i < n; ++i) { 
    num[i] = i+1; } printf("依次出环的顺序为:"); //josef就是实现的关键函数,函数有一个返回值返回最后出圈的人的编号值,在函数内也实现了打印每个出队的编号 int final = josef(num, n, m); printf("\n最后出的人为原先的%d号", final); return 0; } 

讯享网

下面给出josef函数的实现:

讯享网int josef(int num[],int n,int m) { 
    //定义最后一个出圈人的编号值final int final; int count, i , j = 0; //最外层的循环:每一次循环便实现出圈一个人,直到全部出圈,并且每次将出圈人的编号打印出 for(count = 0; count < n; ++count) { 
    i = 1; // 每次while一次循环表示报一次数,i来记录报数值,当遇到报数值为m的时候跳出循环 while(i < m) { 
    while(!num[j]) j=(++j)%n; //判断是否为0 i++; j = (++j)%n;// } while(!num[j]) j=(++j)%n; printf("%d ", num[j]); if(count == n-1) { 
    final = num[j]; } //在设置为0的之前,先将其打印出,并且判断是不是最后一个出圈 num[j] = 0; } return final; } 

比如我我们输入n和m的值分别为 5 和 3 来模拟一次输出:
在这里插入图片描述
一次循环后(置为0的表示已出圈):
在这里插入图片描述
每循环一次置报数为3的为0, 当到第三次循环时,由2开始从1报数:
在这里插入图片描述
直到后面第4、5次循环结束都为0,最后输出结果就是:
在这里插入图片描述
比如我们再输入100 9:
在这里插入图片描述

小讯
上一篇 2025-02-13 13:20
下一篇 2025-03-09 20:55

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76346.html