算法:围成一圏，以等间隔循环去数

有17个人围成一圈(编号0~16),从第0号的人开始从1报数，凡报到3的倍数的人离开圈子，然后再数下去，直到最后只剩下一个人为止，问此人原来的位置是多少号?

 

 

实现思路：
　　 1、将n个人放到一个数组中。
　　 2、完成一次报数，被3整除的，贴上标签，不允许再次报数。
　　 3、统计数组中没有被贴标签的个数，如果大于1，每个没有贴标签的人再次报数，能被3整除的贴上标签，这样循环直到统计数组中没有被贴标签的个数等于1为止。
　　 4、找到这个唯一没有被贴标签的学生在数组的位置。

 

代码实现：

    用链表，即时从链表中删除3倍数的节点；

 

    const int MAX_COUNT = 17;
    CList< int,int > lst;
    void Init()
    { 
      for( int i = 0; i< MAX_COUNT; i++ )
      {
        lst.AddTail( i );
      } 
    };

 

    main()

    {

       Init();

       int nCurStep = 1;
 
       POSITION posCur = lst.GetHeadPosition();
       while(  lst.GetCount() > 1 )
       {       
         if( NULL == posCur )
         posCur = lst.GetHeadPosition();
  
         if( ( nCurStep % 3 == 0) )
         {
             POSITION posDel = posCur;
             lst.GetNext( posCur );
             lst.RemoveAt( posDel );
             nCurStep = 1;
         }
         else
         {
             lst.GetNext( posCur );
             nCurStep++;
         }    
      }

 

      int n = lst.GetCount();
      posCur = lst.GetHeadPosition();
      int nLast = lst.GetAt( posCur );

    }