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

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

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

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

  -在排序數(shù)組中查找和為給定值的兩個(gè)數(shù)字

  題目:輸入一個(gè)已經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字,在數(shù)組中查找兩個(gè)數(shù),使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字,輸出任意一對(duì)即可。

  例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15,因此輸出4和11。

  分析:如果我們不考慮時(shí)間復(fù)雜度,最簡單想法的莫過去先在數(shù)組中固定一個(gè)數(shù)字,再依次判斷數(shù)組中剩下的n-1個(gè)數(shù)字與它的和是不是等于輸入的數(shù)字。可惜這種思路需要的時(shí)間復(fù)雜度是O(n2)。

  我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個(gè)數(shù)。如果它們的和等于輸入的數(shù)字,那太好了,我們找到了要找的兩個(gè)數(shù)字;如果小于輸入的數(shù)字呢?我們希望兩個(gè)數(shù)字的和再大一點(diǎn)。由于數(shù)組已經(jīng)排好序了,我們是不是可以把較小的數(shù)字的往后面移動(dòng)一個(gè)數(shù)字?因?yàn)榕旁诤竺娴臄?shù)字要大一些,那么兩個(gè)數(shù)字的和也要大一些,就有可能等于輸入的數(shù)字了;同樣,當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字的時(shí)候,我們把較大的數(shù)字往前移動(dòng),因?yàn)榕旁跀?shù)組前面的數(shù)字要小一些,它們的和就有可能等于輸入的數(shù)字了。

  我們把前面的思路整理一下:最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí),把較大的數(shù)字往前移動(dòng);當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí),把較小的數(shù)字往后移動(dòng);當(dāng)相等時(shí),打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。

  問題是這樣的思路是不是正確的呢?這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以自行證明一下。

  參考代碼:    

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

  // Find two numbers with a sum in a sorted array

  // Output: ture is found such two numbers, otherwise false

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

  bool FindTwoNumbersWithSum

  (

  int data[], // a sorted array

  unsigned int length, // the length of the sorted array

  int sum, // the sum

  int& num1, // the first number, output

  int& num2 // the second number, output

  )

  {

  bool found = false;

  if(length < 1)

  return found;

  int ahead = length - 1;

  int behind = 0;

  while(ahead > behind)

  {

  long long curSum = data[ahead] + data[behind];

  // if the sum of two numbers is equal to the input

  // we have found them

  if(curSum == sum)

  {

  num1 = data[behind];

  num2 = data[ahead];

  found = true;

  break;

  }

  // if the sum of two numbers is greater than the input

  // decrease the greater number

  else if(curSum > sum)

  ahead --;

  // if the sum of two numbers is less than the input

  // increase the less number

  else

  behind ++;

  }

  return found;

  }

1 2 3 下一頁

  相關(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 
中國科學(xué)院研究生院權(quán)威支持(北京)
在線模擬試題
考證通關(guān)殺器
考試最新資訊
學(xué)
一次通關(guān)技巧