文档介绍：数据结构与算法
实验报告(2)
实验二
求解约瑟夫问题
实验日期:2002-11-19
【问题描述】:
设有n个人围成一个圆圈坐下,对所有围从的人从某个位置开始编号为1,2,3,……,n,从编号为1的人开始报数1,报数依交进行,报数n的人即出列,下一个人从1开始报数,再报数m的人便是第二个出列的人如此重复下去,直到最后一个人出列为止,于是便得到一个出列的顺序,这称之为约瑟夫(Josephu)问题。
【求解方法说明】:
因为该问题中报数一直是循环进行的,因此可以把n个人的编号 1,2,3……n组织成一个循环结构。
为了使报数始终按一个规则进行下去,在有人出列以后,剩下的人要仍然构成一个圆圈(编号不变),因此宜采用链式存储结构。
报数过程以1到m重复进行。每一轮(1到m)报数过程中,一方面要选出本轮报数的出列者,也就是要记住正在报数的人之编号,当报数到m时,让该人出列并加入到出列人的队尾;另一方面为了保证报数m的人出列后,剩下的人仍构成一个圆圈,在报数m的人出列后,应该使报数m的下一个人(下一轮报数1的人)紧接在报数m的前一个人(本轮报数m-1的人)之后。也就是说,每次报数时还要记住刚刚报完数的人之编号,目的是要记下报数为m-1的人的编号,以便在报数m的人出列后将其后件改为报数为m+1的人(下一轮报数1的人)。
【算法简介】:
根据上述求解方法说明,可以归纳出算法思路如下:
1. 要把n个围坐人的编号1,2,3……n(每个编号代表一个人)组织成一个循环的链式结构,可以利用一个数组来实现。例如,定义一个数组A(1:n)来存放,其中数组元素A(i)存放i的下一个编号(即指示i的下一个报数人),初始数组A 中各元素为:
A(i)= i+1, i=1,2,3,……,n-1
A(n)= 1
2. 为了得到出列人的序列,可以将报数过程中陆续出列的人依次存放到另一个数组B中,待全部人出列时,B中存放的是出列的序列。
3. 整个报数过程是 n个人逐一出列的过程,它由若干轮1到m报数完成。为了使未出列的人始终保持一个循环链,在每一轮报数的过程中,要随时记住当前报数的人和他的前一个(刚报完数的人)。假设用变量k记当前报数的人,用变量l记刚报完数的人,则每一次报数时要做l<-k,还要把下一个要报数的人送到k中,即做:k<-A(k)。
当完成一轮报数(1到m)时,一方面要使当前报数的人k出列,并加入到出队队列中,假设当前的k报数m,且是出列的第i个别,数组B中存放出列队列,即要做B(i)<-k;另一方面使下一个将要报数的人A(k)紧接在k的前一个人(刚报完数的人)之后,也就是说:
k出列之前报数人链中有:……,l, k, A(k)
k出列之后报数人链变成:……, l, A(k), ……
此时A(k)成为当前报数人,为此,当一轮报数结束时,应该做:
B(i)<-(k+1); A(l)<-A(k); k<-A(k)
【简单语言算法】:
输入:A(1:n), m
输出:B(1:n)
FOR i=0 TO n-1 DO A(i)<-(i+1)
A(n-1)<-0
k<-0; l<-0; i<-0;
WHILE i<n DO
{FOR j=1 TO m-1 DO {l<-k; k<-A(k)}
B(i)<-