网站首页 C及单片机 约瑟夫环问题数组解决
约瑟夫环问题数组解决
编辑时间:2017-03-26 作者:金满斗 浏览量:732 来源:原创

这段时间一直右胳膊疼,没怎么熬夜,店里的生意也属于淡季,有时候就跑C语言吧装装13。帮人家解答一些简单的问题顺便也是温故知新吧,前天发现有人问个约瑟夫环的问题,说要数组实现。如果要用aardio实现应该是分分钟的事情,高级语言的数组push pop起来那个爽啊,但是用C语言,由于C语言的数组是固定长度的,一下还把我难住了,多想用链表啊,链表毕竟更灵活。

终于,在自己不会又百度的情况下,找到了一个模拟的很好的代码,最起码和我的思维很合拍。这里放上来,有可以愉快的玩耍啦。

上代码

/*
约瑟夫环问题
问题由来 
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,
39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,
每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从。Josephus要他的朋友先假装遵从,
他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
*/ 
 
#include<stdio.h>
 
int main() {
    int num[50],n,m,i,j;
    int len,start = 0,counter = 1;                             //len列队剩余人数 
    printf("请输入总人数和隔几人一杀,空间空格隔开,回车结束\n");
    scanf("%d %d",&n,&m);            						//n是人数,m为隔几位一杀 
    if(n < 0 || n > 50 ) n = 50;   							//这里判断输入,如果输入不合理就按默认的50 
    if(m < 1 || m > n) m = n/2;    							//这里也是一样,输入不合理就默认为25 
    printf("总人数:%d,隔:%d位一杀\n",n,m);
    for(i = 0; i < n; ++i) num[i] = i + 1; 					// 预填,先把人数模拟出来 
    len = n; 												// len保留队列中现有人数
    
    while(len >= m) {                      //如果剩余的人数已经少于报数杀人的数量了,游戏就不必玩了,是幸存者 
        if(counter == m) {          						//数数数到要杀的 
            printf("%d 号出去受死\n",num[start]);
            --len;											//剩余人数减一,因为杀了一个嘛 
            //重新整顿人数 
            for(j = start; j < len; ++j){ 
                num[j] = num[j + 1];						//后面后补到已被杀的这个位置 
			}  
            counter = 1;                                    //数数人又从1开始 
        }
        else {
            ++counter;                                   //要杀的人继续数数 
            ++start;                                       //要杀的下标 
            start %= len;                                  //当数到的下标超过剩余人数后,就倒头,这个求余再这里还有这么大的作用,以后一定注意 
        }
    }
    printf("要幸存必须站在:");
    for(i=0;i<m-1;i++){
		printf("%d位 ",num[i]); 
	} 
    return 0;
}


来说两句吧