问题 填空题

阅读以下函数说明和C语言函数,将应填入 (n) 处的字句写在对应栏内。
[说明]
这是一个求解Josephus问题的函数。用整数序列1,2,3…,n表示顺序围坐在圆桌周围的人,并采用数组表示作为求解过程中使用的数据结构。Josephus问题描述,设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,…如此反复直到所有的人全部出局为止。
[C函数]
void Josephus(int A[],int n,s,m)
(int i,j,k,temp;
if(m==O){
printf("m=0是无效的参数!\n");
return;
}
for(i=0;i<n;i++) A[i]=i+1; /*初始化,执行n次*/
i= (1) /*报名起始位置*/
for(k=n;k>1;k-){
if( (2) ) i=0;
i= (3) /*寻找出局位置*/
if(i!=k-1){
tmp=A[i];
for(j=i;J<k-1;j++) (4) ;
(5) ;
}
}
for(k=0;k<n/2;k++){
tmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp;
}
}

答案

参考答案:s-1 (2) i==k (3) (i+m-1)%k (4) A[j]=A[j+1] (5) A[k-1]=tmp

解析: JosephuS问题是一个经典的顺序表问题,所用到的数据结构就是一维数组。整个算法过程实际上就是一个从n到1的循环。当还剩下k个人的时候,首先找到出局位置,然后将出局者交换到第k-1位置。循环结束,将数组逆置,即得到出局序列。空(1)是赋报名起始位置,应填“s-1”:(2)填“i==k”。空(3)是寻找出局位置,应填“(i+m-1)%k”。数组A的元素要循环向右移动一个位置,则(4)填“A[j]=A[j+1](5)填“A[k-1]=tmp”。

选择题
多项选择题