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

Amber ·

更新时间:2024-09-21

· 682 次阅读

么是约瑟夫问题？
约瑟夫问题是一个有趣的数学游戏，游戏规则如下：
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并将剔除出队列的人员编号按顺序输出到控制台上。

您可能感兴趣的文章:C++实现二叉树遍历序列的求解方法C++实现第K顺序统计量的求解方法使用C++递归求解跳台阶问题详解次小生成树以及相关的C++求解方法C++ 自定义栈实现迷宫求解C++通过自定义函数求一元二次方程的根c++编写简单的计算器程序简单实现C++复数计算器C/C++经典实例之模拟计算器示例代码C++实现的求解多元一次方程示例

c+ 方法约瑟夫问题 C++ Python

1024 个赞