首页 > 代码库 > C++ 约瑟夫环

C++ 约瑟夫环

约瑟夫环:

已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

例如:n = 9, k = 1, m = 5 【解答】出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

 1 int main()//约瑟夫环 2 { 3     int n=9, m=5,k=2;//n是人数(编号1,2,……,x),m是出列号,k是起始人编号 4     int j=0, l=0; 5     int a[10]; 6     for (int i=1;i<=9;i++) 7     { 8         a[i]=1; 9     }10 11     while (l<n) 12     {13         for (int i=1;i<=n;i++) 14         {15             if (a[i]==1) 16             {17                 j++;18                 if (j==m) 19                 {//满足出列号20                     a[i]=0;21                     if (i==n&&k>1) 22                     {23                         cout<<1<<endl;24                     }25                     else26                     {27                         cout<<i+(k-1)<<endl;28                     }29                     j=0;30                     l++;31                 }32             }33         }34     }35 36 }

 

 

 

顺便附上一个数学思想的约瑟夫环解法,要求有点不一样。

就是一共n个人,查到m的人出圈,求最后圈里的人是几号。

int fun(int n, int m)
{
    int i, r = 0;
    for (i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}

C++ 约瑟夫环