Blog Content

约瑟夫环，报数出列

算法 C/C++   2011-02-05 08:12:15

---

直接上代码了。

/*
题目描述 ：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；
他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

输入：7 3
输出：3 6 2 7 5 1 4

0,1,2,3,4,5,6
-----------------
数值变化
1,2,3,4,5,6,7
1,2,4,5,6,7
1,2,4,5,7
1,4,5,7
1,4,5
1,4
4
----------------
索引变化
0,1,2,3,4,5,6
0,1,3,4,5,6
0,1,3,4,6
0,3,4,6
0,3,4
0,3
3

第i次淘汰的索引可以归纳出下面的递归公式： 
f(n,m,i)=[f(n-1,m,i)+m]%n; 
当i=1时，f(n,m,1)=(n+m-1)%n;

*/

#include 


int lastRem(int n,int m,int i)
{
    if(i==1)
       return (n+m-1)%n;
    else
       return (lastRem(n-1,m,i-1)+m)%n;
}

int main()
{
    
    int a ;
    for(int i=1;i<=7;i++){
        a = lastRem(7, 3,i)+1;
          printf("%d\n", a);
    }

    
    printf("\n");

    return 0;
}

---

上一篇：Lintcode-5:在数组中找到第k大的元素
下一篇：CPP 学习路线及资源推荐