SWUST OJ 536:The Josephus Problem

标签: OJ题解  算法设计与分析  算法  python

题干:

在这里插入图片描述

大致题意为:

这个问题是以犹太历史学家Flavius Josephus的名字命名的,他参与并记录了公元前66-70年的犹太人起义。反对罗马人。约瑟夫,作为一个将军,成功地守住了约塔帕塔要塞47天,但在这座城市失陷后,他和40名顽固派躲在附近的一个洞穴里。在那里,反叛者投票赞成死亡而不是投降。约瑟夫建议每个人轮流分派他的邻居,以抽签决定的顺序。约瑟夫设法抽签,作为洞穴中幸存的两个人之一,他说服了他的目标向罗马人投降。你的任务:计算幸存者最初有n个人时的位置。

其实就是一个约瑟夫环,但在本题中不用考虑间隔数,只需要计算出幸存者的下标即可。

思路:

  1. 约瑟夫问题有一个递推公式,即:
    k为偶数时, J ( 2 k ) = 2 J ( k ) − 1 J(2k) = 2J(k) - 1 J(2k)=2J(k)1
    k为奇数时, J ( 2 k + 1 ) = 2 J ( k ) + 1 J(2k+1) = 2J(k) + 1 J(2k+1)=2J(k)+1
    于是可以根据递推公式进行递推。
    显然当k = 1时,J(k) = 1。所以可采用循环或递归方法求解;

  2. 依照以上递推公式,可写出k = [1, 7]范围内的J(k)取值。以k = 6, 7时为例:J(6) = 5, J(7) = 7
    而在k的取值为
    k = 2 n k = 2 ^ {n} k=2n
    时,结果发现J(k)的取值均为1。于是不难得出:
    约瑟夫问题与n的二进制有关

即:对n的二进制做一次向左的循环移位,将新得到的二进制数转化为十进制,即为最终结果。 参考代码如下:

#!/usr/bin/env python
# -*-coding:utf-8-*-
# @Time    :2020/10/5 13:00
# @Author  :Zihan Zhao
# @Site    :
# @File    :main2.py
# @Software:Pycharm Community Edition

if __name__ == '__main__':
	n = int(input())
	n = bin(n)
	binary_n = n[2:]
	print(int(binary_n[1:] + binary_n[0], 2))

算法说明:

  1. 先将待求解的问题规模n输入,并转换为二进制,python提供了一个bin()方法,可以将其转换为二进制数;
  2. 转换之后的结果并不是平时的0、1字符串,而是转换的标准格式(可以百度),为开头会有“0b”,所以采用字符串切片将其删除;
  3. 本算法中将二进制数循环移位的操作,我同样选择切片+拼接,有更好的思路还望各位不吝赐教。之后将其转化为十进制数,转化的语法为:int(binary_num, 2),输出即可。

其他说明:

从本题开始,以后本博客更新的SWUST OJ题解均采用python3作为其编程语言,个别题可能会采用C++。

版权声明:本文为qq_45690050原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45690050/article/details/109088736