Chinaunix首页 | 论坛 | 博客
  • 博客访问: 43007
  • 博文数量: 10
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 95
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-28 00:25
个人简介

加油

文章分类

全部博文(10)

文章存档

2015年(1)

2014年(8)

2013年(1)

我的朋友
最近访客

分类: C/C++

2014-11-09 21:10:34

题目描述:M个人围成一个圈,从第一个人开始报数1,报到N的人退出,下一个人继续从1开始报数,最后剩下的一个人的胜利者,求该胜利者。
分析:使用C++标准库bitset,每个人对应一位,然后开始报数,当报到N时将该位置为0.从下一位继续开始报数。
//M个人,报到N的退出。

点击(此处)折叠或打开

  1. //M个人,报到N的退出。
  2. void JosephRing(int M ,int N)
  3. {
  4.     assert(M > 0 && N > 0);
  5.     int i = 0;
  6.     int num = 0;//报数号。
  7.     std::bitset<M> bit;
  8.     bit.set(); //所有的人都在圈中,所有位都除初始化为1.
  9.     //当bit中只有一个人时退出。
  10.     for (;bit.count() > 1;++i)
  11.     {
  12.         //只有在圈中的人才报数。
  13.         if(bit.test(i % M))
  14.         {
  15.             ++num;
  16.             
  17.         }
  18.         if (num == N)
  19.         {
  20.             bit.reset(i);
  21.             num = 0;
  22.         }
  23.     }
  24. }


阅读(1301) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~