首页 > 试题广场 >

幸存者游戏

[编程题]幸存者游戏
  • 热度指数:168 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有n个同学围成一圈,其id依次为1,2,3...n(n号挨着1号)。现在从1号开始报数,第一回合报到m的人就出局,第二回合从出局的下一个开始报数,报到m^2的同学出局。
以此类推直到最后一个回合报到m^(n-1)的人出局,直到剩下最后一个同学。输出这个同学的编号。n<=15,m<=5


输入描述:
每一行第一个数字代表n,第二个数字代表m


输出描述:
输出最后剩下同学的编号
示例1

输入

5 2

输出

5
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
       if (n<1 || m<1) return -1;
    int circle=pow(m,n-1);
    int f=0;
    for(int i=2;i<=n;++i)
    {
        f=(f+circle)%i;
        circle/=m; // 调整为当前的 m,因为 m 有做关于 n 的次方
    }
    cout<<f+1<<endl;
    return 0;
}

发表于 2019-06-16 10:19:11 回复(0)
n, m = [int(x) for x in input().split()]
ans = 1
for i in range(2, n+1):
    ans = (ans + m**(n-i+1)) % i
    if ans == 0:
        ans = i
print(ans)


编辑于 2019-09-11 00:03:39 回复(0)
用PHP语言的array_values()函数
<?php
fscanf(STDIN, "%d %d", $n, $m);
$num=array();
$num[0]=0;
for ($i=1;$i<=$n;++$i) $num[$i]=$i;
$i--;
$j=1;
$pre=0;
while ($i>1){
    $j*=$m;
    $outid***re)%$i;
    if ($outidx==0) $outidx=$i;
    $pre=$outidx-1;
    //echo $num[$outidx]."\n";
    unset($num[$outidx]);
    $num=array_values($num);
    //var_dump($num);
    $i--;
}
echo $num[1];
?>

发表于 2019-05-21 17:35:34 回复(0)