在以前初高中参加信息学竞赛的时候，经常会碰到的一个题目叫约瑟夫环。
关于这个问题的详细由来可以在百度进行搜索
在这里简单概述一下问题：
30 个人在一条船上，超载，需要 15 人下船。
于是人们排成一队，排队的位置即为他们的编号。
报数，从 1 开始，数到 9 的人下船。
如此循环，直到船上仅剩 15 人为止，问都有哪些编号的人下船了呢？
在这里我没有使用常见的思路，也就是使用链表来解决，而是通过字典来解决
首先定义一个空字典people={}，并对它进行初始化
初始化字典
在这里说明一下，用1代表这个人是还在船上的，而0代表的是这个人已经下船了。
在初始化完成之后我们先做点接下来数数的准备工作：
i：作为索引的计数，范围在1-30，刚开始的时候定义为1，每次移动都+1。如果i到达31则将其赋值变为从1开始进行计数
j：统计有多少人下船，范围在0-15，刚开始的时候定义为0。当j达到15的时候则终止程序
count：每隔多少个人的一个计数器，范围在0-9，刚开始的时候定义为0。当count变成9的时候，所对应的这个人要下船，也就是people{i}=0，同时j就+1，count也重新赋值为0
前期工作准备好之后，来讲讲逻辑思路：
首先设定好两个判断条件：
1）当i=31的时候要重新赋值为1
2）当j=15的时候就结束程序
其次要判断所对应的这个人是否在船上。可能刚开始第一圈还好，但是到后面因为有些人已经下船了，不能把这个空位置也加入进计数里面。如果这个人不在船上，那么索引i就跳过这个位置继续往下数（i+1）
而如果这个人在船上呢？首先肯定是count执行+1数数。
数完之后，我们也要看看是不是已经数到了9个人了：
1）如果还没有到，那么i继续+1往下继续数
2）如果数到的这个人已经是第9个人了，那么，就要将它标记为下船（people{i}=0），用于统计多少个人已经下船的j要+1，并且把对应的号码打印出来。同时不要忘了count要赋值为0，要从头开始数
约瑟夫环代码
而最终的运行结果就是：
最终下船的编号
网友评论