关于数组实现约瑟夫环的问题

C语言 码拜 9年前 (2015-05-11) 998次浏览 0个评论

一个约瑟夫环的小程序,初学者,也是刚刚查阅了约瑟夫环的具体过程,但是对这些有些不太理解,特别是第二个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]);
	} 
10分
仅供参考:

//假设有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();
}
约瑟夫问题的数组解法
http://blog.csdn.net/zhangxiangdavaid/article/details/25057811
10分
几点解释:

各变量的含义:
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;                   //此人出局
}  

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明关于数组实现约瑟夫环的问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!