约瑟夫问题的Python和C++求解方法

yipeiwu_com7年前Python基础

么是约瑟夫问题?
约瑟夫问题是一个有趣的数学游戏,游戏规则如下:
1、N个人围成一个圈,编号从1开始,依次到N。
2、编号为M的游戏参与者开始报数,报数从1开始,后面的人报数接龙,直到K为止,报数为K的人将出局。
3、出局者的下一个玩家接着从1开始报数,如此循环,直到剩下一个玩家时游戏结束,这个玩家就是游戏获胜者。
那么问题来了,哪个编号是游戏获胜者呢?
下面通过简单的几行python代码来解决这个问题:

#!/usr/bin/env python 
# Joseph Problem 
def joseph(total, begins, count): 
  queue = range(1, total + 1) 
  death = (begins + count - 2) % len(queue) 
  for times in range(total - 1): 
    print 'out: ', queue[death] 
    del queue[death] 
    death = (death + count -1) % len(queue) 
  print 'survivor: ', queue[0] 

joseph()函数中,参数total即上面提到的N,begins即M,count及K,每次循环报数out一个编号,最后剩下的survivor便是游戏获胜者。

而C++的通常实现方法如下:

#include <iostream>
using namespace std;
void main()
{
 int N=0,C=0;
 cout<<"Please enter the number of people:N=";
 cin>>N;
 cout<<"Please enter:C=";
 cin>>C;
 int i=0,j=0,n=N,s=0;
 int *a=new int [N];
 for (i=0;i<N;i++)
 {
 a[i]=1;
 }

 while(0!=n)
 {
 s+=a[j];
 if(C==s)
 {
  a[j]=0;
  s=0;
  --n;
  if(0!=n)
  {
  cout<<j+1<<"->";
  }
  else
  {
  cout<<j+1<<endl;
  }
 }
 j=(j+1)%N;
 }
 delete []a;
}

这是C++语言常见的机试题目,以下程序实现从控制台输入人数N,C并将剔除出队列的人员编号按顺序输出到控制台上。

相关文章

Python基于csv模块实现读取与写入csv数据的方法

Python基于csv模块实现读取与写入csv数据的方法

本文实例讲述了Python基于csv模块实现读取与写入csv数据的方法。分享给大家供大家参考,具体如下: 通过csv模块可以轻松读取格式为csv的文件,而且csv模块是python内置的...

wx.CheckBox创建复选框控件并响应鼠标点击事件

wx.CheckBox创建复选框控件并响应鼠标点击事件

本文实例为大家分享了wx.CheckBox创建复选框控件并响应鼠标点击事件的具体代码,供大家参考,具体内容如下 执行效果图: 执行代码: #!/usr/bin/env pytho...

Python扩展内置类型详解

除了实现新的种类的对象以外,类有时有用于扩展Python的内置类型的功能。主要有以下两种技术: 通过嵌入扩展类型 下例把一些集合函数变成方法,而且新增了一些基本运算符重载,实现了新的集...

Python用户推荐系统曼哈顿算法实现完整代码

Python用户推荐系统曼哈顿算法实现完整代码

出租车几何或曼哈顿距离(Manhattan Distance)是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ,是种使用在几何度量空间的几何学用语,用以标明两个点在标准坐标系上的绝对轴距总和。...

基于Python实现船舶的MMSI的获取(推荐)

基于Python实现船舶的MMSI的获取(推荐)

目的 工作中遇到一个需求,通过需要通过网站查询船舶名称得到MMSI码,网站来自船讯网。 分析请求 根据以往爬虫的经验,打开F12,通过输入船舶名称,观察发送的请求,发现返回数据的网址...