Josephus问题分析与探讨

Department of Computer Science

Josephus问题是一个经典的递归问题。本文从问题的编程解决入手,提出静态数组、环链表、递归等3种解题方案。本文还对问题作进一步分析,考虑解的稳定点,最后提出一个优化方案,将问题的解决归约到一个较小的规模。

The Josephus problem is a typical recursive problem in discrete mathematics.This paper,begins with the programming solution to the problem,advances three feasible models,--static array,circular linear table and recursive formula.It makes a further analysis to the problem,concentrating on the fixed points in the permutation of the eliminated persons.In the end,It reach es an optimized solution to the problem,reducing the problem scope remarkably.