约瑟夫环问题：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

 

第一种方法：要求将每次出列的人的序号输出，并输出最后一个出列的人。

代码如下：

[html] view plaincopy

 

1 //c语言用数组实现约瑟夫环  

2 #include  

3 #include  

4 void main()  

5 {  

6     int y(int n,int m);  

7     int p,q,r;  

8     printf("请输入参选人的个数p和开始的位置q：\n");  

9     scanf("%d%d",&p,&q);  

10     r=y(p,q);  

11     printf("最后那个人的初始位置是：%d\n",r);  

12 }  

13 int y(int n,int m)  

14 {  

15     int i,j=0,s=0,l;  

16     int *a=(int *)malloc(sizeof(int));  

17     int *b=(int *)malloc(sizeof(int));  

18     for(i=0;i;i++)  

19     {  

20         a[i]=i+1;  

21     }  

22     a[n]=-1;  

23     for(i=0;j!=n;i++)  

24     {  

25         if(a[i]==-1)   

26             i=0;  

27         if(a[i]!=0 && a[i]!=-1)  

28             s++;  

29         if(s==m)  

30         {  

31             b[j]=a[i];  

32             a[i]=0;  

33             j++;  

34             s=0;  

35         }  

36     }  

37     for(i=0;i;i++)  

38     {  

39         printf("]",b[i]);  

40     }  

41     printf("\n");  

42     l=b[n-1];  

43     return l;  

44 }  

第二种方法：只要求出最后出列的那个人的位置即可

这种方法利用了约瑟夫环的公式，用到了递归，相对简单。

代码如下，

[html] view plaincopy

 

45 #include  

46 void main()  

47 {  

48     int y(int n,int m);  

49     int a,b,c;  

50     scanf("%d%d",&a,&b);  

51     c=y(a,b);  

52     printf("最后一个数为：%d\n",c);  

53 }  

54 int y(int n,int m)  

55 {  

56     int x;  

57     if(n==1)  

58         x=1;  

59     else  

60     {  

61         x=(y(n-1,m)+m)%n;  

62         if(x==0) x=n;  

63     }  

64     return x;  

65       

66 }  

希望对各位有用。

我的博客：

新浪博客

网易博客

Google博客

我的邮箱：

jinhuer168@163.com