关于约瑟夫环的问题

haoyue1014 2009-11-14 10:05:47

今日解决了一个约瑟夫环的问题，但是总觉得不够好，
各位高手把你们好的算法拿来分享一下。。。。

...全文

185 16 打赏收藏转发到动态举报

写回复

用AI写文章

16 条回复

切换为时间正序

请发表友善的回复…

发表回复

ernst20020530 2009-11-15

打赏
举报

這個是不是加法群的問題？

timeriver_wang 2009-11-15

打赏
举报

[Quote=引用 5 楼 mstlq 的回复:]
引用 3 楼 haoyue1014 的回复:
哥哥，what are you doing?

这就是约瑟夫环问题的数学解法……

[/Quote]
你是错的

haoyue1014 2009-11-15

打赏
举报

[Quote=引用 7 楼 whg01 的回复:]
http://www.cnblogs.com/woodfish1988/archive/2007/02/18/652251.html
看看这个就理解mstlq的代码了。
[/Quote]
不过多亏有这楼的帮助

haoyue1014 2009-11-15

打赏
举报

[Quote=引用 6 楼 jernymy 的回复:]
?
......
[/Quote]
不过多亏有这楼的帮助

haoyue1014 2009-11-15

打赏
举报

[Quote=引用 12 楼 wnjok 的回复:]
引用 5 楼 mstlq 的回复:
引用 3 楼 haoyue1014 的回复:
哥哥，what are you doing?

这就是约瑟夫环问题的数学解法……

你是错的
[/Quote]
我看这个算法最好了。

teddymy 2009-11-15

打赏
举报

oj通过了，哈哈

honghu069 2009-11-15

打赏
举报

如果要求每轮被淘汰人的序号
可以用线段树优化，这样比直接模拟效果要好多了

qq25304239 2009-11-14

打赏
举报

楼上的我看不懂。。。。。最后剩下一个人？

企-鹅 2009-11-14

打赏
举报



//約瑟夫問題

#include <stdio.h> 

#include <stdlib.h> 

#define N 41 

#define M 3 



int main(void) { 

    int man[N] = {0}; 

    int count = 1; 

    int i = 0, pos = -1; 

    int alive = 0; 



    while(count <= N) { 

        do { 

            pos = (pos+1) % N;  // 環狀處理 

            if(man[pos] == 0) 

                i++; 



            if(i == M) {  // 報數為3了 

                i = 0; 

                break; 

            } 

        } while(1); 



        man[pos] = count; 

        count++; 

    } 



    printf("\n約琴夫排列："); 

    for(i = 0; i < N; i++) 

        printf("%d ", man[i]); 



    printf("\n\n您想要救多少人？"); 

    scanf("%d", &alive); 



    printf("\nL表示這%d人要放的位置：\n", alive); 

    for(i = 0; i < N; i++) { 

        if(man[i] > alive) 

            printf("D"); 

        else 

            printf("L"); 



        if((i+1) % 5 == 0) 

            printf("  "); 

    } 

    printf("\n"); 



    return 0; 

}

whg01 2009-11-14

打赏
举报

http://www.cnblogs.com/woodfish1988/archive/2007/02/18/652251.html
看看这个就理解mstlq的代码了。

jernymy 2009-11-14

打赏
举报

?
......

mstlq 2009-11-14

打赏
举报

[Quote=引用 3 楼 haoyue1014 的回复:]
哥哥，what are you doing?
[/Quote]
这就是约瑟夫环问题的数学解法……

yzschen521 2009-11-14

打赏
举报

说一下算法啊

haoyue1014 2009-11-14

打赏
举报

哥哥，what are you doing?

mstlq 2009-11-14

打赏
举报

#include <stdio.h>



int main(){



  int n, m, i, s=0;



  printf ("N M = "); scanf("%d%d", &n, &m);



  for (i=2; i<=n; i++) s=(s+m)%i;



  printf ("The winner is %d\n", s+1);



}

mstlq 2009-11-14

打赏
举报

#include <stdio.h>



int main(){



  int n, m, i, s=0;



  printf ("N M = "); scanf("%d%d", &n, &m);



  for (i=2; i<=n; i++) s=(s+m)%i;



  printf ("The winner is %d\n", s+1);



}