约瑟夫环问题

以前写的程序,今天在整理文件的时候发现了,贴出来有需要的朋友可以参考!

问题提出:

约瑟夫环是一个数学的应用问题:已知n个人(以编号0,2,3...n-1分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 解决方案: 约瑟夫环有递归和非递归两种解决方案。 1. 非递归可用数组和循环链表来解决。下面给出用数组解决的源码:

namespace JosephusRing
{
    class Josephus
    {

        public int[] Jose(int total, int start, int span)
        {
            int[] people = new int[total];//定义存储初始人员的数组
            int[] result = new int[total];//定义存储出列顺序的数组
            int count = 0;//定义出列的计数器
            //people数组进行初始化,编号从0开始
            for (int i = 0; i < total; i++)
            {
                people[i] = i;
            }
            //每次循环,出列一个人,共有total-1次循环
            for (int j = total; j > 1; j--)
            {
                start = (start + span - 1) % j;
                //start为要出列的人的编号,%的作用是当报数超出人数时做下一轮循环处理
                result[count++] = people[start];//把出列的人存储到result数组中
                //此循环用于删除出列的人
                for (int k = start + 1; k < j; k++)
                {
                    people[k - 1] = people[k];
                }

            }
            result[count] = people[0];//把剩余的最后一个人添加到result数组中
            return result;
        }
        static void Main(string[] args)
        {
            Josephus jose = new Josephus();
            int[] joseRing = jose.Jose(17,0,3);
            foreach(int num in joseRing)
            {
                Console.WriteLine(num);
            }
            Console.ReadKey();
        }
    }
}

2. 递归函数。先来看一下递归函数: 为了简化问题,我们假设k=0,设f(n,m,i)为n个人的环,报数为m,第i个人出环的编号 当i=1时,f(n,m,i) = (m-1)%m 当i!=1时,f(n,m,i)= ( f(n-1,m,i-1)+k )%n

下面给出C#源码:

namespace JoseRecursion
{
    class Joseph
    {
        //total为总人数,span为步长,count为出列的计数器
        public int Jose(int total,int span,int count)
        {
            int result;//result为第count次出列的人员编号
            if (count == 1) return result = (span - 1) % total;
            else return (Jose(total - 1,span,count - 1) + span) % total;
        }
        static void Main(string[] args)
        {
            Joseph jose = new Joseph();
            int[] result = new int[17];
            for (int i = 0; i < 17; i++)
            {
                result[i] = jose.Jose(17,3,i + 1);
                Console.WriteLine(result[i]);

            }
            Console.ReadKey();
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前沿技墅

从图灵到高德纳:《算法分析导论》作者师承考据

普林斯顿大学计算机系创始人,在斯坦福大学师从D. E. Knuth院士;曾任Adobe Systems公司董事会成员,并在Xerox PARC、IDA和INRI...

27440
来自专栏和蔼的张星的图像处理专栏

12.YOLO系列算法详解

这是YOLO系列的第一篇,文章发表在CVPR2016上,论文链接:YOLOV1. 摘要指出了文章的主要创新之处:把分类问题转换为回归问题,使用一个卷积神经网络...

57820
来自专栏iOS开发攻城狮的集散地

数据结构与算法 - 线性表

16120
来自专栏ACM算法日常

深度学习初探——深层神经网络

后续文章适合(基本的编程知识,熟悉Python、对机器学习有基本了解)想要尝试进入人工智能领域的计算机专业的同学准备。

10330
来自专栏C语言及其他语言

【每日一题】问题 1111: Cylinder

Using a sheet of paper and scissors, you can cut out two faces to form a cylinde...

13320
来自专栏本立2道生

MTCNN算法与代码理解—人脸检测和人脸对齐联合学习

主页:https://kpzhang93.github.io/MTCNN_face_detection_alignment/index.html 论文:htt...

65020
来自专栏凌帅的阅读思考与实践

班科算法进阶(班科专题第7篇,也是最后一篇)

班科算法,很简单的一个公式,居然会有那么强大的应用。越来越多的项目使用BANCOR发币,特别是在熊市交易量小的情况下,更是很多新发项目的首选,真不愧是价值百万的...

15930
来自专栏ATYUN订阅号

AI算法帮助预测火山爆发,为开发全球火山预警系统提供可能

黄石火山观测台的科学家Michael Poland表示,如果没有这些工具,地球科学家就无法跟上卫星传回的信息,因为数据量异常之大。

9850
来自专栏数据猿

深入机器学习系列之:Bisecting KMeans

k-means算法分为两步,第一步是初始化中心点,第二步是迭代更新中心点直至满足最大迭代数或者收敛。

13710
来自专栏数据猿

深入机器学习系列之:4-KMeans

本文会介绍一般的k-means算法、k-means++算法以及基于k-means++算法的k-means||算法。在spark ml,已经实现了k-means算...

12320

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励