关于数组实现约瑟夫环的有关问题
关于数组实现约瑟夫环的问题
一个约瑟夫环的小程序,初学者,也是刚刚查阅了约瑟夫环的具体过程,但是对这些有些不太理解,特别是第二个for循环中使用数组b对出局人的控制,望能够解释一下,谢谢
------解决思路----------------------
仅供参考:
------解决思路----------------------
几点解释:
一个约瑟夫环的小程序,初学者,也是刚刚查阅了约瑟夫环的具体过程,但是对这些有些不太理解,特别是第二个for循环中使用数组b对出局人的控制,望能够解释一下,谢谢
#include <stdio.h>
#define N 100
main () {
int a[N]={0}, b[N]={0};
int i,p,n=-1, sum;
printf("请输入总人数:");
scanf("%d",&p);
for (i = 0; i <= p-1; i++) {
a[i] = i + 1;
b[i] = 1;
} printf("输出:");
for (sum = p; sum > 1; sum--){
for (i = 1; i <= 7;) {
n = (n + 1)%p;
if (b[n] == 1)
i++;
}
printf(" %d", a[n]);
b[n] = 0;
}
for (i = 0; b[i] == 0; i++);
printf("\n最后一位:%d\n", a[i]);
}
------解决思路----------------------
仅供参考:
//假设有n个人团团围做,从第1个人开始数数,数到第m个人时候,第m个人出列,
//然后继续从1开始数数,数到第m个人退出
#include <stdio.h>
#include <conio.h>
int i,k,t;
int n,m;
static char f[1001];//0该座位未出圈,1该座位已出圈
void main() {
while (1) {
printf("Input n m(1000>=n>=m>=1):");
fflush(stdout);
rewind(stdin);
if (2==scanf("%d%d",&n,&m)) {
if (1000>=n && n>=m && m>=1) break;
}
}
t=0;//已出圈总人数
i=1;//座位编号
k=1;//当前要数的数
while (1) {
if (0==f[i]) {
if (m==k) {
t++;
f[i]=1;
printf("%3d ",i);
if (0==t%10) printf("\n");
if (t>=n) break;
}
k++;if (k>m) k=1;
}
i++;if (i>n) i=1;
}
cprintf("Press any key ...");
getch();
}
------解决思路----------------------
几点解释:
各变量的含义:
a[N]记录每个人的编号:1、2、3……N
b[N]对应每个人是否出局的标记:值0表明人已出局
理解第二个for循环
n从-1开始
for (sum = p; sum > 1; sum--){ //sum>1表明最后只留一人
for (i = 1; i <= 7;) { //从这里看出数到7的人出局
n = (n + 1)%p; //n每次往前走一步,但具体值需对p求余,这是一个环
if (b[n] == 1) //只有未出局的人才计数,所以只有b[n]为1,才算走了一步
i++;
}
printf(" %d", a[n]); //打印出局人的编号
b[n] = 0; //此人出局
}