当前位置:  编程技术>c/c++/嵌入式

约瑟夫环问题(数组法)c语言实现

    来源: 互联网  发布时间:2014-10-23

    本文导语:  问题说明这个问题是以弗拉维奥·约瑟夫斯命名的,它是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁...

问题说明
这个问题是以弗拉维奥·约瑟夫斯命名的,它是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个机智的约瑟夫!

    有N个编号为1~N的人围成一圈,现在每隔两个人(比如:1、4 之间隔了2、3)就将一个人淘汰出去,问最后剩下的是编号为几的人?

算法代码如下

代码如下:

#include
#include

int main(void)
{
    int people_count = 0;
    int *peoples = NULL;
    printf("please input people number: ");
    scanf("%d", &people_count);
    if (people_count < 2){
        printf("can't do Josephn");
    }
    peoples = (int *)calloc(people_count, sizeof(int));
    int i;
    for(i = 0; i < people_count; i++){
        peoples[i] = i+1;
    }
    i = 0;
    int j = 0;
    int rest = people_count;
    while(rest){
        if (i >= people_count){
            i %= people_count;
        }
        if (peoples[i] == 0){
            i++;
            continue;
        }
        if (j++ % 3 ==0 && rest > 1){
            printf("kill people NO. %dn", peoples[i]);
            peoples[i] = 0;
            rest--;
        }else if (rest==1){
            printf("NO. %d is aliven", peoples[i]);
            rest--;
        }
        i++;
    }
    system("pause");
    return 0;
}


    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3