约瑟夫环与其变形问题

约瑟夫环问题描述:一圈共有N个人,开始报数,报到k的人自杀,然后重新开始报数,问最后自杀的人是谁?

思路:

  1.直接暴力模拟,没什么好说的,简单暴力。但是时间复杂度为O(n*m),太过浪费时间。

  2.动态规划,把问题重新描述一下:N个人(编号0~(N-1)),从0开始报数,报到(k-1)的自杀,剩下的人继续从0开始报数。求最后自杀者的编号。

我们用dp[i]来表示倒数第i轮自杀者的编号,那么最后一轮的自杀者在他说在轮的编号一定为0记作dp[1]=0,为了方便描述这个人记作p。那么在上一轮p的编号则为dp[2],在上一轮中p的前一位报号为(k-1),那么p的报号为k,

那么我们得出:dp[2]=(dp[1]+k)%k。如此下去我们便能的出p在最开始时的编号了。

状态转移方程式为:dp[i]=(dp[i-1]+k)%i,dp[1]=0,i(1->n);

约瑟夫环变形问题描述:一圈共有N个人,开始报数,第i轮报到i的人自杀,然后重新开始报数,问最后自杀的人是谁?

思路:

  和原本的约瑟夫环问题的唯一区别是:k值不在固定。同样的我们将最后一位自杀者叫做p,那么在前一轮(第x轮)中的自杀者所报的号为x-1,第x轮中p的报号为x,如此下去……

得出状态转移方程:dp[i]=(dp[i-1]+n-(i-1))%i; i(1->n)

代码:

void GSP(int n)
{
  jsp[1]=0;
  for(int i=2;i<=n;i++)
  {
    jsp[i]=(jsp[i-1]+(n-(i-1)))%i;
  }
}

原文地址:https://www.cnblogs.com/alan-W/p/6709779.html