关于一次Python的期末考试的耻辱引出的约瑟夫环问题

起因

期末考试

这次Python的期末考试出现了一道看似非常简单，但是我尝试了各种想法之后最终放弃的一道题。

考试题目

题目：
有1~100，共100个数字。从数字1开始，取偶数位置的数字，重复此过程，问最后剩下的数字是多少。

拿到这道题的时候我非常开心，因为这明显是非常简单的。

于是我就开始动手敲代码了。（事实证明，写程序之前一定要打草稿写思路！）

因为考试的时候是断网的，并且也不能查阅任何资料，所以我当时并不知道del这个函数。

解决方法

自己的想法

初步的想法是用循环嵌套，每次使用切片方法，将选择出来的数字放在新的数组里边，重复做循环。

不断循环后，当剩下一个的时候，结束循环，此时输出的内容就是本题的答案。

根据这个思想，我写出了如下代码。

# -*- coding: UTF-8 -*-
a = [i for i in range(1,101)]
b=[]
while len(b)!=1:
    b=[]
    for item in range(0,len(a)):
        if(item%2==1):b.append(a[item])
    a=b
print(b)

看起来是不是很简单？

没错，它就是很简单，而且运行结果还是对的。

那为什么还会有今天这篇文章呢？

理由很简单，因为当时我并不会python的append函数和while循环的写法。

上面的代码片段是我写这篇文章时候根据当时的想法重新写的程序，确实很简单。 如果我当时能写出来这个的话，python考试就能得满分了。

X总的想法

本来抱着考试半个小时就交卷的心态，用了10分钟写完了4/5的题目，这道题让我足足在考场坐到了最后的时间，结果也是没写出来代码。倒是在草稿纸上写出来答案了。(然而并没有任何的用)

考试结束后，本来以为剩下的都是我不认识的人。结果一回头，我舍友X总坐在后边看着我。

在向X总请教后，X总提出了另一种解决方法。即使用del函数。

# -*- coding: UTF-8 -*-
a = [i for i in range(1,101)]
while(len(a)!=1):
    print(a)
    del a[::2]
print(a)

以上，针对这个问题就解决了。

---

发展

在我事♂后搜索这道题的时候，发现了一个非常有意思的问题——约瑟夫环问题。

下面是来自维基百科的解释

约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，处刑下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

看完这个，我觉得它和考试的题目有那么一丝丝相像。

初体验

C#的解决代码

我是用了最熟悉的C#语言尝试写了这个程序

using System;

namespace TmpTest
{
	class Program
	{
		static Josephus josephus;
		static bool show = false; // 显示中间过程
		static bool multi = true; // 多次使用
		static void Main(string[] args)
		{
			josephus = new Josephus(show,multi);
		}
	}
	class Josephus
	{
		private int totalNumber;
		private int gapNumber;
		private int[] peopleArray;
		private int tmpGapNumber;
		/// <summary>
		/// 初始化数组
		/// </summary>
		private void Init()
		{
			peopleArray = new int[totalNumber];
			for (int i = 0; i < peopleArray.Length; i++)
			{
				peopleArray[i] = i + 1;
			}
		}
		public Josephus(bool show = false, bool multi = false)
		{
			do
			{
				Console.Write("TotalNumber： ");
				totalNumber = int.Parse(Console.ReadLine());
				Console.Write("gapNumber： ");
				gapNumber = int.Parse(Console.ReadLine());
				Init();
				Operation(show);
				Console.WriteLine("result=" + FindPosition());
				Console.WriteLine("-------------------------------");
			} while (multi);
		}
		/// <summary>
		/// 检测是否只剩下一个
		/// </summary>
		/// <returns>返回true/false</returns>
		private bool isLeftOne()
		{
			int number = 0;
			foreach (var item in peopleArray)
			{
				if (item != 0) number++;
				if (number > 1) break;
			}
			return number == 1;
		}
		/// <summary>
		/// 执行的方法
		/// </summary>
		private void Operation(bool show)
		{
			tmpGapNumber = 0;
			int count = 1;
			while (!isLeftOne())
			{
				if (peopleArray[tmpGapNumber = (tmpGapNumber + 1) % totalNumber] != 0) // 只计算不为零的内容
				//tmpGapNumber = (tmpGapNumber + 1) % totalNumber; // 首尾相连
				{
					count++; // 记录间隔个数
					if (count > gapNumber)
					{
						count = 0;
						peopleArray[tmpGapNumber] = 0;
					}
				}
				if (show && tmpGapNumber == 0)
				{
					foreach (var item in peopleArray)
					{
						Console.Write(item + ",");
					}
					Console.WriteLine("----------------\n");
				}
			}
		}
		/// <summary>
		/// 找到最后的位置
		/// </summary>
		/// <returns>返回找到的位置</returns>
		private int FindPosition()
		{
			for (int i = 0; i < totalNumber; i++)
			{
				if (peopleArray[i] != 0) return i + 1;
			}
			return -1;
		}
	}
}

C#的测试结果

我测试了几个数字

在写这段代码时候，我想起来了老师教的循环的一个有趣的写法。

tmpGapNumber = (tmpGapNumber + 1) % totalNumber; // 首尾相连

二进宫

上述方法是单纯使用数组进行实现的，此外还有另一种思路，即使用链表。

对于链表的方法，下面提供另一个问题。

有编号为 1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第一个人按顺时针方向自 1 开始报数，报到 m 者出列，不再参加报数，这时将出列者的密码作为 m，从出列者顺时针方向的下一人开始重新自 1 开始报数。 如此下去，直到所有人都出列。试设计算法，输出出列者的序列。

关于这题的解决方法如下

C语言代码

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct NinGen NinGen;
typedef struct NinGen* pNinGen;
int TotalNumber = 0;
struct NinGen {//建立单循环链表
	int Password;
	int BanGo;//番号
	pNinGen pNext;
};
pNinGen InitNinGen() {
	pNinGen pHead;
	pHead = (pNinGen)malloc(sizeof(NinGen));
	pHead->pNext = NULL;
	TotalNumber = 0;
	return pHead;
}
pNinGen CreatePolynomial(int number) {
	pNinGen pHead, Current, Next;
	int i = 0;
	int InputDataNumber = 0;
	pHead = InitNinGen();
	Current = pHead;
	while (i++ < number) {
		Next = (pNinGen)malloc(sizeof(NinGen));
		if (Next) {
			TotalNumber++;
		}
		else {
			cout << "内存满无法申请新的空间";
			exit(0);
		}
		cin >> InputDataNumber;
		Current->pNext = Next;
		Next->pNext = pHead->pNext;
		Next->Password = InputDataNumber;
		Next->BanGo = i;
		Current = Next;
	}
	return pHead;
}
void NinGenOperation(pNinGen pHead, int Original_M) {
	pNinGen Current, Next, rear;
	int Tmp_M = Original_M;
	while (TotalNumber) {
		int i = 1, j = 0;
		Current = pHead;
		Next = Current->pNext;
		rear = Next;
		while (j++ < TotalNumber - 1) {
			rear = rear->pNext;
		}
		while (i++ != Tmp_M) {
			Current = Next;
			Next = Next->pNext;
		}
		Tmp_M = Next->Password;
		cout << Next->BanGo;
		if (TotalNumber > 1) {
			cout << " ";
		}
		if (Next == pHead->pNext) {
			rear->pNext = Next->pNext;
		}
		Current->pNext = Next->pNext;
		pHead->pNext = Next->pNext;
		
		free(Next);
		TotalNumber--;
	}
	cout << endl;
}
int main() {
	int m, n, t;
	pNinGen pHead;
	cin >> t >> n;
	pHead = CreatePolynomial(n);
	cin >> m;
	NinGenOperation(pHead, m);
}

---

其他内容

下边是wiki百科中python的实现方法。

# -*- coding: utf-8 -*- 
class Node(object):
	def __init__(self, value):
		self.value = value 
		self.next = None

def create_linkList(n):
	head = Node(1)
	pre = head
	for i in range(2, n+1):
		newNode = Node(i)
		pre.next= newNode
		pre = newNode
	pre.next = head
	return head

n = 5 #总的个数
m = 2 #数的数目
if m == 1: #如果是1的话，特殊处理，直接输出
	print (n)  
else:
	head = create_linkList(n)
	pre = None
	cur = head
	while cur.next != cur: #终止条件是节点的下一个节点指向本身
		for i in range(m-1):
			pre =  cur
			cur = cur.next
		print (cur.value)
		pre.next = cur.next
		cur.next = None
		cur = pre.next
	print (cur.value)

结束

以上，由一个考试的耻辱引发的一连串思考就这样结束了。。。

$$\sum _ { i = 1 } ^ { n } \frac { 4 x + 2 y } { 4 }$$

$\left\{\begin{array}{lc}a&b\;=\;0\\c&d=\;\;1\end{array}\right.$

$\left\{ \begin{array}{l}x = 23\\y = 12\end{array} \right.$