专栏首页算法与编程之美Python|约瑟夫环算法

Python|约瑟夫环算法

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。(模拟此过程,输出出圈的人的序号)

解决方案

这道题涉及到的算法叫做“约瑟夫算法”,我们需要将列表内所有人类似排列成一个“圈”来解决,需要将前一次删除后剩下的元素的索引不变,但是位置向前提。无限循环这个“圈”,直到删除到只剩一个。

这道题的关键在于如何将每个数的索引数字固定,在删除前一个数字后,后面的数字都应该在排序中加一。所以我们一开始需要创建一个列表,从1开始到含有位数的数字,代表每个数字的索引列表。

代码示例:

def Josephus_problem(num,gap):

     location_list = [a for a in range(1,num+1)]

     if num ==   1 :

         return

     else:

         index = 0

         for i in range(num-1):

            index = (index + gap  )%len(location_list) - 1

            print("本次出局的人为:",location_list[index])

            del location_list[index]

            if index == 0:

                index = 0

         print( "最后剩下的为:",location_list[0])

 

Josephus_problem(5,3)

结语

这道题的解决方法有很多种,这里主要介绍一下这种算法。还有重点为推导出(index + gap )%len(location_list)这个公式。

本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:李和龙

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端|Js的基础知识介绍

    Js全称是Javascript,是一种基于对象和事件驱动并具有相对安全性的客户端脚本语言。同时也是一种广泛用于客户端Web开发的脚本语言,常常用来给HTML网页...

    算法与编程之美
  • Python|力扣周考——顺次表

    我们定义「顺次数」为:每一位上的数字都比前一位上的数字大1的整数。请你返回由[low, high] 范围内所有顺次数组成的有序列表(从小到大排序)。

    算法与编程之美
  • PS|三大图层样式运用

    PS作为一个很全面的图像处理软件,为大家提供了许多的功能,而其图层样式更是使得使用者有更多的方式对图像细节进行处理。接下来,就让我们去学习一下PS三大常用图层样...

    算法与编程之美
  • 取得真经!中国连夜宣布重大发现,“悟空”用火眼金睛看到了暗物质!

    镁客网
  • STM32的Flash读写保护,SWD引脚锁的各种解决办法汇总(2020-03-10)

    问题现象: MDK,J-Flash,IAR等无法连接芯片,有时候链接上了,但是无法下载。 注意:如果下载器线的接触不良,也会有这个问题。

    armfly
  • xpath路径的写法

    3.查找页面上第一个form元素内的直接子input元素(即只包括form元素的下一级input元素,使用绝对路径表示, 单/号)://form[1]/inpu...

    小小咸鱼YwY
  • 数据库安全能力:安全威胁TOP5

    在数据库的安全问题已跃至CSO的工作内容象限榜首的今天,对数据库安全的防御是艰苦的旅程,如何让针对业务安全和数据安全的攻击成为一场废鞋底的马拉松,防止恶意行为者...

    FB客服
  • Facebook超牛的人脸识别能力

    ? 当问到两张陌生照片中的面孔是否是同一个人时,一个人类答对的几率是97.53%。Facebook新开发的软件面对这一挑战的分数是97.25%,不论明暗的变化...

    小莹莹
  • Facebook超牛的人脸识别能力

    大数据文摘
  • 快速学习ES6新特性-简介

    现在使用主流的前端框架中,如ReactJS、Vue.js、angularjs等,都会使用到ES6的新特性,作为一名高级工程师而 言,ES6也就成为了必修课,所以...

    cwl_java

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动