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

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

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

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

　　這種思路需要一個(gè)有n個(gè)結(jié)點(diǎn)的環(huán)形列表來(lái)模擬這個(gè)刪除的過(guò)程，因此內(nèi)存開(kāi)銷(xiāo)為O(n)。而且這種方法每刪除一個(gè)數(shù)字需要m步運(yùn)算，總共有n個(gè)數(shù)字，因此總的時(shí)間復(fù)雜度是O(mn)。當(dāng)m和n都很大的時(shí)候，這種方法是很慢的。

　　接下來(lái)我們?cè)囍鴱臄?shù)學(xué)上分析出一些規(guī)律。首先定義最初的n個(gè)數(shù)字(0,1,…,n-1)中最后剩下的數(shù)字是關(guān)于n和m的方程為f(n,m)。

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

　　接下來(lái)我們把剩下的的這n-1個(gè)數(shù)字的序列k+1,…,n-1,0,…k-1作一個(gè)映射，映射的結(jié)果是形成一個(gè)從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。對(duì)應(yīng)的逆映射是p-1(x)=(x+k+1)%n。

　　由于映射之后的序列和最初的序列有同樣的形式，都是從0開(kāi)始的連續(xù)序列，因此仍然可以用函數(shù)f來(lái)表示，記為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)過(guò)上面復(fù)雜的分析，我們終于找到一個(gè)遞歸的公式。要得到n個(gè)數(shù)字的序列的最后剩下的數(shù)字，只需要得到n-1個(gè)數(shù)字的序列的最后剩下的數(shù)字，并可以依此類(lèi)推。當(dāng)n=1時(shí)，也就是序列中開(kāi)始只有一個(gè)數(shù)字0，那么很顯然最后剩下的數(shù)字就是0。我們把這種關(guān)系表示為：

　　0 n=1

　　f(n,m)={

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

　　盡管得到這個(gè)公式的分析過(guò)程非常復(fù)雜，但它用遞歸或者循環(huán)都很容易實(shí)現(xiàn)。最重要的是，這是一種時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)的方法，因此無(wú)論在時(shí)間上還是空間上都優(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;

　　}

　　如果對(duì)兩種思路的時(shí)間復(fù)雜度感興趣的讀者可以把n和m的值設(shè)的稍微大一點(diǎn)，比如十萬(wàn)這個(gè)數(shù)量級(jí)的數(shù)字，運(yùn)行的時(shí)候就能明顯感覺(jué)出這兩種思路寫(xiě)出來(lái)的代碼時(shí)間效率大不一樣。

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識(shí)點(diǎn)總結(jié)匯總

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

　　2015軟件水平考試《程序員》知識(shí)點(diǎn)總結(jié)匯總