首頁 - 網(wǎng)校 - 萬題庫 - 直播 - 雄鷹網(wǎng)校 - 團(tuán)購 - 書城 - 模考 - 學(xué)習(xí)通 - 導(dǎo)航 -
首頁網(wǎng)校萬題庫直播雄鷹網(wǎng)校團(tuán)購書城?論壇實用文檔作文大全寶寶起名
2015中考
法律碩士
2015高考
MBA考試
2015考研
MPA考試
在職研
中科院
考研培訓(xùn)
專升本
自學(xué)考試 成人高考
四 六 級
GRE考試
攻碩英語
零起點日語
職稱英語
口譯筆譯
申碩英語
零起點韓語
商務(wù)英語
日語等級
GMAT考試
公共英語
職稱日語
新概念英語
專四專八
博思考試
零起點英語
托?荚
托業(yè)考試
零起點法語
雅思考試
成人英語三級
零起點德語
等級考試
華為認(rèn)證
水平考試
Java認(rèn)證
職稱計算機(jī) 微軟認(rèn)證 思科認(rèn)證 Oracle認(rèn)證 Linux認(rèn)證
公 務(wù) 員
導(dǎo)游考試
物 流 師
出版資格
單 證 員
報 關(guān) 員
外 銷 員
價格鑒證
網(wǎng)絡(luò)編輯
駕 駛 員
報檢員
法律顧問
管理咨詢
企業(yè)培訓(xùn)
社會工作者
銀行從業(yè)
教師資格
營養(yǎng)師
保險從業(yè)
普 通 話
證券從業(yè)
跟 單 員
秘書資格
電子商務(wù)
期貨考試
國際商務(wù)
心理咨詢
營 銷 師
司法考試
國際貨運(yùn)代理人
人力資源管理師
廣告師職業(yè)水平
衛(wèi)生資格 執(zhí)業(yè)醫(yī)師 執(zhí)業(yè)藥師 執(zhí)業(yè)護(hù)士
會計從業(yè)資格
基金從業(yè)資格
統(tǒng)計從業(yè)資格
經(jīng)濟(jì)師
精算師
統(tǒng)計師
會計職稱
法律顧問
ACCA考試
初級會計職稱
資產(chǎn)評估師
高級經(jīng)濟(jì)師
注冊會計師
高級會計師
美國注冊會計師
審計師考試
國際內(nèi)審師
注冊稅務(wù)師
理財規(guī)劃師
一級建造師
安全工程師
設(shè)備監(jiān)理師
公路監(jiān)理師
公路造價師
二級建造師
招標(biāo)師考試
物業(yè)管理師
電氣工程師
建筑師考試
造價工程師
注冊測繪師
質(zhì)量工程師
巖土工程師
注冊給排水
造價員考試
注冊計量師
環(huán)保工程師
化工工程師
暖通工程師
咨詢工程師
結(jié)構(gòu)工程師
城市規(guī)劃師
材料員考試
消防工程師
監(jiān)理工程師
房地產(chǎn)估價
土地估價師
安全評價師
房地產(chǎn)經(jīng)紀(jì)人
投資項目管理師
環(huán)境影響評價師
土地登記代理人
寶寶起名
繽紛校園
實用文檔
入黨申請
英語學(xué)習(xí)
思想?yún)R報
作文大全
工作總結(jié)
求職招聘 論文下載 直播課堂
您現(xiàn)在的位置: 考試吧 > 軟件水平考試 > 復(fù)習(xí)資料 > 程序員 > 正文

2015年軟件水平考試程序員精選題(5)

考試吧整理“2015年軟件水平考試程序員精選題(5)”供考生參考,更多軟件水平考試資訊和備考資料請關(guān)注考試吧軟件水平考試網(wǎng)。

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

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

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

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

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

  接下來我們試著從數(shù)學(xué)上分析出一些規(guī)律。首先定義最初的n個數(shù)字(0,1,…,n-1)中最后剩下的數(shù)字是關(guān)于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。相當(dāng)于在剩下的序列中,k+1排到最前面,從而形成序列k+1,…,n-1,0,…k-1。該序列最后剩下的數(shù)字也應(yīng)該是關(guān)于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作一個映射,映射的結(jié)果是形成一個從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。對應(yīng)的逆映射是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)過上面復(fù)雜的分析,我們終于找到一個遞歸的公式。要得到n個數(shù)字的序列的最后剩下的數(shù)字,只需要得到n-1個數(shù)字的序列的最后剩下的數(shù)字,并可以依此類推。當(dāng)n=1時,也就是序列中開始只有一個數(shù)字0,那么很顯然最后剩下的數(shù)字就是0。我們把這種關(guān)系表示為:

  0 n=1

  f(n,m)={

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

  盡管得到這個公式的分析過程非常復(fù)雜,但它用遞歸或者循環(huán)都很容易實現(xiàn)。最重要的是,這是一種時間復(fù)雜度為O(n),空間復(fù)雜度為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;

  }

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

上一頁  1 2 

  相關(guān)推薦:

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

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

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

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系800@exam8.com,我們將會及時處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請注明出處。
Copyright © 2004- 考試吧軟件水平考試網(wǎng) All Rights Reserved 
中國科學(xué)院研究生院權(quán)威支持(北京)
在線模擬試題
考證通關(guān)殺器
考試最新資訊
學(xué)
一次通關(guān)技巧