计算机三级上机约瑟夫环

来源:百度知道 编辑:UC知道 时间:2024/06/12 05:18:56
设有n个人围坐一圈并按顺时针方向从1到n编号,从第s个人开始进行1到m的报数, 报数到第m个人, 此人出圈, 再从他的下一个人重新开始1到m的报数,如此进行下去直到所有的人都出圈为止。现要求按出圈次序,给出这n个人的顺序表p。请考生编制函数Josegh()实现此功能并调用函数WriteDat()把编号按照出圈的顺序输出到OUT.DAT文件中。
注意:第1个出圈的编号存放在p[0]中,第2个出圈的编号存放在p[1]中,直至第n个出圈的编号存放在p[n-1]中。
设 n = 100, s = 1, m = 10进行编程。
注意: 部分源程序存放在PROG1.C中。
请勿改动主函数main()和输出数据函数WriteDat()的内容。
#include <stdio.h>
#define N 100
#define S 1
#define M 10
int p[100], n, s, m ;
void WriteDat(void) ;
void Josegh(void)
{
}
void main()
{
m = M ;
n = N ;
s = S ;
Josegh() ;
WriteDat() ;
}
void WriteDat(void)
{
int i, j = 0 ;
FILE *fp ;
fp = fopen("out.dat", "w") ;
for(i = 0 ; i <= N - 1 ; i++) {
printf("%4d ", p[i]) ;
fprintf(fp, "%4d", p[i]) ;
j++ ;
if(j % 10 == 0) {
printf("\n") ;
fprintf

约瑟夫环有好多种解法,
但是大体的可以分为两类:
1. 将符合出圈要求的人进行标注,但是不出圈,只是下次再轮到此人时,直接跳过,不参加报数
2. 将符合出圈要求的人直接出圈(从环中删除),剩下的人继续报数

这里列的是第二种方法

出圈的处理在这里: p[i-1]=i;
由于已经有人出圈,所以编号也就得-1了:(s1+m-1)%i