约瑟夫问题(c++实现)

描述:约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

输入:每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m, n < 300)。最后一行是: 0 0

输出:对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号

input:

6 2

12 4

8 3

0 0 output:

5

1

7

分析:猴子可以用一个数组来表示,数组的值为猴子的编号,当某只猴子出局即把该编号改为0

说明该猴子出局,当最后只剩下一个不为0的值时该值即为猴王编号。

 1 #include<iostream>
 2 using namespace std;
 3 
 4  int main()
 5 {
 6      int n, m;
 7      int a[300];
 8      while ((cin >> n >> m) && !(n == 0 && m == 0))
 9      {
10          for (int i = 0; i < n; i++)
11              a[i] = i + 1;
12          int k = n;//标记剩下的猴子
13          int j = 0;//标记报数m
14          while (k>1)
15          {
16              
17              for (int i = 0; i < n; i++)
18              {
19                  if (a[i] == 0)
20                      continue;
21                  else
22                      j++;
23                  if (j == m)            //退出圈外的猴子编号变为0
24                  {
25                      a[i] = 0; j = 0; k--;
26                  }
27              }
28          }
29          for (int i = 0; i < n; i++)
30          {
31              if (a[i] != 0)
32                  cout << a[i] << endl;
33          }
34      }
35      system("pause");
36      return 0;
37 }

 评论中的算法更简洁

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int Joseph (int n,int m)
 5 {
 6 int i, s=0;
 7 for (i=2; i<=n; i++)
 8 s=(s+m)%i;
 9 return (s+1);
10 }
11 int main()
12 {
13     int m,n;
14     cin>>n>>m;
15     cout<<Joseph(n,m)<<endl;
16     return 0;
17 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吴老师移动开发

【iOS开发】一些不错的文章博客整理

9430
来自专栏吴老师移动开发

【iOS开发】浅谈iOS列表分页数据管理

@property (nonatomic, copy) NSMutableArray *list; @property (nonatomic) NSInteg...

26530
来自专栏吴老师移动开发

【iOS开发】UITableView和UICollectionView多种类型cell处理,更好地组织代码

开发不仅仅是完成功能,还要写出认后来人可以很容易上手维护的代码。今天就记录一下列表数据,多种类型cell时,如何更好的组织代码。从实际需求场景出发,先看一下UI...

1.6K30
来自专栏吴老师移动开发

【iOS开发】iOS 动画详解

在移动开发中,为了提高用户体验,会用到一些动画来提高应用的视觉效果。让人有眼前一亮的感觉。同时有动画的过渡过程,会让应用看起来不是那么的生硬,更吸引用户。

35360
来自专栏吴老师移动开发

【iOS开发】启动时间优化,runloop的一个小技术点

刚接触项目不久,最近产品说有一个点要优化,App的启动页面显示时间太长了。一直在开发其它的app,还真没注意这个点,去看了一下还真是,有的时候启动页面的显示时间...

26620
来自专栏云计算

如何在Linux,Mac或Windows上安装Git

Git是由Linus Torvalds为Linux内核设计开发的。Git为非线性的分布式开发提供了支持,允许多个项目成员同时在一个项目上进行开发。Git是最流行...

32120
来自专栏吴老师移动开发

【iOS开发】RxSwift入门:从Observable.create讲起

刚学习RxSwift的时候,到github看文档,搜索别人的博客。基本上都是从那些例子讲起,像下面这样,自己再跟着用playground写一篇。

15440
来自专栏吴老师移动开发

【iOS开发】UITableView优化

移动开发中,任何一个应用都或多或少的有列表的存在,列表的上下滑动直接关系到用户体验。如果处理不好,就会使得列表滑动起来有明显的卡顿效果。所以对列表的优化,让它更...

18710
来自专栏吴老师移动开发

【iOS开发】RxSwift中的Subject(PublishSubject/BehaviorSubject/ReplaySubject/Variable)

PublishSubject 即是一个被观察者(Observable)也是一个观察者 (Observer)

11510
来自专栏吴老师移动开发

【iOS开发】Cocoapods详解-使用及创建私有库

CocoaPods现在是通过target来组织的,如果项目有多个target,可以写多个target为每个target引入不同的第三方库。 写法:

12650

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励