请在下方输入要搜索的题目：

设有n个人围成一圈，每个人的编号依次为1，2，3，。。。，n。现从编号为k的人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，依此类推，直到所有人都出列为止。现要求该n个人的出列顺序。这个问题称为约瑟夫（Josephu）问题。试编写求解约瑟夫问题的算法。

发布时间：2025-02-22 11:49:28

推荐参考答案 ( 由快搜搜题库官方老师解答 )

联系客服

答案：设以自然数1，2，3，。。。，n为元素构成一个循环队列，并用一个数组A（1：n）存放该队列中各元素的直接后继，其中A（i）表示表示整数i的下一个整数。在开始时，该数组中的各元素为：A(i) = i 1 ; i = 1, 2, 3, ……., n-1A(n) = 1;以后由于不断地有元素从这个队列中出来，该数组中的元素值也在不断地变化。即当有元素出列后，某些整数i的下一个数就不一定是i 1了。下面的算法中用数组B（1：n）依次存放每次的出列者。# include “ stdlib.h “void jsphu ( int n , int m , int k , int b [ ] ){ int i , j , t , *a ;a = malloc ( n*sizeof ( int ) ) ;for ( i = 0 ; i< n ; i )a[ i ] = i 1 ;a[ n-1] = 0 ;k = k-1 ;for ( j = 0 ; j < n ; j ){ for ( i = 0 ; i < n ; i ){ t = k ; k = a[ k ] ; }b[ j ] = k 1; a[ t ] = a[ k ] ;k = a[ k ] ;}free ( a ) ;return ;}