趣味算法--约瑟夫环问题

分类:博客 热度:

问题描述

已知n个人(以编号1,2,3,...,n分别表示)围坐在一张圆桌上。指定编号为k的人开始从1报数,数到m的那个人出列;出列那个人的下一位又从1开始报数,数到m的那个人出列;以此规则重复下去,直到圆桌上的人全部出列。

分析解决

解决方法主要有逻辑分析、数学分析法。

逻辑分析:就是按照游戏规则一个个报数,报到m的人出局,结构层次简单清晰明了。这种方式实现主要采用顺序表实现

数学分析:采用数学方式归纳统计分析出每次出局人的规律,直接得出每次出局的人,然后以代码实现。这种方法需要较强的数学分析能力,代码较简单。这种实现主要采用数学公式。

逻辑分析

先以C语言数组为例,由于C语言数组不能像Java、Python这种面向对象语言的数组那样使用删除数组元素的方法,每次删除数组中的一个元素,都要将后面元素前移一位,这里简单的将删除的元素值设为0。

假设总人数n=7,从编号k=2的人开始,数到m=3的人出局,下面是分析过程。

 C 数组版

运行后,结果与上面分析一致

下面给出Java的数组对象实现和Python的列表实现。因为Java数组对象和Python列表都有删除元素的方法,这里的逻辑和上面稍有不同。

 java数组版

代码运行结果与分析一致,java数组版比C数组版逻辑处理代码稍微简单一点点。

 Python列表版

运行结果与分析一致,可以看出C、java和Python用数组实现约瑟夫环,Python的代码是最短的,C的代码最长,Java居中。当然代码都还有优化的地方。

也可以使用环形链表实现。

数学分析

总人数有n个人,从k的位置开始报数,报数到m的人出局。

先假设人数n足够大,不管出局多少个人,都不会回到编号为1的位置。

第一次出局的人的位置为k-1+m,出局人的下一位从新开始报数,这就成了一个新的约瑟夫环,相当于第二次报数的起始位置从k+m开始,总人数为n-1;

第二次出局的人的位置为k+m-1+m,出局人的下一位从新开始报数,这就又成了一个新的约瑟夫环,相当于第三次报数的起始位置从k+2m开始,总人数为n-2;

第三次出局的人的位置为k+2m-1+m,出局人的下一位从新开始报数,这就又成了一个新的约瑟夫环,相当于第四次报数的起始位置从k+3m开始,总人数为n-3;

。。。

第t次出局的人的位置为k+tm-1,出局人的下一位从新开始报数,这就又成了一个新的约瑟夫环,相当于第t+1次报数的起始位置从k+tm开始,总人数为n-t。

因为假设人数n足够大,不管出局多少个人,都不会回到编号为1的位置,相当与出局后又成了一个新的约瑟夫环,所以(k+tm-1)%(n-t)=(k+tm-1)为出局人的位置。

现在假设k-1+m>n

 当编号n报数时还没有报到m,则从编号1接着编号n报数,相当与n后面还是接着无穷无尽等待报数的人。

假设循环c轮,编号p,报的数是m,编号p要出局,相当于k-1+m=cn+p,即(k-1+m)%cn=p,剩余的人数为n-1。

按上面的方法很容易得出第t次出局的人的编号为(k+tm-1)%(n-t)。

当k-1+m=n时

 即编号为n的人报数为m,此时(k+tm-1)%(n-t)=0,重新开始的位置为编号为1的位置。

 Java 实现
package yuesefu;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Yue {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入总人数:");
        int total = scanner.nextInt();
        System.out.print("请输入出局号:");
        int count = scanner.nextInt();
        System.out.print("请输入开始的编号:");
        int start = scanner.nextInt();
        
        /*初始化约瑟夫环*/
        List<Integer> people = new ArrayList<Integer>();
        for (int i = 1; i <= total; i++) {
            people.add(i);
        }
        int k=start-1;
        System.out.println("约瑟夫环为:"+people);
        while (people.size()>0) {
            k = (k + count)%(people.size())-1;
            if(k<0) {
                System.out.println("出局人的编号为:" + people.get(people.size()-1));
                people.remove(people.size()-1);
                k=0;
            }else {
                System.out.println("出局人的编号为:" + people.get(k));
                people.remove(k);
            }
        }
    }
}
 
Java 实现
 Python实现
total = int(input("请输入总人数:"))
out = int(input("请输入出局号:"))
start = int(input("请输入开始位置:"))
 
#初始化约瑟夫环
people = []
for i in range(total):
    people.append(i+1)
 
print("需要处理的约瑟夫环为:\n",people)
now = start - 1     #now指定当前报数的人
while len(people):
    now = (now + out)%len(people)-1
    if now < 0:
        print("编号为 %d 的人出局" %people[now])
        people.pop(now)
        now = 0
    else:
        print("编号为 %d 的人出局" % people[now])
        people.pop(now)
 
Python实现

测试的结果也是和前面的测试结果一样的,后面程序处理更简单些,省了很多逻辑判断环节。

上一篇:以太坊ERC20代币开发 下一篇:比特币和区块链使用了什么技术
猜你喜欢
热门排行
精彩图文
  • 比特币和区块链使用了什么技术
    比特币和区块链使用了什么技术
    用最简单的方式解释什么是比特币和什么是区块链技术 本文主要回答以下几个问题 比特币简介区块链技术简介比特币为啥被创造出来比特币的价值到底是
  • 趣味算法--约瑟夫环问题
    趣味算法--约瑟夫环问题
    问题描述 已知n个人(以编号1,2,3,...,n分别表示)围坐在一张圆桌上。指定编号为k的人开始从1报数,数到m的那个人出列;出列那个人的下一位又从1开始报
  • 以太坊ERC20代币开发
    以太坊ERC20代币开发
    以太坊ERC20代币开发首先需要对以太坊,代币,ERC20,智能合约等以太坊代币开发中的基本概念有了解。根据我们的示例代码就可以发行自己的以太坊代币。 什
  • 使用自动内存管理
    使用自动内存管理
    本节提供有关Oracle数据库的自动内存管理功能的背景信息,并包含有关启用此功能的说明。涵盖以下主题: 关于自动内存管理 启用自动内存管理 监视和调
  • WordPress 4.9.4 修复自动更新功能
    WordPress 4.9.4 修复自动更新功能
    几年了,第一次看到这么连续的两个版本发布,WordPress 4.9.4 的发布是为了修复在WordPress 4.9.3 中出现的一个新问题:无法自动更新WordPress内核版本。 起因是