題目描述

每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數m,讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0…m-1報數….這樣下去….直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)

經典解法：

我們使用一個數組來模擬這些孩子，當孩子還沒有被挑選到，就設為0，如果孩子被挑出，就設為1，如果已經遍歷到了結尾，就移到數組的開頭，直到最后剩下一個孩子。

創新解法：

在這n個數字中，第一個被刪除的數字是(m - 1)% n，為了簡單起見，我們將其記作k，刪除k之后剩下的n-1個數字為0， 1， 2， 3， … ， k -1， k + 1， … ， n - 1, 并且下一次刪除從k +１開始計數，但顯然該數列最后剩下的數字也是應該關于ｎ和ｍ的函數，我們將其記作f’(n - 1, m)，最初序列剩下的最后一個數字一定是刪除一個數字之后的序列的最后剩下的數字，即f(n, m)= f’(n - 1, m)。 剩下的一個數組序列可以產生這樣的映射: k + 1 -> 0 k + 2 -> 1 … n - 1 -> n - k - 2 0 -> n - k - 1 1 -> n - k … k - 1 -> n - 2 映射定義為p，則p(x) = (x - k - 1) % n,逆映射p^(-1)(x）= （x + k + 1）%n， 映射之后的序列和之前的序列有同樣的形式，所以可以記作f(n - 1, m )，根據我們的映射，映射之前的序列中最后剩下的數字f’(n - 1, m) = p ^(-1)[f(n - 1, m)] = [f(n - 1, m) + k + 1] % n = [f(n - 1, m ) + m] % n = f(n, m）.

代碼如下：