圓圈中最后剩下的數(shù)字

　　題目：n個數(shù)字(0,1,…,n-1)形成一個圓圈，從數(shù)字0開始，每次從這個圓圈中刪除第m個數(shù)字(第一個為當前數(shù)字本身，第二個為當前數(shù)字的下一個數(shù)字)。當一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。求出在這個圓圈中剩下的最后一個數(shù)字。

　　分析：既然題目有一個數(shù)字圓圈，很自然的想法是我們用一個數(shù)據(jù)結構來模擬這個圓圈。在常用的數(shù)據(jù)結構中，我們很容易想到用環(huán)形列表。我們可以創(chuàng)建一個總共有m個數(shù)字的環(huán)形列表，然后每次從這個列表中刪除第m個元素。

　　在參考代碼中，我們用STL中std::list來模擬這個環(huán)形列表。由于list并不是一個環(huán)形的結構，因此每次跌代器掃描到列表末尾的時候，要記得把跌代器移到列表的頭部。這樣就是按照一個圓圈的順序來遍歷這個列表了。

　　這種思路需要一個有n個結點的環(huán)形列表來模擬這個刪除的過程，因此內存開銷為O(n)。而且這種方法每刪除一個數(shù)字需要m步運算，總共有n個數(shù)字，因此總的時間復雜度是O(mn)。當m和n都很大的時候，這種方法是很慢的。

　　接下來我們試著從數(shù)學上分析出一些規(guī)律。首先定義最初的n個數(shù)字(0,1,…,n-1)中最后剩下的數(shù)字是關于n和m的方程為f(n,m)。

　　在這n個數(shù)字中，第一個被刪除的數(shù)字是m%n-1，為簡單起見記為k。那么刪除k之后的剩下n-1的數(shù)字為0,1,…,k-1,k+1,…,n-1，并且下一個開始計數(shù)的數(shù)字是k+1。相當于在剩下的序列中，k+1排到最前面，從而形成序列k+1,…,n-1,0,…k-1。該序列最后剩下的數(shù)字也應該是關于n和m的函數(shù)。由于這個序列的規(guī)律和前面最初的序列不一樣(最初的序列是從0開始的連續(xù)序列)，因此該函數(shù)不同于前面函數(shù)，記為f’(n-1,m)。最初序列最后剩下的數(shù)字f(n,m)一定是剩下序列的最后剩下數(shù)字f’(n-1,m)，所以f(n,m)=f’(n-1,m)。

　　接下來我們把剩下的的這n-1個數(shù)字的序列k+1,…,n-1,0,…k-1作一個映射，映射的結果是形成一個從0到n-2的序列：

　　k+1 -> 0

　　k+2 -> 1

　　…

　　n-1 -> n-k-2

　　0 -> n-k-1

　　…

　　k-1 -> n-2

　　把映射定義為p，則p(x)= (x-k-1)%n，即如果映射前的數(shù)字是x，則映射后的數(shù)字是(x-k-1)%n。對應的逆映射是p-1(x)=(x+k+1)%n。

　　由于映射之后的序列和最初的序列有同樣的形式，都是從0開始的連續(xù)序列，因此仍然可以用函數(shù)f來表示，記為f(n-1,m)。根據(jù)我們的映射規(guī)則，映射之前的序列最后剩下的數(shù)字f’(n-1,m)= p-1 [f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=m%n-1代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。

　　經(jīng)過上面復雜的分析，我們終于找到一個遞歸的公式。要得到n個數(shù)字的序列的最后剩下的數(shù)字，只需要得到n-1個數(shù)字的序列的最后剩下的數(shù)字，并可以依此類推。當n=1時，也就是序列中開始只有一個數(shù)字0，那么很顯然最后剩下的數(shù)字就是0。我們把這種關系表示為：

　　0 n=1

　　f(n,m)={

　　[f(n-1,m)+m]%n n>1

　　盡管得到這個公式的分析過程非常復雜，但它用遞歸或者循環(huán)都很容易實現(xiàn)。最重要的是，這是一種時間復雜度為O(n)，空間復雜度為O(1)的方法，因此無論在時間上還是空間上都優(yōu)于前面的思路。

　　思路一的參考代碼：

　　///////////////////////////////////////////////////////////////////////

　　// n integers (0, 1, ... n - 1) form a circle. Remove the mth from

　　// the circle at every time. Find the last number remaining

　　// Input: n - the number of integers in the circle initially

　　// m - remove the mth number at every time

　　// Output: the last number remaining when the input is valid,

　　// otherwise -1

　　///////////////////////////////////////////////////////////////////////

　　int LastRemaining_Solution1(unsigned int n, unsigned int m)

　　{

　　// invalid input

　　if(n < 1 || m < 1)

　　return -1;

　　unsigned int i = 0;

　　// initiate a list with n integers (0, 1, ... n - 1)

　　list integers;

　　for(i = 0; i < n; ++ i)

　　integers.push_back(i);

　　list::iterator curinteger = integers.begin();

　　while(integers.size() > 1)

　　{

　　// find the mth integer. Note that std::list is not a circle

　　// so we should handle it manually

　　for(int i = 1; i < m; ++ i)

　　{

　　curinteger ++;

　　if(curinteger == integers.end())

　　curinteger = integers.begin();

　　}

　　// remove the mth integer. Note that std::list is not a circle

　　// so we should handle it manually

　　list::iterator nextinteger = ++ curinteger;

　　if(nextinteger == integers.end())

　　nextinteger = integers.begin();

　　-- curinteger;

　　integers.erase(curinteger);

　　curinteger = nextinteger;

　　}

　　return *(curinteger);

　　}

　　思路二的參考代碼：

　　///////////////////////////////////////////////////////////////////////

　　// n integers (0, 1, ... n - 1) form a circle. Remove the mth from

　　// the circle at every time. Find the last number remaining

　　// Input: n - the number of integers in the circle initially

　　// m - remove the mth number at every time

　　// Output: the last number remaining when the input is valid,

　　// otherwise -1

　　///////////////////////////////////////////////////////////////////////

　　int LastRemaining_Solution2(int n, unsigned int m)

　　{

　　// invalid input

　　if(n <= 0 || m < 0)

　　return -1;

　　// if there are only one integer in the circle initially,

　　// of course the last remaining one is 0

　　int lastinteger = 0;

　　// find the last remaining one in the circle with n integers

　　for (int i = 2; i <= n; i ++)

　　lastinteger = (lastinteger + m) % i;

　　return lastinteger;

　　}

　　如果對兩種思路的時間復雜度感興趣的讀者可以把n和m的值設的稍微大一點，比如十萬這個數(shù)量級的數(shù)字，運行的時候就能明顯感覺出這兩種思路寫出來的代碼時間效率大不一樣。

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

　　2015年軟件水平考試《程序員》提高練習題匯總

　　2015軟件水平考試《程序員》知識點總結匯總