東北師范大學(xué)研究生課程—算法與程序設(shè)計

1、算法與程序設(shè)計碩士學(xué)位課程教材系列算法與程序設(shè)計Algorithm and Program Design目錄目錄02課程信息03專題一 信息學(xué)競賽簡介與算法基礎(chǔ)06專題二 數(shù)制轉(zhuǎn)換與高精度計算22專題三 字符串基礎(chǔ)41專題四 查找算法53專題五 排序算法68專題六 遞歸算法89專題七 貪心算法117專題八 圖論130專題九 動態(tài)規(guī)劃145專題十 模擬算法167閱讀文獻(xiàn)196課程信息【課程性質(zhì)】專業(yè)必修課【課程學(xué)分】2學(xué)分?！窘虒W(xué)目標(biāo)】這是為教育碩士開設(shè)的一門專業(yè)課程，其主要目標(biāo)旨在使學(xué)生進(jìn)一步體驗算法思想，了解算法和程序設(shè)計在解決問題過程中的地位和作用；能從簡單問題出發(fā)，設(shè)計解決問題的算法，并

2、能初步使用一種程序設(shè)計語言編制程序，實現(xiàn)算法解決問題，能夠勝任中小學(xué)計算機(jī)競賽的培訓(xùn)。具體的教學(xué)目標(biāo)包括：1. 知識與技能（1）理解算法、程序、語言等內(nèi)涵及其相互關(guān)系。（2）了解順序、選擇、循環(huán)三種基本結(jié)構(gòu)及其重要作用。（3）掌握計算機(jī)程序的基本概念，能解釋計算機(jī)程序執(zhí)行的基本過程。（4）了解程序設(shè)計語言、編輯程序、編譯程序、連接程序以及程序開發(fā)環(huán)境等基本知識。（5）了解面向?qū)ο笈c軟件工程的基本思想。 2. 過程與方法（1）結(jié)合實例，經(jīng)歷分析問題、確定算法、編程求解等用計算機(jī)解決問題的基本過程，認(rèn)識算法和程序設(shè)計在其中的地位和作用。（2）掌握用自然語言、流程圖或偽代碼等方法描述算法的過程。（3

3、）通過觀看演示、模仿、探究、實踐等活動，在使用計算機(jī)解決實際問題的過程中，分析其特點(diǎn)，了解人與計算機(jī)解決問題的異同。 3. 情感態(tài)度與價值觀（1）培養(yǎng)對算法與程序設(shè)計的興趣。（2）感受計算機(jī)解決問題的優(yōu)勢。（3）逐步養(yǎng)成運(yùn)用計算機(jī)分析問題、解決問題的習(xí)慣?！窘虒W(xué)方式】采用網(wǎng)絡(luò)授課和假期集中授課相結(jié)合的方式。由學(xué)生在網(wǎng)絡(luò)平臺進(jìn)行自我學(xué)習(xí)，PPT按教學(xué)內(nèi)容制作，便于同學(xué)形象理解。教學(xué)視頻由老師錄制，與上課同步，使網(wǎng)絡(luò)授課的學(xué)生也能得到在課堂上的效果。以上資源在網(wǎng)上共享，便于同學(xué)下載學(xué)習(xí)。程序設(shè)計例題以online judge上的題目為主，閱讀文獻(xiàn)以國家集訓(xùn)隊論文為主?！究己朔绞健勘菊n程采用多種考核

4、評價方式，包括自我評價、同伴評價、教師評定。側(cè)重于對學(xué)生的過程評價。課程一共分為10個專題，每個專題一個算法，每個算法除了理論知識外，還有相應(yīng)的實例。并且每個專題都留有相應(yīng)的練習(xí)題，需要學(xué)生在課后之余訓(xùn)練，而且都是通過在線評判系統(tǒng)提交。在線評判系統(tǒng)及時反饋評測結(jié)果，這樣達(dá)到學(xué)生進(jìn)行自我評價。每個專題的練習(xí)結(jié)果都將作為最終評價的一部分，這樣可以更好地突出學(xué)生整個的學(xué)習(xí)狀況和程度。在寒暑期集中學(xué)習(xí)階段，結(jié)合分組討論，進(jìn)行同伴評價。最終的評價將由主講老師結(jié)合這3個方面給出每個學(xué)生的成績。【學(xué)習(xí)建議】算法與程序設(shè)計是一門實踐性非常強(qiáng)的課程，因此要求學(xué)習(xí)者多動手，多上機(jī)，為此我們給出以下學(xué)習(xí)建議：（1）

5、算法與數(shù)據(jù)結(jié)構(gòu)相輔相成，密不可分程序設(shè)計不僅僅需要算法，還需要相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來支撐。因此要想學(xué)好程序設(shè)計，除了要學(xué)會和掌握相應(yīng)的算法，還需要掌握數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。因此建議學(xué)習(xí)者在學(xué)習(xí)算法與程序設(shè)計課程之前，復(fù)習(xí)已經(jīng)學(xué)過的數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，重點(diǎn)掌握像線性表、堆棧、隊列、串、樹、圖等常見的數(shù)據(jù)結(jié)構(gòu)。（2）算法的描述方法、算法的設(shè)計、算法的分析優(yōu)化，是學(xué)習(xí)和掌握各種算法的基礎(chǔ)建議學(xué)習(xí)者在學(xué)習(xí)這門課程之前學(xué)習(xí)有關(guān)算法設(shè)計和分析方面的理論知識。（3）在“做中學(xué)”和“學(xué)中做”調(diào)查表明,我們所掌握的知識，有10是通過“閱讀”得來的，有15是“聽”來的，有80是親身經(jīng)歷獲得來的。對于算法和程序設(shè)計來說，眾多的算法

6、是前輩們通過各種途徑總結(jié)出來的，是非常經(jīng)典的。要想學(xué)會和掌握它們，僅僅通過閱讀和背誦是不行的，必須多上機(jī)練習(xí)，掌握其實際的應(yīng)用，這樣才能達(dá)到學(xué)以致用。（4）各個專題的重點(diǎn)內(nèi)容第一專題：信息學(xué)競賽簡介與算法基礎(chǔ)重點(diǎn)掌握信息學(xué)競賽的整體狀況和NOI競賽的比賽規(guī)則、試題類型、知識范疇，以及算法基礎(chǔ)知識。第二專題：數(shù)制轉(zhuǎn)換與高精度計算重點(diǎn)掌握各種數(shù)制及其它們之間轉(zhuǎn)換以及高精度數(shù)的各種運(yùn)算。第三專題：字符串處理重點(diǎn)掌握字符串的比較、查找等處理。第四專題：排序算法重點(diǎn)掌握各種常見排序算法及其使用，如冒泡排序、插入排序、快速排序。第五專題：搜索算法重點(diǎn)掌握二分查找法。第六專題：遞歸算法重點(diǎn)掌握遞歸算法的設(shè)計

7、，注意遞歸出口。第七專題：貪心算法重點(diǎn)掌握貪心算法的基本思想以及貪心算法解題的基本要素。第八專題：圖論重點(diǎn)掌握圖的搜索算法，如深度優(yōu)先搜索和廣度優(yōu)先搜索。第九專題：動態(tài)規(guī)劃重點(diǎn)掌握動態(tài)規(guī)劃求解時如何尋找“子問題”，如何定義“狀態(tài)”，如何給出“狀態(tài)轉(zhuǎn)移方程”。第十專題：模擬重點(diǎn)掌握用計算機(jī)模擬解決現(xiàn)實中難以用公式解決的問題。專題一 信息學(xué)競賽簡介與算法基礎(chǔ)【主要內(nèi)容】1.信息學(xué)奧林匹克相關(guān)知識：介紹信息學(xué)奧林匹克競賽的基本常識、比賽規(guī)則、題目范圍等。2.算法與程序設(shè)計的基礎(chǔ)：介紹算法的基本常識以及常見的算法介紹等。【學(xué)習(xí)重點(diǎn)】信息學(xué)奧林匹克競賽的基本常識、算法的基本介紹，包括信息學(xué)奧林匹克競賽的

8、基本常識、比賽規(guī)則、題目范圍以及算法的基本常識以及常見的算法介紹等。一、信息學(xué)競賽簡介（一）信息學(xué)競賽概述信息學(xué)奧林匹克競賽是一項旨在推動計算機(jī)普及的學(xué)科競賽活動，重在培養(yǎng)學(xué)生能力，使得有潛質(zhì)有才華的學(xué)生在競賽活動中鍛煉和發(fā)展。近年來，信息學(xué)競賽活動組織逐步趨于規(guī)范和完善，基本上形成了“地級市?。ㄖ陛犑校┤珖鴩H”四級相互接軌的競賽網(wǎng)絡(luò)。信息學(xué)競賽系列活動主要包括以下六個方面：（1）各省市組織的與NOI有關(guān)的培訓(xùn)和競賽活動；（2）全國青少年信息學(xué)奧林匹克聯(lián)賽（National Olympiad in Informatics in Provinces，簡稱NOIP）；（3）全國青少年信息學(xué)奧林匹

9、克競賽（National Olympiad in Informatics，簡稱NOI），同時舉行夏令營和全國青少年信息學(xué)奧林匹克團(tuán)體對抗賽；（4）全國青少年信息學(xué)奧林匹克競賽冬令營；（5）亞洲和太平洋地區(qū)信息學(xué)奧林匹克競賽（Asia and Pacific Informatics Olympiad，簡稱APIO）；（6）國際信息學(xué)奧林匹克中國隊選拔賽，全國信息學(xué)奧林匹克精英賽，參加國際信息學(xué)奧林匹克（International Olympiad in Informatics，簡稱IOI）。其大致順序為：先舉辦全國信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽（NOIP），聯(lián)賽分高中組，初中組進(jìn)行，以普及為主

10、。在分區(qū)聯(lián)賽的基礎(chǔ)上，各省市組成自己的代表隊，參加第二個層次的比賽，即全國青少年信息學(xué)奧林匹克競賽（NOI）。第三個層次是從NOI中選拔優(yōu)秀選手（20人），經(jīng)過培訓(xùn)，考試選拔，組成國家隊（一般4-5人），參加國際信息學(xué)奧林匹克競賽，即IOI，這是國際性的最高水平的競賽。（二）各類比賽簡介1全國青少年信息學(xué)奧林匹克競賽（NOI）1984年鄧小平指出：“計算機(jī)的普及要從娃娃做起。”教育部和中國科協(xié)委托中國計算機(jī)學(xué)會（CCF）舉辦了全國青少年計算機(jī)程序設(shè)計競賽。從此每年舉辦一次全國青少年計算機(jī)程序設(shè)計競賽。該競賽是經(jīng)國家教委批準(zhǔn)，中國科協(xié)具體領(lǐng)導(dǎo)，由中國計算機(jī)學(xué)會主辦的，是國內(nèi)包括港澳在內(nèi)的省級代表

11、隊最高水平的大賽。由各省市組織參賽，經(jīng)各省NOIP選拔產(chǎn)生5名選手（其中一名是女選手），每年由中國計算機(jī)學(xué)會在計算機(jī)普及較好的城市舉辦一次比賽。獎項有個人一、二、三等獎，女選手第一、二、三名，各省隊團(tuán)體總分名次排隊。而自從1989年我國參加第一屆國際信息學(xué)奧林匹克（簡稱IOI）以來，全國青少年計算機(jī)程序設(shè)計競賽也更名為全國青少年信息學(xué)（計算機(jī)）奧林匹克（NOI）。NOI期間，舉辦同步夏令營和NOI網(wǎng)上同步賽，給那些程序設(shè)計愛好者和高手提供機(jī)會。為增加競賽的競爭性、對抗性和趣味性以及可視化，NOI組織進(jìn)行團(tuán)體對抗賽，團(tuán)體對抗賽實質(zhì)上是程序?qū)官?，其成績納入總分計算。2全國青少年信息學(xué)奧林匹克競賽

12、冬令營全國青少年信息學(xué)奧林匹克競賽冬令營（簡稱冬令營）自1995年起。每年在寒假期間開展為期8天的培訓(xùn)活動。冬令營包括授課、 講座、討論、測試等。參加冬令營的營員分正式營員和非正式營員。獲得NOI前20名的選手和指導(dǎo)教師為正式營員，非正式營員限量自愿報名參加。在冬令營授課的是著名大學(xué)的資深教授及已獲得國際金牌學(xué)生的指導(dǎo)教師。IOI的選手是從獲NOI前20名選手中選拔出來的，獲得前4名的優(yōu)勝者代表中國參加國際競賽。選拔科目包括：NOI成績、冬令營成績、論文和答辯、平時作業(yè)、選拔賽成績、口試。上述項目加權(quán)產(chǎn)生最后成績。官方網(wǎng)站：3全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）全國青少年信息學(xué)奧林匹克聯(lián)賽

13、（NOIP）是由中國計算機(jī)學(xué)會主辦的以省為賽區(qū)單位組織實施的全國性競賽，是全國青少年信息學(xué)奧林匹克競賽（NOI）系列活動的重要組成部分。在舉辦1995年NOI活動之前，為了擴(kuò)大普及面，并考慮到多數(shù)省、直轄市、自治區(qū)已經(jīng)開展了多年省級競賽，舉辦了首屆全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽。考慮到不同年級學(xué)生的知識層次，也為了鼓勵更多的學(xué)生積極參與，競賽設(shè)提高組、普及組，并分初、復(fù)賽進(jìn)行，這樣可以形成一個梯隊，確保每年的競賽活動有比較廣泛扎實的基礎(chǔ)。4亞洲和太平洋地區(qū)信息學(xué)奧林匹克競賽亞洲和太平洋地區(qū)信息學(xué)奧賽（APIO）于2007年創(chuàng)建，該競賽為區(qū)域性的網(wǎng)上準(zhǔn)同步賽，是亞洲和太平洋地區(qū)每年一

14、次的國際性賽事，旨在給青少年提供更多的賽事機(jī)會，推動亞太地區(qū)的信息學(xué)奧林匹克的發(fā)展。APIO每年5月舉行，由不同的國家輪流主辦。每個參賽團(tuán)參賽選手上限為100名，其中成績排在前6名的選手作為代表該參賽團(tuán)的正式選手統(tǒng)計成績。APIO中國賽區(qū)由中國計算機(jī)學(xué)會組織參賽，獲獎比例將參照IOI。5國際信息學(xué)奧林匹克競賽1987年，保加利亞的sendov教授在聯(lián)合國教科文組織（UNESCO）第24次全體會議上提出了舉辦IOI的倡議。從此IOI成為五項國際學(xué)科奧林匹克競賽之一，是由聯(lián)合國教科文組織于1988年創(chuàng)建。首屆競賽于1989年5月在保加利亞的布拉維茨舉行，有13個國家的46名選手參賽。我國只有信息學(xué)

15、是首屆就獲得參賽資格的，而且首屆競賽的試題原型是由中國提供的。IOI的宗旨是：宣傳信息學(xué)這一新興學(xué)科；激發(fā)學(xué)生對計算機(jī)科學(xué)和信息技術(shù)的興趣；給學(xué)校這一類課程增加動力和新思路；通過競賽形式對有才華的青少年給予激勵，促使其能力得以發(fā)展；特別是使世界各國有才華的中學(xué)生匯聚一堂，進(jìn)行科學(xué)文化上的交流，并學(xué)習(xí)主辦國優(yōu)秀的文化。中國參賽隊由中國計算機(jī)學(xué)會組織，代表中國參加國際每年一次的IOI。中國是IOI創(chuàng)始國之一。出國參賽得到中國科協(xié)和國家自然科學(xué)基金委的資助。自1989年開始，我國在NOI（網(wǎng)上同步賽1999年開始）、NOIP、冬令營、選拔賽的基礎(chǔ)上，組織參加國際信息學(xué)奧林匹克（IOI）競賽。中國已成

16、為世界公認(rèn)的信息學(xué)奧林匹克競賽強(qiáng)國。官方網(wǎng)站：/index.shtml二、全國青少年信息學(xué)奧林匹克聯(lián)賽組織指南1競賽組別：競賽分普及組和提高組兩個組別，各分初賽和復(fù)賽兩輪進(jìn)行。2參賽對象：凡初、高中階段的學(xué)生和同等年齡段中等專業(yè)學(xué)校的在校學(xué)生均可以報名參加。3大綱與命題：聯(lián)賽大綱由主辦單位NOI科學(xué)委員會制訂并頒布。命題采取開放形式，任何有興趣者均可志愿提供候選賽題。最終競賽題目由主辦單位 NOI科學(xué)委員會確定。4組織形式：由主辦單位統(tǒng)一大綱、統(tǒng)一命題、統(tǒng)一制卷、統(tǒng)一評分標(biāo)準(zhǔn)、統(tǒng)一競賽時間、統(tǒng)一評測。5競賽形式和時間初賽為筆試，主要測試選手

17、有關(guān)計算機(jī)方面的基本知識，每年10月份的第三個周六下午2:30-4:30在各賽區(qū)進(jìn)行。復(fù)賽為上機(jī)編程，主要測試選手算法設(shè)計編程能力，每年11月份的第三個周六在各賽區(qū)進(jìn)行：提高組于上午8:30-11:30進(jìn)行，普及組于下午1:30-4:30進(jìn)行。6參賽報名及參賽資格：參賽的選手到各省組織單位報名，確認(rèn)后參加。報名工作由各賽區(qū)特派員負(fù)責(zé)實施。報名截止日期：當(dāng)年的9月20日。初賽：報名參賽的選手填寫好報名表。各賽區(qū)特派員將按普及組和提高組（分語言）分別統(tǒng)計出報名人數(shù)，于當(dāng)年的9月20日前用電子郵件或網(wǎng)絡(luò)方式將NOIP試卷數(shù)量申請表上報主辦單位。復(fù)賽：各賽區(qū)根據(jù)初賽成績從高到低依次確定參加復(fù)賽的選手，

18、不參加初賽的選手不具有參加復(fù)賽的資格。參加復(fù)賽的人數(shù)不高于參加初賽人數(shù)的20%。特派員應(yīng)于初賽后10天內(nèi)，按普及組和提高組（分語言）統(tǒng)計出參加復(fù)賽的選手和人數(shù)以及復(fù)賽試卷申請數(shù)量，用電子郵件或網(wǎng)絡(luò)方式上報主辦單位。三、全國青少年信息學(xué)奧林匹克聯(lián)賽大綱解讀（一）競賽宗旨由中國計算機(jī)學(xué)會負(fù)責(zé)組織的全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）是全國信息學(xué)奧林匹克競賽（NOI）系列活動中的一個重要組成部分，旨在向中學(xué)生普及計算機(jī)基礎(chǔ)知識，培養(yǎng)計算機(jī)科學(xué)和工程領(lǐng)域的后備人才。普及的重點(diǎn)是根據(jù)中學(xué)生的特點(diǎn)，培養(yǎng)學(xué)生學(xué)習(xí)計算機(jī)的興趣，使得他們對信息技術(shù)的一些核心內(nèi)容有更多的了解，提高他們創(chuàng)造性地運(yùn)用程序設(shè)計知識

19、解決實際問題的能力。對學(xué)生的能力培養(yǎng)將注重以下的幾個方面：想象力與創(chuàng)造力；對問題的理解和分析能力；數(shù)學(xué)能力和邏輯思維能力；對客觀問題和主觀思維的口頭和書面表達(dá)能力；人文精神：包括與人的溝通能力，團(tuán)隊精神與合作能力，恒心和毅力，審美能力等。（二）競賽形式和成績評定NOIP分兩個等級組：普及組和提高組。每組競賽分兩輪：初試和復(fù)試。初試形式為筆試，側(cè)重考察學(xué)生的計算機(jī)基礎(chǔ)知識和編程的基本能力，并對知識面的廣度進(jìn)行測試。初試為資格測試，獲本省初試成績在本賽區(qū)前15%的學(xué)生進(jìn)入復(fù)賽。復(fù)試形式為上機(jī)編程，著重考察學(xué)生對問題的分析理解能力，數(shù)學(xué)抽象能力，編程語言的能力和編程技巧、想象力和創(chuàng)造性等。各省NOI

20、P的等第將在復(fù)試的優(yōu)勝者中產(chǎn)生。比賽中使用的程序設(shè)計語言是：初賽：PASCAL或C/C+： 復(fù)賽：PASCAL或C/C+。每年復(fù)賽結(jié)束后，各省必須在指定時間內(nèi)將本省一等獎候選人的有關(guān)情況、源程序和可執(zhí)行程序報送科學(xué)委員會。經(jīng)復(fù)審和評測后，由中國計算機(jī)學(xué)會報送中國科協(xié)和教育部備案。中國計算機(jī)學(xué)會對各省獲NOIP二等獎和三等獎的分?jǐn)?shù)線或比例提出指導(dǎo)性意見，各省可按照成績確定獲獎名單。（三）試題形式每次NOIP的試題分四組：普及組初賽題A1、普及組復(fù)賽題A2、提高組初賽題B1和提高組復(fù)賽題B2。其中，A1和B1類型基本相同，A2和B2類型基本相同，但題目不完全相同，提高組難度高于普及組。1初賽初賽全

21、部為筆試，滿分100分。試題由四部分組成：（1）選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），后10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。普及組20個都是單選題。（2）問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學(xué)生對問題進(jìn)行分析，找到一個合適的算法，并推算出問題的解?？忌o出的答案與標(biāo)準(zhǔn)答案相同，則得分；否則不得分。（3）程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關(guān)于程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。

22、輸出與標(biāo)準(zhǔn)答案一致，則得分；否則不得分。（4）程序完善題：共2題，每題14分，共計28分。題目給出一段關(guān)于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。2復(fù)賽復(fù)賽的題型和考試形式與NOI類似，全部為上機(jī)編程題，但難度比NOI低。題目包括4道題，每題100分，共計400分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關(guān)說明。測試時，測試程序為每道題提供了5-10組測試數(shù)據(jù)，考生程序每答對一組得1020分，累計分即為該道題的得分。特別說明的是：自2

23、011年起，復(fù)賽提高組由一試改為兩試，分兩天進(jìn)行。每天競賽試題由原來的4題改為3題。所有進(jìn)入復(fù)賽的提高組選手均參加一試和二試，選手最終成績由一試與二試成績算術(shù)相加而得。復(fù)賽普及組不變：復(fù)賽普及組仍為一試，四個題目。四、試題的知識范圍（一）NOIP初賽內(nèi)容與要求1計算機(jī)的基本常識 （1）計算機(jī)和信息社會（信息社會的主要特征、計算機(jī)的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化）； （2）信息輸入輸出基本原理（信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式）； （3）信息的表示與處理（信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序和存儲程序原理、程序的三種基本控制結(jié)構(gòu)）； （4）信息的存儲、組織與

24、管理（存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理）； （5）信息系統(tǒng)組成及互連網(wǎng)的基本知識（計算機(jī)構(gòu)成原理、槽和端口的部件間可擴(kuò)展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP/IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點(diǎn)）； （6）人機(jī)交互界面的基本概念（窗口系統(tǒng)、人和計算機(jī)交流信息的途徑（文本及交互操作）； （7）信息技術(shù)的新發(fā)展、新特點(diǎn)、新應(yīng)用等。 2計算機(jī)的基本操作 （1）Windows和LINUX的基本操作知識； （2）互聯(lián)網(wǎng)的基本使用常識（網(wǎng)上瀏覽、搜索和查詢等）； （3）常用的工具軟件使用（文字編輯、電子郵件收發(fā)等）。 3程序設(shè)計的基本知識 （1）數(shù)據(jù)結(jié)構(gòu) 程序語言中基本數(shù)據(jù)

25、類型（字符、整數(shù)、長整、浮點(diǎn)） 浮點(diǎn)運(yùn)算中的精度和數(shù)值比較 一維數(shù)組（串）與線性表 記錄類型（PASCAL）/ 結(jié)構(gòu)類型（C） （2）程序設(shè)計 結(jié)構(gòu)化程序設(shè)計的基本概念 閱讀理解程序的基本能力 具有將簡單問題抽象成適合計算機(jī)解決的模型的基本能力 具有針對模型設(shè)計簡單算法的基本能力 程序流程描述（自然語言/偽碼/NS圖/其他） 程序設(shè)計語言（PASCAL/C/C+）- 2003仍允許BASIC （3）基本算法處理 初等算法（計數(shù)、統(tǒng)計、數(shù)學(xué)運(yùn)算等） 排序算法（冒泡法、插入排序、合并排序、快速排序） 查找（順序查找、二分法） 回溯算法 （二）NOIP復(fù)賽內(nèi)容與要求 在初賽內(nèi)容的基礎(chǔ)上增加以下內(nèi)容：

26、 1數(shù)據(jù)結(jié)構(gòu) （1）指針類型 （2）多維數(shù)組 （3）單鏈表及循環(huán)鏈表 （4）二叉樹 （5）文件操作（從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中） 2程序設(shè)計 （1）算法的實現(xiàn)能力 （2）程序調(diào)試基本能力 （3）設(shè)計測試數(shù)據(jù)的基本能力 （4）程序的時間復(fù)雜度和空間復(fù)雜度的估計 3算法處理 （1）離散數(shù)學(xué)知識的應(yīng)用（如排列組合、簡單圖論、數(shù)理邏輯） （2）分治思想 （3）模擬法 （4）貪心法 （5）簡單搜索算法（深度優(yōu)先、廣度優(yōu)先），搜索中的剪枝 （6）動態(tài)規(guī)劃的思想及基本算法 （三）NOI競賽內(nèi)容 NOI競賽的題目以考查選手對算法和編程能力的掌握為主。題目類型有以下三種： 1非交互式程序題 非交互

27、式程序題要求選手提交答案程序的源文件。該程序從一個正文文件中讀入數(shù)據(jù)，并向指定的輸出文件中寫入計算結(jié)果。非交互式程序題的題面包括下列內(nèi)容： （1）求解問題的描述 （2）輸入文件名和輸出文件名（可以是標(biāo)準(zhǔn)輸入/輸出） （3）輸入數(shù)據(jù)格式、輸出數(shù)據(jù)格式以及輸入數(shù)據(jù)范圍 （4）對程序使用計算資源的限制以及其它可能的限制 2交互式程序題 交互式程序題要求選手提交答案程序的源文件。該程序通過調(diào)用所提供的庫函數(shù)實現(xiàn)數(shù)據(jù)的輸入和輸出。交互式程序題的題面包括下列內(nèi)容： （1）求解問題的描述 （2）庫函數(shù)的功能、函數(shù)原型以及獲取和鏈接方式 （3）輸入數(shù)據(jù)格式、輸出數(shù)據(jù)格式以及輸入數(shù)據(jù)范圍 （4）對程序使用計算資

28、源的限制以及其它可能的限制 3答案提交題 答案提交題不要求選手提交程序的源文件。選手需要按題目要求，根據(jù)給定的輸入數(shù)據(jù)文件生成一組輸出數(shù)據(jù)文件。該組數(shù)據(jù)文件既可以是由選手的程序輸出的，也可以是由選手手工構(gòu)造的。當(dāng)選手使用自行設(shè)計的程序生成題目答案時，其所使用的程序不應(yīng)提交。答案提交題的題面包括下列內(nèi)容： （1）求解問題的描述 （2）輸入數(shù)據(jù)格式、輸出數(shù)據(jù)格式 （3）輸入數(shù)據(jù)文件的獲取方法 對于交互式程序題和非交互式程序題，對選手程序使用內(nèi)存大小的限制包括運(yùn)行代碼、程序運(yùn)行時所需的棧和堆在內(nèi)的所有工作內(nèi)存的總和。當(dāng)題面中沒有給出對使用內(nèi)存的限制時，以選手用機(jī)的實際使用限制為準(zhǔn)。對選手程序運(yùn)行時間

29、的限制一般均大于標(biāo)準(zhǔn)答案程序所需最長運(yùn)行時間的50%以上，以避免測試中的超時判斷誤差。 五、競賽允許使用的編程語言NOIP：允許使用Basic、Pascal或C語言。在個別賽區(qū)的個別年份允許使用C+，不過這只是極個別的情況。因此準(zhǔn)備NOIP競賽的時候最好別考慮C+。推薦使用Pascal，因為當(dāng)前市場上分區(qū)聯(lián)賽的相關(guān)輔導(dǎo)書籍都使用Pascal描述的。不推薦使用Basic，因為NOI中不允許使用這種語言。 NOI：允許使用C/C+或Pascal語言。 六、算法基礎(chǔ)（一）算法概述 1算法定義 用計算機(jī)解決問題的過程可以分成三個階段：分析問題、設(shè)計算法和實現(xiàn)算法。算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順

30、序所構(gòu)成的完整的解題步驟，它是求解問題類的、機(jī)械的、統(tǒng)一的方法，它由有限多個步驟組成，對于問題類中的每個給定的具體問題，機(jī)械地執(zhí)行這些步驟就可以得到問題的解答?；蛘呖闯砂凑找笤O(shè)計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。 2算法特征 一個算法應(yīng)該具有以下五個方面的重要特征： （1）輸入：所謂輸入是指從算法在執(zhí)行時需要從外界取得必要的信息。一個算法有零個或多個輸入，以刻畫運(yùn)算對象的初始情況。 （2）確定性：算法的每一個步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴(yán)格而不含混地進(jìn)行規(guī)定，不能有歧義性，以保證算法的實際執(zhí)行結(jié)果是精確地符合要求或期望，通常要求實際運(yùn)行結(jié)

31、果是確定的。 （3）有窮性（有限性）：一個算法在執(zhí)行有限步之后必須結(jié)束。也就是說，一個算法，它所包含的計算步驟應(yīng)是有限的。 （4）輸出：算法有一個或多個的輸出，即與輸入有某個特定關(guān)系的量，簡單地說就是算法的最終結(jié)果。 （5）有效性（可行性）：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的，換言之，它們都是能夠精確地進(jìn)行的，算法執(zhí)行者甚至不需要掌握算法的含義即可根據(jù)該算法的每一步驟要求進(jìn)行操作，并最終得出正確的結(jié)果。 （二）復(fù)雜度 不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮。 1時間復(fù)雜度 （1）

32、時間頻度 一個算法執(zhí)行所耗費(fèi)的時間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測試才能知道。但我們不可能也沒有必要對每個算法都上機(jī)測試，只需知道哪個算法花費(fèi)的時間多，哪個算法花費(fèi)的時間少就可以了。并且一個算法花費(fèi)的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費(fèi)時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T（n）。 （2）時間復(fù)雜度 在剛才提到的時間頻度中，n稱為問題的規(guī)模，當(dāng)n不斷變化時，時間頻度T（n）也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)雜度概念。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T（n）

33、表示，若有某個輔助函數(shù)f（n），使得當(dāng)n趨近于無窮大時，T（n）/f（n）的極限值為不等于零的常數(shù)，則稱f（n）是T（n）的同數(shù)量級函數(shù)。記作T（n）=O（f（n），稱O（f（n） 為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。 在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復(fù)雜度為O（1），另外，在時間頻度不相同時，時間復(fù)雜度有可能相同，如T（n）=n2+3n+4與T（n）=4n2+2n+1它們的頻度不同，但時間復(fù)雜度相同，都為O（n2）。 按數(shù)量級遞增排列，常見的時間復(fù)雜度有： 常數(shù)階O（1），對數(shù)階O（log2n）（以2為底n的對數(shù)，下同），線性階O（n），線性對數(shù)階O（nlog2n

34、），平方階O（n2），立方階O（n3），.，k次方階O（nk），指數(shù)階O（2n）。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。 2空間復(fù)雜度 算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計算和表示方法與時間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。空間復(fù)雜度是指算法在計算機(jī)內(nèi)執(zhí)行時所需存儲空間的度量。 記作：S（n）=O（f（n） 我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。 （三）算法描述描述算法的方法有多種，常用的有自然語言、結(jié)構(gòu)化流程圖、偽代碼和程序設(shè)計語言等，其中最普遍的是流程圖。1用自然語言表示

35、自然語言是人們?nèi)粘Ｋ玫恼Z言，如漢語、英語、德語等。使用這些語言不用專門訓(xùn)練，所描述的算法也通俗易懂。但比較冗長，容易出現(xiàn)歧義性。自然語言往往含義不太嚴(yán)格，很多時候需要根據(jù)上下文才能準(zhǔn)確地判斷其正確的含義。此外用自然語言來描述分支或循環(huán)的算法，比較麻煩。因此，除了那些很簡單的算法外，一般很少用自然語言來描述算法。 2用流程圖表示 以特定的圖形符號加上說明，表示算法的圖，稱為流程圖或框圖。流程圖是由一些圖框和流程線組成的，其中圖框表示各種操作的類型，圖框中的文字和符號表示操作的內(nèi)容，流程線表示操作的先后次序。 流程圖主要包括： 圓角矩形表示“開始”與“結(jié)束”； 矩形表示行動方案、普通工作環(huán)節(jié)用；

36、 菱形表示問題判斷或判定（審核/審批/評審）環(huán)節(jié)； 用平行四邊形表示輸入輸出； 箭頭代表工作流方向。 美國國家標(biāo)準(zhǔn)化協(xié)會ANSI規(guī)定了一些常用的流程圖符合，已為世界各國程序工作者普遍使用。 1966年，Bohra和Jacopini提出了三種基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)作為表示一個良好算法的基本單元。 三種結(jié)構(gòu)共同特點(diǎn)： （1）只有一個入口； （2）只有一個出口； （3）結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會被執(zhí)行到（不存在死語句）； （4）結(jié)構(gòu)內(nèi)不存在死循環(huán)（永遠(yuǎn)執(zhí)行不完的循環(huán)）。 1973年美國學(xué)者I. Nassi和B. Shneiderman提出了一種新的流程圖形式，完全去掉了帶箭頭的流程線，

37、稱為N-S流程圖表示法。 3偽代碼表示 偽代碼是用介于自然語言和計算機(jī)語言之間的文字和符號來描述算法。它自上而下，每一行（或幾行）表示一個基本操作。不用圖形符號，書寫方便，格式緊湊，也比較好懂，也便于向計算機(jī)語言算法（即程序）過渡。 4程序設(shè)計語言 按照某種編程語言的規(guī)范，用該編程語言編寫實現(xiàn)算法。 七、常見算法1算法可以宏泛分為三類： （1）有限的，確定性算法：這類算法在有限的一段時間內(nèi)終止。它們可能要花很長時間來執(zhí)行指定的任務(wù)，但仍將在一定的時間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。 （2）有限的，非確定算法：這類算法在有限的時間內(nèi)終止。然而，對于一個（或一些）給定的數(shù)值，算法的結(jié)果并

38、不是唯一的或確定的。 （3）無限的算法：是那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數(shù)據(jù)滿足而不終止運(yùn)行的算法。通常，無限算法的產(chǎn)生是由于未能確定的定義終止條件。 2算法具體分類 算法可大致分為基本算法（枚舉、搜索、深度優(yōu)先搜索、廣度優(yōu)先搜索、啟發(fā)式搜索、遺傳算法）、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計算幾何的算法（凸包）、圖論的算法（哈夫曼編碼、樹的遍歷、最短路徑、最小生成樹、最小樹形圖）、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法。 （1）枚舉：羅列出某些有窮序列集的所有成員，逐一進(jìn)行嘗試，直到找到滿足條件的解。 （2）搜索：搜索算法是利用計算機(jī)的高

39、性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。 （3）深度優(yōu)先搜索：深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索樹。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前（子結(jié)點(diǎn)）探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇不符合要求，就回溯至父親結(jié)點(diǎn)重新選擇另一結(jié)點(diǎn)，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至求得最優(yōu)解。深度優(yōu)先搜索的實現(xiàn)方式可以采用遞歸或者棧來實現(xiàn)。 （4）廣度優(yōu)先搜索：類似樹的按層遍歷，其過程為：首先訪問初始點(diǎn)Vi，并將其標(biāo)記為已訪問過，接著訪問Vi的所有未被訪問過可到達(dá)的鄰接點(diǎn)Vi1、Vi2Vit，并均標(biāo)記為已訪問過，然后再按照Vi1、Vi

40、2Vit的次序，訪問每一個頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，并均標(biāo)記為已訪問過，依此類推，直到圖中所有和初始點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問過為止。 （5）啟發(fā)式搜索：啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進(jìn)行評估，得到最好的位置，再從這個位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。 （6）遺傳算法：遺傳算法是計算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。 遺傳算法通常實現(xiàn)方式為一種計

41、算機(jī)模擬。對于一個最優(yōu)化問題，一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進(jìn)化。傳統(tǒng)上，解用二進(jìn)制表示（即0和1的串），但也可以用其他表示方法。進(jìn)化從完全隨機(jī)個體的種群開始，之后一代一代發(fā)生。在每一代中，整個種群的適應(yīng)度被評價，從當(dāng)前種群中隨機(jī)地選擇多個個體（基于它們的適應(yīng)度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。 （7）凸包分為兩種情況：點(diǎn)集Q的凸包是指一個最小凸多邊形，滿足Q中的點(diǎn)或者在多邊形邊上或者在其內(nèi)。 一組平面上的點(diǎn)，求一個包含所有點(diǎn)的最小的凸多邊形，這就是凸包問題了。 （8）遞推法：遞推算法是一種用若干步可重復(fù)的簡運(yùn)

42、算（規(guī)律）來描述復(fù)雜問題的方法。遞推是序列計算機(jī)中的一種常用算法。它是按照一定的規(guī)律來計算序列中的每個項，通常是通過計算機(jī)前面的一些項來得出序列中的指定象的值。其思想是把一個復(fù)雜的龐大的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)，該算法利用了計算機(jī)速度快和不知疲倦的機(jī)器特點(diǎn)。 （9）遞歸法：程序調(diào)用自身的編程技巧稱為遞歸。 一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，

43、遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時，遞歸前進(jìn)；當(dāng)邊界條件滿足時，遞歸返回。 注意： 遞歸就是在過程或函數(shù)里調(diào)用自身； 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。 （10）窮舉法：或稱為暴力破解法，是一種針對于密碼的破譯方法，即將密碼進(jìn)行逐個推算直到找出真正的密碼為止。例如一個已知是四位并且全部由數(shù)字組成的密碼，其可能共有10000種組合，因此最多嘗試10000次就能找到正確的密碼。理論上利用這種方法可以破解任何一種密碼，問題只在于如何縮短試誤時間。因此有些人運(yùn)用計算機(jī)來增加效率，有些人輔以字典來縮小密碼組合的范圍。 （11）貪婪算法: 貪婪算法是

44、一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計技術(shù)。用貪婪法設(shè)計算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題， 通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪婪法不要回溯。 貪婪算法是一種改進(jìn)了的分級處理方法。其核心是根據(jù)題意選取一種量度標(biāo)準(zhǔn)。然后將這多個輸入排成這種量度標(biāo)準(zhǔn)所要求的順序，按這種順序一次輸入

45、一個量。如果這個輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最佳解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優(yōu)解的分級處理方法稱為貪婪算法。對于一個給定的問題，往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來，這些量度標(biāo)準(zhǔn)似乎都是可取的，但實際上，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，但對某問題能選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪婪算法求解則特別有效。最優(yōu)解可以通過一系列局部最優(yōu)的選擇即貪婪選擇來達(dá)到，根據(jù)當(dāng)前狀態(tài)做出

46、在當(dāng)前看來是最好的選擇，即局部最優(yōu)解選擇，然后再去解做出這個選擇后產(chǎn)生的相應(yīng)的子問題。每做一次貪婪選擇就將所求問題簡化為一個規(guī)模更小的子問題，最終可得到問題的一個整體最優(yōu)解。 （12）分治法：就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 分治法所能解決的問題一般具有以下幾個特征： 該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 利用該問題分解出的子問題的解可以合并為該問題的解； 該問題所分解出的各個子問題是相互獨(dú)立的，即子

47、問題之間不包含公共的子子問題。 （13）動態(tài)規(guī)劃法 :動態(tài)規(guī)劃是一種在數(shù)學(xué)和計算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計算機(jī)科學(xué)和工程領(lǐng)域。 動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不像前面所述的那些搜索或數(shù)值計算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法

48、，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 （14）迭代法: 迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代法又分為精確迭代和近似迭代?！岸址ā焙汀芭ｎD迭代法”屬于近似迭代法。迭代算法是用計算機(jī)解決問題的一種基本方法。它利用計算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計算機(jī)對一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值

49、。 （15）分枝界限法: 分枝界限法是一個用途十分廣泛的算法，運(yùn)用這種算法的技巧性很強(qiáng)，不同類型的問題解法也各不相同。分支定界法的基本思想是對有約束條件的最優(yōu)化問題的所有可行解（數(shù)目有限）空間進(jìn)行搜索。該算法在具體執(zhí)行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個子集內(nèi)的解的值計算一個下界或上界（稱為定界）。在每次分支后，對凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支。這樣，解的許多子集（即搜索樹上的許多結(jié)點(diǎn)）就可以不予考慮了，從而縮小了搜索范圍。這一過程一直進(jìn)行到找出可行解為止，該可行解的值不大于任何子集的界限。因此這種算法一般可以求得最優(yōu)解。與貪心算法一樣，這種方

50、法也是用來為組合優(yōu)化問題設(shè)計求解算法的，所不同的是它在問題的整個可能解空間搜索，所設(shè)計出來的算法雖其時間復(fù)雜度比貪婪算法高，但它的優(yōu)點(diǎn)是與窮舉法類似，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優(yōu)解的子空間進(jìn)一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高。 （16）排序算法: 所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。目前主要有插入排序、冒泡排序、選擇排序、快速排序、堆排序、歸并排序、基數(shù)排序、希爾排序等。專題二 數(shù)制轉(zhuǎn)換與高精度計算【主要內(nèi)容】 1. 數(shù)制轉(zhuǎn)換：介紹數(shù)

51、制的相關(guān)概念以及常見的各種數(shù)制及其它們之間的轉(zhuǎn)換。 2. 高精度計算：介紹高精度數(shù)的各種運(yùn)算。 【學(xué)習(xí)重點(diǎn)】 數(shù)制的相關(guān)概念、常見的各種數(shù)制及其它們之間的轉(zhuǎn)換以及高精度數(shù)的各種運(yùn)算。 一、數(shù)制轉(zhuǎn)換（一）相關(guān)概念1數(shù)制 數(shù)制是人們利用符號進(jìn)行計數(shù)的一種科學(xué)方法。數(shù)制也稱計數(shù)制，是用一組固定的符號和統(tǒng)一的規(guī)則來表示數(shù)值的方法。 2進(jìn)制 進(jìn)制也就是進(jìn)位制，是人們規(guī)定的一種進(jìn)位方法。對于任何一種進(jìn)制X進(jìn)制，就表示某一位置上的數(shù)運(yùn)算時是逢X進(jìn)一位。 十進(jìn)制是逢十進(jìn)一，十六進(jìn)制是逢十六進(jìn)一，二進(jìn)制就是逢二進(jìn)一。 3數(shù)碼 數(shù)制中表示基本數(shù)值大小的不同數(shù)字符號。例如，十進(jìn)制有10個數(shù)碼：0、1、2、3、4、5

52、、6、7、8、9。 4基數(shù) 數(shù)制所使用數(shù)碼的個數(shù)。例如，二進(jìn)制的基數(shù)為2；十進(jìn)制的基數(shù)為10。 5位權(quán) 位權(quán)表示數(shù)的符號在不同的位置上時所代表的數(shù)的值是不同的。也就是數(shù)制中某一位上的1所表示數(shù)值的大?。ㄋ幬恢玫膬r值）。例如，十進(jìn)制的123，1的位權(quán)是100，2的位權(quán)是10，3的位權(quán)是1。 （二）各種常見的進(jìn)制 人們通常采用的進(jìn)制有十進(jìn)制、二進(jìn)制、八進(jìn)制和十六進(jìn)制等。 1十進(jìn)制（Decimal） 十進(jìn)制是人們?nèi)粘Ｉ钪凶钍煜さ倪M(jìn)位計數(shù)制。在十進(jìn)制中，數(shù)碼共有0，1，2，3，4，5，6，7，8，9這十個符號。計數(shù)規(guī)則是逢十進(jìn)一。 2二進(jìn)制（Binary） 二進(jìn)制是在計算機(jī)系統(tǒng)中采用的進(jìn)位計數(shù)制。

53、二進(jìn)制數(shù)有兩個特點(diǎn)：在二進(jìn)制中，數(shù)碼有0和1兩個符號。計數(shù)規(guī)則是逢二進(jìn)一。 為區(qū)別于其它進(jìn)制數(shù)，二進(jìn)制數(shù)的書寫通常在數(shù)的右下方注上基數(shù)2，或在后面加上B表示。例如：二進(jìn)制數(shù)10110011可以寫成（10110011）2，或?qū)懗?0110011B。 3八進(jìn)制數(shù)（Octal） 由于二進(jìn)制數(shù)據(jù)的基數(shù)比較小，所以二進(jìn)制數(shù)據(jù)的書寫和閱讀很不方便，為此，在小型機(jī)中引入了八進(jìn)制。八進(jìn)制的基數(shù)R=8=23，有數(shù)碼0、1、2、3、4、5、6、7，并且每個數(shù)碼正好對應(yīng)三位二進(jìn)制數(shù)，所以八進(jìn)制能很好地反映二進(jìn)制。八進(jìn)制用下標(biāo)8或數(shù)據(jù)后面加O表示 例如：二進(jìn)制數(shù)據(jù) （ 11 101 010 . 010 110 100

54、 ）2 ，對應(yīng)的八進(jìn)制數(shù)據(jù) ( 3 5 2 . 2 6 4 )8或352.264O。 4十二進(jìn)制（Duodecimal） 十二進(jìn)制在生活中也是經(jīng)常用到的，例如，長度單位一英尺等于12英寸，一先令等于12便士，就連足球比賽罰點(diǎn)球的英制長度也是12碼。此外還有一打12個，鐘表轉(zhuǎn)一圈12小時等等。 一般在十二進(jìn)制中，10和11可用M和N表示，有時候也可用A和B表示。 5十六進(jìn)制（Hexadecimal） 十六進(jìn)制是人們在計算機(jī)指令代碼和數(shù)據(jù)的書寫中經(jīng)常使用的數(shù)制。在十六進(jìn)制中，由十六個字符09以及A，B，C，D，E，F(xiàn)（或a，b，f）組成（它們分別表示十進(jìn)制數(shù)1015）來描述。計數(shù)規(guī)則是逢十六進(jìn)一，即基數(shù)R=16=24，通常在表示時用尾部標(biāo)志H或下標(biāo)16以示區(qū)別。例如：十六進(jìn)制數(shù)4AC8可寫成（4AC8）16，或?qū)懗?AC8H。 6六十進(jìn)位制數(shù)（Sexagesimal） 古代人由于生產(chǎn)勞動的需要，要研究天文和歷法，就牽涉到時間和角度了。因為歷法需要的精確度較高，時間的單位小時，角度的單位度都嫌太大。必須進(jìn)一步研究他們的小數(shù)。它們的小數(shù)都具有這樣的性質(zhì)：使1/2，1/3，1/4，1/5，1