約瑟夫環

題目描述

此題來源于洛谷P1996

核心思路

問題：如何了解j=a[j]呢？

如何了解 a [ j ] = a [ a [ j ] ] a[j]=a[a[j]] a[j]=a[a[j]]呢？

出局圖示如下：

代碼

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int a[N];   //a[i]存放的是目前節點i的下一個節點的位置下标
int b[N];   //出局序列   b[i]這個值表示的是出局那個人的編号
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    //a[1]=2,即目前節點1号它的下一個節點的位置下标是2
    for(int i=1;i<n;i++)    //模拟連結清單
        a[i]=i+1;
    a[n]=1;     //第n個人指向第1人,形成一個環
    int k=1;    //記錄每一個m間隔中此時已經數了多少個人
    int j=n;    //讓j落到最後 這樣當j=a[j]時就可以從1開始了
    for(int i=1;i<=n;i++)   //n個人都出局為止
    {
        //報數,當還沒有報到m時,就繼續
        while(k<m)
        {
            j=a[j];//j移動到下一個節點
            k++;    //報數個數+1
        }
        //退出循環後,說明此時正好報到m,是以此時編号為a[j]的這個人就要出局
        b[i]=a[j];
        //由于數到m的那個節點出局(即目前節點j的下一個節點a[j]出局了),此時讓a[j]=a[a[j]]
        //那麼此時目前節點j的下一個節點就目前節點j的下一個節點的下一個節點
        a[j]=a[a[j]];
        k=1;    //重置k為1
        //printf("%d出局 a[%d]=%d\n",b[i],j,a[j]);
    }
    //輸出這n個人的出局序列
    for(int i=1;i<=n;i++)
        printf("%d ",b[i]);
    return 0;
}
           

題目描述

核心思路

我們可以給每一個人一個編号(索引值)，每個人用字母來代替，下面舉例 n = 8 , m = 3 n=8,m=3 n=8,m=3時，我們定義 f [ n ] [ m ] f[n][m] f[n][m]表示最後剩下的那個人的編号，是以我們隻關系最後剩下來這個人的索引号的變化情況即可。

當某個人出隊後，它的下一個人就成為了隊首，而不再是原來的隊首了。如下圖，當C出隊後，它的下一個人就是D，那麼D就會成為隊首，而不是讓A成為隊首。模拟發現，最終G是勝利者。

從8個人開始，每次殺掉一個人，去掉被殺的人，然後把殺掉那個人之後的第一個人作為開頭重新編号

• 第一次C被殺掉，人數變成7，D作為開頭，（最終活下來的G的編号從6變成3）
• 第二次F被殺掉，人數變成6，G作為開頭，（最終活下來的G的編号從3變成0）
• 第三次A被殺掉，人數變成5，B作為開頭，（最終活下來的G的編号從0變成3）
• 第四次E被殺掉，人數變成4，G作為開頭，（最終活下來的G的編号從3變成0）
• 第五次B被殺掉，人數變成3，D作為開頭，（最終活下來的G的編号從0變成1）
• 第六次H被殺掉，人數變成2，D作為開頭，（最終活下來的G的編号從1變成1）
• 第七次D被殺掉，人數變成1，G作為開頭，（最終活下來的G的編号從1變成0）

由此可見，當隻剩一個人時，這個人就是勝利者，他的編号肯定為0。

問題：如何由最終的勝利者的編号反推呢？

現在我們知道了G的索引号的變化過程，那麼我們反推一下，從 n = 7 n=7 n=7到 n = 8 n=8 n=8的過程，怎樣才能将 n = 7 n=7 n=7的排列順序變為 n = 8 n=8 n=8時的排列順序呢？我們【先把被殺掉的C補充回來，然後右移m個人，發現溢出了，再把溢出的補充在最前面】，經過這般操作後，就可以恢複到 n = 8 n=8 n=8時的排列順序了。當删除某個節點時，這個節點後面的全部節點都向前平移 m m m個距離；當恢複某個節點時，那麼全部節點都向後移動 m m m個機關，然後如果某些節點出界了，那麼就然這些節點回到前面(設目前這輪有 x x x個人，那麼如果越界的話，就讓那些越界的人 % x \%x %x就可以回到前面了)。

是以，我們可以推導出遞歸關系式 f ( 8 , 3 ) = [ f ( 7 , 3 ) + 3 ] % 8 f(8,3)=[f(7,3)+3]\%8 f(8,3)=[f(7,3)+3]%8，推廣到一般情況就是 f ( n , m ) = [ f ( n − 1 , m ) + m ] % n f(n,m)=[f(n-1,m)+m]\%n f(n,m)=[f(n−1,m)+m]%n。

遞推公式：

再把

n=1

這個最初的情況加上，就得到遞推公式：

f ( n , m ) = { 0 n = 1 [ f ( n − 1 , m ) + m ] % n n > 1 f(n,m)=\begin {cases} 0 & n=1 \\ [f(n-1,m)+m]\%n & n>1 \end{cases} f(n,m)={0[f(n−1,m)+m]%n​n=1n>1​

代碼

class Solution {
public:
    int lastRemaining(int n, int m) {
        int pos = 0; // 最終活下來那個人的初始位置
        //i表示這一輪的人數  一直做到最初有n個人時 最終勝利者的位置
        for(int i = 2; i <= n; i++)
        {
            pos = (pos + m) % i;  // 每次循環右移
        }
        //這題的編号是從0開始,是以直接傳回數組下标pos就是正确的編号
        //如果題目的編号是從1開始,但是由于我們的數組下标是從0開始,那麼此時輸出答案時就要數組下标pos+1,才能轉成編号
        return pos;
    }
};