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

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

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

  查看匯總:2015軟件水平考試程序員精選題匯總

  最長(zhǎng)公共子串

  題目:如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中,則字符串一稱(chēng)之為字符串二的子串。注意,并不要求子串(字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫(xiě)一個(gè)函數(shù),輸入兩個(gè)字符串,求它們的最長(zhǎng)公共子串,并打印出最長(zhǎng)公共子串。

  例如:輸入兩個(gè)字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串,則輸出它們的長(zhǎng)度4,并打印任意一個(gè)子串。

  分析:求最長(zhǎng)公共子串(Longest Common Subsequence, LCS)是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題,因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。

  完整介紹動(dòng)態(tài)規(guī)劃將需要很長(zhǎng)的篇幅,因此我不打算在此全面討論動(dòng)態(tài)規(guī)劃相關(guān)的概念,只集中對(duì)LCS直接相關(guān)內(nèi)容作討論。如果對(duì)動(dòng)態(tài)規(guī)劃不是很熟悉,請(qǐng)參考相關(guān)算法書(shū)比如算法討論。

  先介紹LCS問(wèn)題的性質(zhì):記Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個(gè)字符串,而Zk={z0,z1,…zk-1}是它們的LCS,則:

  1. 如果xm-1=yn-1,那么zk-1=xm-1=yn-1,并且Zk-1是Xm-1和Yn-1的LCS;

  2. 如果xm-1≠yn-1,那么當(dāng)zk-1≠xm-1時(shí)Z是Xm-1和Y的LCS;

  3. 如果xm-1≠yn-1,那么當(dāng)zk-1≠yn-1時(shí)Z是Yn-1和X的LCS;

  下面簡(jiǎn)單證明一下這些性質(zhì):

  1. 如果zk-1≠xm-1,那么我們可以把xm-1(yn-1)加到Z中得到Z’,這樣就得到X和Y的一個(gè)長(zhǎng)度為k+1的公共子串Z’。這就與長(zhǎng)度為k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。

  既然zk-1=xm-1=yn-1,那如果我們刪除zk-1(xm-1、yn-1)得到的Zk-1,Xm-1和Yn-1,顯然Zk-1是Xm-1和Yn-1的一個(gè)公共子串,現(xiàn)在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設(shè)有Xm-1和Yn-1有一個(gè)長(zhǎng)度超過(guò)k-1的公共子串W,那么我們把加到W中得到W’,那W’就是X和Y的公共子串,并且長(zhǎng)度超過(guò)k,這就和已知條件相矛盾了。

  2. 還是用反證法證明。假設(shè)Z不是Xm-1和Y的LCS,則存在一個(gè)長(zhǎng)度超過(guò)k的W是Xm-1和Y的LCS,那W肯定也X和Y的公共子串,而已知條件中X和Y的公共子串的最大長(zhǎng)度為k。矛盾。

  3. 證明同2。

  有了上面的性質(zhì),我們可以得出如下的思路:求兩字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS,如果xm-1=yn-1,那么只需求得Xm-1和Yn-1的LCS,并在其后添加xm-1(yn-1)即可;如果xm-1≠yn-1,我們分別求得Xm-1和Y的LCS和Yn-1和X的LCS,并且這兩個(gè)LCS中較長(zhǎng)的一個(gè)為X和Y的LCS。

  如果我們記字符串Xi和Yj的LCS的長(zhǎng)度為c[i,j],我們可以遞歸地求c[i,j]:

  / 0 if i<0 or j<0

  c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj

  \ max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj

  上面的公式用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項(xiàng)(本面試題系列第16題)的分析中我們知道直接遞歸會(huì)有很多重復(fù)計(jì)算,我們用從底向上循環(huán)求解的思路效率更高。

  為了能夠采用循環(huán)求解的思路,我們用一個(gè)矩陣(參考代碼中的LCS_length)保存下來(lái)當(dāng)前已經(jīng)計(jì)算好了的c[i,j],當(dāng)后面的計(jì)算需要這些數(shù)據(jù)時(shí)就可以直接從矩陣讀取。另外,求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個(gè)方向計(jì)算得到,相當(dāng)于在矩陣LCS_length中是從c[i-1,j-1],c[i,j-1]或者c[i-1,j]的某一個(gè)各自移動(dòng)到c[i,j],因此在矩陣中有三種不同的移動(dòng)方向:向左、向上和向左上方,其中只有向左上方移動(dòng)時(shí)才表明找到LCS中的一個(gè)字符。于是我們需要用另外一個(gè)矩陣(參考代碼中的LCS_direction)保存移動(dòng)的方向。

  參考代碼如下:

  #include "string.h"

  // directions of LCS generation

  enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};

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

  // Get the length of two strings' LCSs, and print one of the LCSs

  // Input: pStr1 - the first string

  // pStr2 - the second string

  // Output: the length of two strings' LCSs

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

  int LCS(char* pStr1, char* pStr2)

  {

  if(!pStr1 || !pStr2)

  return 0;

  size_t length1 = strlen(pStr1);

  size_t length2 = strlen(pStr2);

  if(!length1 || !length2)

  return 0;

  size_t i, j;

  // initiate the length matrix

  int **LCS_length;

  LCS_length = (int**)(new int[length1]);

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

  LCS_length[i] = (int*)new int[length2];

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

  for(j = 0; j < length2; ++ j)

  LCS_length[i][j] = 0;

  // initiate the direction matrix

  int **LCS_direction;

  LCS_direction = (int**)(new int[length1]);

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

  LCS_direction[i] = (int*)new int[length2];

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

  for(j = 0; j < length2; ++ j)

  LCS_direction[i][j] = kInit;

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

  {

  for(j = 0; j < length2; ++ j)

  {

  if(i == 0 || j == 0)

  {

  if(pStr1[i] == pStr2[j])

  {

  LCS_length[i][j] = 1;

  LCS_direction[i][j] = kLeftUp;

  }

  else

  LCS_length[i][j] = 0;

  }

  相關(guān)推薦:

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

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

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

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