青少年信息學競賽簡要介紹

1、青少年信息學競賽簡要介紹青少年信息學（計算機）奧林匹克競賽（早期稱為青少年計算機程序設計競賽）是旨在廣大青少年中普及計算機教育，推廣計算機應用的一項學科性競賽活動。全國從1984年開始舉辦全國性競賽。而自從1989年我國參加第一屆國際信息學奧林匹克（International Olympiad in Informatics, 簡稱IOI）以來，全國青少年計算機程序設計競賽也更名為全國青少年信息學（計算機）奧林匹克（National Olympiad in Informatics, 簡稱NOI）。全國信息學奧林匹克競賽是經(jīng)國家教委批準，中國科協(xié)具體領導，由中國計算機學會主辦的。浙江省信息學奧林匹

2、克競賽活動從84年參加全國賽開始，由省科學技術協(xié)會、省教育廳和省計算機學會聯(lián)合組織。 為促進計算機普及并兼顧提高，從95年開始全國舉辦信息學奧林匹克競賽分區(qū)聯(lián)賽，根據(jù)浙江實際情況，我省將分區(qū)聯(lián)賽初、復賽作為省信息學奧賽的初賽和復賽。浙江省開始幾年初賽試題自己命題，現(xiàn)在采用全國卷。一 信息學奧林匹克競賽的內(nèi)容和考核方式：對學生學習計算機理論知識和實踐能力有一個整體性的全面要求，也即整個信息學（計算機）競賽已成為智力和應用計算機能力的競賽，涉及到有關計算機基礎知識、計算機軟件知識、程序設計知識、組合數(shù)學和運籌學的知識、人工智能初步知識以及計算機應用知識等，同時要求學生有較強的編程和上機調(diào)試的實踐能

3、力。 1 NOI全國分區(qū)聯(lián)賽初賽 (每年10月左右)對象：在校中學生， 分初中、高中組考試形式：筆試 性質(zhì)： 普及確定獲初級選手證書名單及進入復賽名單，在各地市舉行。2NOI全國分區(qū)聯(lián)賽復賽 (每年12月左右)對象：初賽優(yōu)勝者 分初中、高中組考試形式：上機試 性質(zhì)：普及兼顧提高確定全國分區(qū)聯(lián)賽一、二等獎，省各等獎及全國各級證書獲得者名單，在杭州進行，省派評委協(xié)助測評。信息學奧林匹克競賽復賽的考核方式是采用封閉式（連續(xù)34小時）上機編程解題的形式，編程語言基本限于BASIC與 PASCAL，競賽難度較大。程序完成后要通過嚴格的數(shù)據(jù)測試，這就對同學們編程能力有更高的要求：不但要能編程，編好的程序能

4、運行，而且所設計的程序還要能通過在各種邊界條件下和各種環(huán)境下設置的測試數(shù)據(jù)。二 全國青少年信息學奧林匹克聯(lián)賽大綱競賽大綱一、初賽內(nèi)容與要求：（表示普及組可不涉及，以下同）計基算本機常的識*誕生與發(fā)展 *特點 *在現(xiàn)代社會中的應用 *計算機系統(tǒng)的基本組成 *計算機中的數(shù)的表示 *計算機的工作原理# *計算機信息安全基礎知識 *計算機網(wǎng)絡 計 基算 本機 操的 作*常見操作系統(tǒng)的使用基礎*常用輸入/輸出設備的種類、功能、使用*漢字輸入/輸出方法 *常用計算機屏示信息程序設計基本知識程序的表示*自然語言的描述 *PASCAL或BASIC語言數(shù)據(jù)結(jié)構(gòu)*簡單數(shù)據(jù)的類型 *構(gòu)造類型：數(shù)組、字符串*了解基本

5、數(shù)據(jù)結(jié)構(gòu)（線性表、隊列與棧）程序設計*結(jié)構(gòu)化程序的基本概念 *閱讀理解程序的基本能力*具有完成下列過程的能力：現(xiàn)實世界（指知識范疇的問題）信息世界（表達解法）計算機世界（將解法用計算機能實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法描述出來）基本算法處 理*簡單搜索 *字串處理 *排序 *查找 *統(tǒng)計 *分類 *合并 *簡單的回溯算法 *簡單的遞歸算法二、復賽內(nèi)容與要求： 在初賽的內(nèi)容上增加以下內(nèi)容：計算機軟 件*操作系統(tǒng)的使用知識 *編程語言的使用 數(shù)據(jù)結(jié)構(gòu)*結(jié)構(gòu)類型中的記錄類型 *指針類型 *文件（提高組必須會使用文本文件輸入）*鏈表 *樹 *圖#程序設計*程序設計能力 *設計測試數(shù)據(jù)的能力*運行時間和占用空間的估

6、算能力#算法處理*排列組合的應用 *進一步加深回溯算法、遞歸算法*分治法 *搜索算法：寬度、深度優(yōu)先算法*表達式處理：計算、展開、化簡等# *動態(tài)規(guī)劃#三、初賽試題類型：注：試題語言兩者選一、高中學生必須參加提高組聯(lián)賽。 （ 程序設計語言：基本BASIC或TURBO PASCAL） *判斷 *填空 *完善程序 *讀程序?qū)戇\行結(jié)果 *問答四、推薦讀物： *分區(qū)聯(lián)賽輔導叢書 *學生計算機世界報三 Pascal語言一、 結(jié)構(gòu)化程序設計結(jié)構(gòu)化程序設計實際上就是為了使程序具有合理的結(jié)構(gòu)，以便保證和驗證程序的正確性而規(guī)定的一套進行結(jié)構(gòu)程序設計的方法。用結(jié)構(gòu)化程序設計的方法設計出來的程序稱為結(jié)構(gòu)化程序。結(jié)構(gòu)

7、化程序設計語言就是反映了結(jié)構(gòu)化程序設計的要求和限制，便于用來書寫結(jié)構(gòu)化程序的語言。用這種語言書寫的程序易于保證正確性。 二、 PASCAL語言的特色 從使用者的角度看，PASCAL語言有以下幾個主要特點： 1、它是結(jié)構(gòu)化語言 PASCAL語言是結(jié)構(gòu)化的程序設計語言。PASCAL語言提供了直接實現(xiàn)3種基本結(jié)構(gòu)的語句心以及定義子程序(“過程”和“函數(shù)”)的功能?？梢苑奖愕臅鴮懗鼋Y(jié)構(gòu)化的程序。在編寫程序時可以完全不使用轉(zhuǎn)向語句。這就易于保證程序的正確性和易讀性。PASCAL語言強調(diào)的是可靠性、易讀性和概念性的清晰性。 2、有豐富的數(shù)據(jù)類型 PASCAL語言提供了整型、實型、字符型、布爾型、枚舉型、子

8、域型以及由以上類型構(gòu)成的數(shù)組類型、集合類型、記錄類型和文件類型。此外，還提供了指針類型。PASCAL語言所提供的豐富的數(shù)據(jù)結(jié)構(gòu)和上述的結(jié)構(gòu)化性質(zhì)，使得它可以被方便地用來描述復雜的算法，得到質(zhì)量較高的程序。 3、能適應于數(shù)值計算和非數(shù)值信息處理領域 在PASCAL語言出現(xiàn)之前，F(xiàn)ORTRAN語言主要處理科學計算，而COBOL語言則主要用于非數(shù)值信息處理。PASCAL語言則兼顧了這兩個不同領域的應用。PASCAL語言可廣泛應用于各種領域，還可以用于計算機輔助教育、計算機繪圖等應用領域。 4、PASCAL程序的書寫格式比較自由 PASCAL允許一行寫多個語句，一個語句可以分寫在多行上，這樣就可以使P

9、ASCAL程序?qū)懙孟裰v詩歌格式一樣優(yōu)美，便于閱讀。 除了以上優(yōu)點外，PASCAL語言還具有簡單易學的特點，許多學校把PASCAL作為程序設計課程的第一種程序設計語言。 PASCA:L語言的主要缺點：不夠靈活，書寫較麻煩。四 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)基礎課程之一，是十分重要的核心課程。計算機的所有系統(tǒng)軟件和應用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。要想更好地運用計算機來解決實際問題，僅僅學習計算機語言而缺乏數(shù)據(jù)結(jié)構(gòu)知識是遠遠不夠的，而打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的扎實基礎，對于學習計算機專業(yè)的其他課程都是十分重要的。隨著計算機應用領域不斷擴大，非數(shù)值計算問題占據(jù)了當今計算機應用的絕大多數(shù)，簡單的數(shù)據(jù)

10、類型已經(jīng)遠遠不能滿足需要，各數(shù)據(jù)元素之間的復雜聯(lián)系已經(jīng)不是普通數(shù)學方程所能表達的。因此，掌握好數(shù)據(jù)結(jié)構(gòu)方面的知識，對于提高我們解決實際問題的能力將會有莫大的幫助。實際上一個好的程序無非是選擇一個合適的數(shù)據(jù)結(jié)構(gòu)和好的算法，而好的算法的選擇很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)的選取。所以，學好數(shù)據(jù)結(jié)構(gòu)，將是進一步提高我們程序設計的關鍵之一。五 算法例子1稱小球重量：有6個小球分別用16編號, 其中5個重量相同?，F(xiàn)在有一架臺稱，一次能稱出放在上面的若干物體的總重，要求編一個程序，讓計算機找出一種稱法，只要稱3次就可以知道每個小球的重量。具體操作時由操作者默想6個物體的重量，然后由計算機用編號提問若

11、干物體的重量，如此3次后程序應能輸出每個物體的重量。PROGRAM EX02;VARS1, S2, S3, p: integer;BEGINP:=0;write(請輸入1號+2號+3號+4號的重量總和:); read（s1）;write(請輸入1號+2號+5號的重量總和:'); read（S2）；IF 3*s1<>4*s2 THENBEGINwrite('請輸入1號+3號的重量總和：）; read(s3);IF S1+S3=2*S2 THEN BEGIN P:=1; Writeln(第1號重, S3+S2-S1,其余重,S2-S3);END;IF S3+2*S2 =

12、2*S1 THENBEGIN p:=1; writen(第2號重, 3*S2-2*S1, ,其余重,S1-S2); END;IF 2*S2+3*S33*S1 THENBEGIN p:=1; writeln(第3號重,S3-(S2 div 3),其余重,S2 div 3); END;IF 2*S23*S3 THEN BEGIN p:=1; writeln(第4號重,S1-3*(S3 div 2),其余重,S3 div 2); END;IF S1 =2*S3 THENBEGIN p:=1; writeln(第5號重,s2-2*(s3 div 2),其余重, s3 div 2), END;IF p:

13、=0 THEN writeln('輸入的數(shù)據(jù)不正確!');ENDELSE IF 3*s1 = 4*s2 THENBEGIN write('請輸入6號的重量:'); read（s3）;writeln('第6號重',s3, '其余重' ,s2 div 3);END;Writeln;END.2打印奇數(shù)階幻方： 方法：M×M 階奇數(shù)幻方,在最后一行（第 M行）的中間(M+1)/2處填上1,左下方向填2, .,若前方已經(jīng)有數(shù),在原數(shù)的上方填入。 三階: 2 9 4 7 5 3程序如下: 6 1 8program huafang;

14、var i,j,k,n :integer; a: array1.20,1.20 of integer; 五階：9 2 25 18 11 begin 3 21 19 12 10 for i:= 1 to 20 do 22 20 13 6 4 for j:= 1 to 20 do ai,j:=0; 16 14 7 5 23 write('Input n:'); readln(n); 15 8 1 24 17 while (n mod 2=1) and (n<=19) do begin i:=n; j:=(n div 2)+1; ai,j:=1; for k:= 2 to n*

15、n do begin i:=i+1; j:=j-1; if i=n+1 then i:=1; if j=0 then j:=n; if ai,j=0 then ai,j:=k else begin i:=i-2; j:=j+1; if i<0 then i:=i+n; if j=n+1 then j:=1; ai,j:=k; end; end; for i:= 1 to n do begin for j:= 1 to n do write(ai,j:4); writeln; end; exit; end; write('Error!'); end.313個人編號圍成一圈，

16、從1開始，4個一數(shù)，數(shù)到者出列，打印出列的順序。（方法一：） Program EX1301; Const m=13;t=4; Var i,k,p :integer; A:array1.m of integer; Begin For i:= 1 to m do ai:=1; I:=0; k:=0; p:=0; Repeat I:=i+1;if i=m+1 then i:=1; K:=k+ai; If k=t then Begin Write(i:4);ai:=0; p:=p+1; k:=0; End; Until p=m; Writeln; End. （方法二：鏈接表） Program EX13

17、02; Const m=13;t=4; Var i,j,k,p :integer; A:array1.m of integer; Begin For i:= 1 to m-1 do ai:=i+1; Am:=1; i:=m; k:=1; p:=0; Repeat i:=ai; k:=k+1; If k=t then Begin Write(ai:4); ai:=aai; p:=p+1; k:=1; End; Until p=m; writeln; End.出列順序： 4 8 12 3 9 1 7 2 11 10 13 6 5計算機的數(shù)制、碼制及其運算1 計算機是智能化的電器設備計算機就其本身來

18、說是一個電器設備，為了能夠快速存儲、處理、傳遞信息，其內(nèi)部采用了大量的電子元件，在這些電子元件中，電路的通和斷，電壓高和低，這兩種狀態(tài)最容易實現(xiàn)，最穩(wěn)定；也最容易實現(xiàn)對電路本身的控制。我們將計算機所能表示這樣的狀態(tài)，用0，1來表示，就形成了用二進制數(shù)表示計算機內(nèi)部的所有運算和操作。計算機內(nèi)部是以二進制形式表示數(shù)據(jù)的(指令、被處理的數(shù)據(jù))。二進制數(shù)的運算規(guī)則：00=0 01=1 10=1 11=10；0×0=0 0×1=0 1×0=0 1×1=12 進位基數(shù)和位權值數(shù)的進制與基數(shù)計數(shù)的進制不同，則它們的基數(shù)也不相同，用到的數(shù)碼也不一樣。如表1-1所示。進制

19、基數(shù)數(shù)碼二進制201三進制3012四進制40123八進制801234567十進制100123456789十六進制160123456789ABCDEF進制基數(shù)：指的是該進位記數(shù)制中可能用到的數(shù)碼個數(shù)。對于任意計數(shù)進制：每一位計滿這個基數(shù)后，都應向高位進位。二進制，逢二進一；八進制，逢八進一；十進制，逢十進一；十六進制，逢十六進一；R進制(R為任意正整數(shù))：數(shù)碼個數(shù)為R個，分別為0R-1，每一位數(shù)當計滿R后，應向高位進位。數(shù)的權不同進制的數(shù)，基數(shù)不同，其每位上所代表的值的大小也不相同，我們稱之為“權”。如：(219)10=2×1021×1019×100 (按權展開式)

20、2在百位上代表2個100即200；1在十位上代表1個10即10；9在個位上代表9個1即9。注：以后我們用下標來注明圓括號內(nèi)數(shù)的進制。 (11010)2=1×241×230×221×210×20(273)8=2×827×813×80(27B)16=2×1627×16111×160任意R進制S：S=knkn-1k0.k-1k-2k-m = kn×Rnkn-1×Rn-1k0×R0.k-1×R-1k-2×R-2k-m×R-mR為進位基

21、數(shù)，Ri是對應的權值。3 任意進制的數(shù)轉(zhuǎn)換成十進制整數(shù)將任意進制數(shù)轉(zhuǎn)換成十進制數(shù)的基本方法是按權展開，然后求和按權相加法。因為在上式中基數(shù)我們已經(jīng)轉(zhuǎn)換成了相應的十進制數(shù)，所以展開式即是一個十進制數(shù)的表達式。(11010)2=1×241×230×221×210×20=(26)10(123)8=1×822×813×80=(83)10 (1AB)16=(427)104 十進制整數(shù)轉(zhuǎn)換成任意進制數(shù)將十進制整數(shù)轉(zhuǎn)換成任意進制數(shù)的基本方法是：將十進制數(shù)除以所給定的進制的基數(shù)，再反向取余。例如：將十進制數(shù)39用二進制數(shù)表示，用除

22、二反向取余法。 (39)10=(100111)2(245)10=(365)8減權定位法：把十進制數(shù)展開成所指定進制的基數(shù)的整數(shù)次冪之和，然后找到對應位上取值。例如：將十進制數(shù)123用二進制數(shù)表示。(123)10=64+32+16+8+0+2+1=1×26+1×25+1×24+1×23+0×22+1×21+1×20 =(1111011)25 十進制小數(shù)轉(zhuǎn)換成任意進制數(shù)常用把給定的十進制小數(shù)乘以給定進制數(shù)的基數(shù)，取積的整數(shù)部分，得到給定進制小數(shù)的小數(shù)點的第1位；乘積的小數(shù)部分再乘以基數(shù)，積的整數(shù)部分為小數(shù)點后的第2位；一直重復做

23、下去，就可以得到希望的進制小數(shù)。例如：將十進制小數(shù)0.75轉(zhuǎn)換成二進制小數(shù)。0.75×2=1.50.5×2=1 (0.75)10=(0.11)2(0.315)10=(0.0101)2不是所有的十進制小數(shù)都可以用一個精確的二進制小數(shù)表示。6 二進制與八進制之間的轉(zhuǎn)換三位二進制，正好能完全表示八進制的8個數(shù)碼。二進制000001010011100101110111八進制01234567二進制數(shù)轉(zhuǎn)換成八進制數(shù)的方法是：從小數(shù)點開始，分別向左向右，每3位二進制數(shù)為一組，用八進制來書寫。若左側(cè)位數(shù)不是3的倍數(shù)，則最左側(cè)用0補充，若右側(cè)位數(shù)不是3的倍數(shù)，則最右側(cè)用0補充。例如：(101

24、10111.01101)2=(267.32)8反過來，八進制數(shù)轉(zhuǎn)換成二進制數(shù)的方法：將每個八進制數(shù)用3位二進制數(shù)來書寫。例如：(1234.45)8=(1010011.100101)27 二進制與十六進制之間的轉(zhuǎn)換二進制0000000100101001101010111100110111101111十六進制0129ABCDEF每四位二進制數(shù)可以用一位十六進制數(shù)表示。二進制數(shù)轉(zhuǎn)換成十六進制數(shù)方法：從小數(shù)點開始，分別向左向右，每4位二進制數(shù)為一組，用十六進制來書寫。若左側(cè)位數(shù)不是4的倍數(shù)，則最左側(cè)用0補充，若右側(cè)位數(shù)不是4的倍數(shù)，則最右側(cè)用0補充。例如：(110110111.01101)2=(1B7

25、.68)16十六進制數(shù)轉(zhuǎn)換成二進制數(shù)方法：將每個十六進制數(shù)用4位二進制來書寫，其最左或最右側(cè)的0可以省去。例如：(7AC.DE)16=(11110101100.1101111)2綜合例子：(3/32)10轉(zhuǎn)換成二進制解：(3/32)10=3×2-5=(11)2×(0.00001)2=(0.00011)2總之：十進制數(shù)與二進制數(shù)之間的轉(zhuǎn)換必須用前面講的繁瑣方法進行，因為10不能用2的整數(shù)次冪進行表示。也就是不能象八進制或十六進制數(shù)那樣用幾位二進制數(shù)表示十進制數(shù)的十個數(shù)碼。把十進制數(shù)27.625轉(zhuǎn)換成二進制、八進數(shù)和十六進制數(shù)。解：(27)10=(11011)2(0.625)1

26、0=(0.101)2(27.625)10=(11011.101)2=(33.5)8=(1B.A)16要把一個十進制數(shù)轉(zhuǎn)換為八進制數(shù)或十六進制，最先把它轉(zhuǎn)換成二進制數(shù)，再由二進制數(shù)轉(zhuǎn)換成八進制或十六進制。課后練習： 請用等號或不等號聯(lián)接下列不同進位制數(shù)值的大小。(98.375)10 (142.3)8 (58.5)16 (1011000.0101)2 下面四個不同進制的數(shù)，最小的數(shù)是 。A (11011001)2 B (75)10 C (37)8 D (A7)16 小張用十六進制、八進制和十進制寫了如下一個等式：52-19=33式中三個數(shù)是各不相同進位制的數(shù)，請問52、19、33，分別為 。A 八

27、進制，十進制，十六進制 B 十進制，十六進制，八進制C 八進制，十六進制，十進制 D 十進制，八進制，十六進制 十進制算術表達式：3*512+7*64+4*8+5的運算結(jié)果，用二進制表示為( )A 10111100101 B 11111100101 C 11110100101 D 11111101101二進數(shù)在計算機內(nèi)的表示數(shù)值數(shù)據(jù)是用于表示數(shù)量的大小，經(jīng)常用到數(shù)值范圍和數(shù)據(jù)精度。數(shù)值范圍指的是一種類型的數(shù)據(jù)所能表示的最大值和最小值；數(shù)據(jù)精度通常用實數(shù)所能指出的有效數(shù)字位數(shù)來表示。與用多少個二進制位表示某類數(shù)據(jù)，以及怎么對這些位進行編碼有關。機器數(shù)與真值計算機中數(shù)的符號用數(shù)碼表示。一般情況下，

28、用0表示正，用1表示負。且符號位放在數(shù)的最高位。例：X1=(+1011011)2 真值數(shù)X2=(-1011011)20101101111011011機器數(shù) 連同符號位在一起作為一個數(shù)，稱為機器數(shù)。而它的數(shù)值部分稱為真值數(shù)。一、 數(shù)的定點和浮點表示計算機在處理數(shù)據(jù)時，要考慮到小數(shù)點的位置。如果將小數(shù)點固定在某一位置，則稱為定點表示；如果小數(shù)點可以任意移動，則稱為浮點表示。1 數(shù)的定點表示法定點小數(shù)和定點整數(shù)定點小數(shù)格式：小數(shù)點的位置固定在最高數(shù)據(jù)位的左邊，小數(shù)點前面再設一位符號位。任何m位二進制小數(shù)在計算機中用m+1位二進制表示。Ns ·N-1N-2N-m+1N-m符號位 小數(shù)點 數(shù)值

29、部分由于小數(shù)點總是在符號位與最高數(shù)據(jù)位之間，因此在計算機中不明確表示出來定點整數(shù)格式：小數(shù)點位置固定在最低數(shù)據(jù)位的右邊。整數(shù)又分為帶符號和不帶符號的兩類。帶符號的整數(shù)，符號位安排在最高（最左）位。NsNn-1Nn-2N1N0·符號位 n位數(shù)值 小數(shù)點由于小數(shù)點固定在最低數(shù)據(jù)右邊，因此在計算機中不明確表示出來。n位帶符號整數(shù)N=NsNn-1Nn-2N1N0在計算機中用n+1位二進制表示。對于不帶符號的整數(shù)，把所有n+1位二進制位全部視為數(shù)值。在不同計算機中，使用多種位數(shù)的整數(shù)。16位，32位，64位，64位二進制來表示一個整數(shù)。2 數(shù)的浮點表示法浮點數(shù)是指小數(shù)點數(shù)據(jù)中的位置可以左右移動

30、的數(shù)。一個數(shù)N要用浮點數(shù)表示可以寫：N=M*REM：浮點數(shù)的尾數(shù)。E：浮點數(shù)的指數(shù)或階碼。R：浮點數(shù)的基數(shù)，是常數(shù)一般取2、8或16一旦機器的浮點部件設計好了，基數(shù)的大小也就確定了，不能再改變了，基數(shù)在浮點數(shù)表示中不出現(xiàn)，是隱含的。浮點數(shù)的表示方法：EsEmE2E1MsMnM2M1階符階碼 數(shù)符數(shù)碼M：尾數(shù)。用定點小數(shù)表示，表示浮點數(shù)的有效位，其位數(shù) n的大小決定了浮點數(shù)的精度。E：階碼。用定點整數(shù)表示。階碼用于表示小數(shù)點在浮點數(shù)中的位置。其位數(shù)m的大小反映此浮點數(shù)所能表示的數(shù)的范圍。浮點數(shù)的規(guī)格化：規(guī)定計算機內(nèi)浮點數(shù)的尾數(shù)用純小數(shù)形式給出，而且當尾數(shù)的值不為0時，其絕對值應大于或等于0.5，

31、不符合這一規(guī)定的浮點數(shù)要進行規(guī)格化。（通過修改階碼的大小并同時左右移尾數(shù)的辦法使其滿足要求。）正數(shù)：1/2S1，二進制表示S=0.1負數(shù)：-1/2S-1，二進制表示S=1.1機器零：尾數(shù)為0，不論其階碼為何值。階碼的值遇到比它所能表示的最小值還小時，不管尾數(shù)為何值。_階碼、尾數(shù)全變成0。浮點數(shù)常用格式：符號位階碼尾數(shù)總位數(shù)短浮點數(shù)：182332長浮點數(shù)：1115264臨時浮點數(shù)：1156480二、 二進制數(shù)值數(shù)據(jù)的編碼方法編碼方法是研究在計算機中如何方便的表示定點小數(shù)，定點整數(shù)和浮點數(shù)的正數(shù)、負數(shù)和零。最常用的編碼方法有原碼表示法、補碼表示法、反碼表示法三種。我們以定點小數(shù)為例：原碼表示法：1

32、、定義：用機器數(shù)的最高（左）一位代表符號，其余各位給出數(shù)值（真值）的絕對值。X (0X1)X原=1-X (-1X0)1+|X|例：X1=0.1011 X2=-0.1011X1原=01011 X2原=11011符號 數(shù)值 符號 數(shù)值2真值零的原碼表示法+0原=00000-0原=100003原碼表示的范圍如果用 n位二進制表示定點小數(shù)，其中一位符號位。最大數(shù)：+(1-2-(n-1)最小數(shù)：-(1-2-(n-1)原碼編碼個數(shù)：2n-1 0點兩個編碼例n=8最大數(shù)：01111111對應1-2-(8-1)=1-0.0000001=0.1111111=127/128最小數(shù)：11111111對應-(1-2-

33、(8-1)=-0.1111111=-127/128反碼表示法1、 定義：用機器數(shù)的最高一位代表符號，數(shù)值位是對負數(shù)值各位取反的表示方法。取反01 10 X(0X1)X反=(2-2-n)+X (-1X0)例： X1=0.1011 X1反=01011X2=-0.1011 X2反=10100把任何一個二進制負數(shù)的絕對值與它的反碼相加，得到的和永遠1.1111，若在最后位上加1,恒等于2。2、 真值零的反碼表示法+0反=00000 -0反=11111反碼同原碼一樣，零的表示不是唯一的，有兩個。補碼表示法1、 模的概念例：11點6點往回撥5格 11-5=6往前撥7格 11+7=18 18-12=6舍掉進

34、位的情況下：從11點中減去5和往11上加7結(jié)果是一樣的。例：9-3=69+7=16 16-10=6 （十進制）而7=12-5 對于12進制計數(shù)的基數(shù)12（模數(shù)）7是5對于12的補碼。7=10-3 對于10進制計數(shù)的基數(shù)10（模數(shù)）7是3對于10的補碼。在計算機中，機器表示的數(shù)據(jù)字長是固定的，對于n位數(shù)來說，模數(shù)大小是n位數(shù)全為1，且在最末位再加1。實際上模數(shù)的值已超出計算機所能表示的數(shù)的范圍，因此模數(shù)在機器中是表示不出來的，若運算結(jié)果大模數(shù)，則模數(shù)自動丟掉。如果是n位整數(shù)（包括符號位），則它的模數(shù)是2n,若n位小數(shù)，則它的模數(shù)總是2。同理：在二進制定點小數(shù)減法運算中，減去一個二進制數(shù)，也可以化

35、為加上這個數(shù)對于模數(shù)2的補碼。2、 定義：用機器數(shù)的最高（左）一位表示符號位，其余各位給出負數(shù)數(shù)值按2取模的結(jié)果。X (0 X1)X補=2+X ( -1X0)2-|X|例：X1=0.1011 X1補=01011X2=-0.1011 X2補=10101=10-0.10113、真值零的補碼表示法+0補=00000-0補=10-0.0000=00000+0補=-0補4、在補碼表示法中數(shù)的表示范圍定點小數(shù)：最大：1-2-(n-1)最小：-1 -1補=10-1.0000=10000n=8 最大：1-2-7=0.1111111 補碼01111111最?。?1 補碼10000000由于在補碼表示法中零有唯一

36、的編碼，n位二進制能表示2n個補碼數(shù)。5、補碼的求法1、 從反碼求補碼|X|+X反+0.0001=10X反+0.0001=10-|X|=X補、從原碼反碼補碼、補碼原碼除符號位外反轉(zhuǎn)，再在未位加1。小結(jié)1、如果真值X為正數(shù)，則X原=X補=X反2、如果真值X為負數(shù)，X原、X補、X反表示不同。3、如果X=0，則X補有唯一編碼，X原有兩個不同表示方法，X反有兩個不同表示方法。4、在定點小數(shù)中，原碼和反碼的表示范圍為-1X1補碼的表示范圍為-1X1三、 整數(shù)的編碼方法可用原碼、補碼、反碼三種方法進行編碼。1、 整數(shù)的編碼方法與小數(shù)的編碼方法的區(qū)別小數(shù)點位置表示范圍模數(shù)的差別2、 整數(shù)的編碼方法四、 浮點

37、的編碼方法EsEMsMM部分采用定點小數(shù)形式，可以用原碼表示，也可以用補碼表示。階碼多采用整數(shù)形式的移碼表示。1、 移碼的表示方法移碼定義X移=2n+X -2nX2n將這一定義與整數(shù)補碼相比較 X 0X2nX補= 2n+1+X -2nX0當0X2n時，X移=2n+X=2n+X補當-2nX0時，X移=2n+X=(2n+1+X)-2nX移是將X補的符號位變反。例：X=+1010101 X補=01010101 X移=11010101 X=-1010101 X補=10101011 X移=001010112、 移碼的特點：符號位在最高位，正用1表示，負用0表示。五、 ASCII碼和BCD碼ASCII碼在

38、人們通常接觸和處理信息中，有相當一部分是用字符或字符的組合來表示的。字符是指字母、數(shù)字以及其它一些可打印顯示的符號。計算機和外部設備之間進行通訊聯(lián)系時，還需要一些控制功能的特殊符號。例如，控制打印機的走紙符、換行符等。在計算機內(nèi)部，上述字符必須用一種二進制代碼來表示。日前，在國際上廣泛采用的是美國標準信息交換代碼（American Standard Code for Information Interchange），簡稱ASCII碼。ASCII碼是7位二進制編碼，它可以表示27=128個字符。由于標準的7位ASCII碼所能表示的字符較少，不能滿足有些信息處理的需要，于是在ASCII碼地基礎上又

39、設計了一種擴充的ASCII碼。擴充的ASCII碼是一種8位二進制編碼，它可以表示256個字符。BCD碼十進制數(shù)在鍵盤輸入和打印時，往往是將各個數(shù)字以ASCII碼來表示的。但是它在計算機內(nèi)運算時，是以二進制形式進行的。為了便于轉(zhuǎn)換，設計了一些二進制編碼來表示十進制數(shù)，稱為二十進制碼，即BCD碼（Binary Coded Decimal）。BCD碼是用四位二進制代碼來表示一位十進制數(shù)。從16個四位二進制代碼00001111中，只須選擇其中10個作為十進制數(shù)的10個數(shù)字的代碼就可以了。這樣就有多種BCD碼：如8421碼、2421碼、余3碼和格雷碼等。十進制數(shù)字8421碼2421碼余3碼格雷碼0000

40、0000000110000100010001010000012001000100101001130011001101100010401000100011101105010101011000111060110011010011010701110111101010008100011101011110091001111111000100由于8421碼最常用，因此通常就把它稱為BCD碼。例如，十進制數(shù)315用BCD碼表示為001100010101。注意：用BCD碼表示的數(shù)，形式上像二進制數(shù)，但不是真正的二進制數(shù)。例如，315轉(zhuǎn)換成二進制數(shù)是100111011B。在計算機中，可以把用BCD碼表示的十進制

41、數(shù)轉(zhuǎn)化成真正的二進制數(shù)后，再進行運算，也可以直接對用BCD碼表示的十進制數(shù)進行計算。但需要進行“十進制調(diào)整”，以符合“逢十進一”的十進制運算規(guī)則。PASCAL程序設計初步PASCAL從1971年正式推出至今，已成為世界上最廣泛使用的程序設計語言之一，PASCAL語言全面地體現(xiàn)了結(jié)構(gòu)化程序設計的概念，具有豐富完備的數(shù)據(jù)類型、簡明靈活的語句和清晰明了的模塊結(jié)構(gòu)，書寫格式自由，運行效率高，查錯能力強，移植性好，程序設計風格優(yōu)美，有助于養(yǎng)成結(jié)構(gòu)化程序設計的良好習慣。我們選擇的是Turbo Pascal 6.0的版本的教材。要使用計算機解決實際問題，除了會理解題目和設計算法外，關鍵的一點就是要會編寫程序

42、。程序其實就是用計算機語言來表述我們所設計的算法過程。計算機語言與我們的語言相類似，有著多種多樣的語言，不過這些語言最終的目的都是一致的，都是為了讓計算機看懂我們所設計的得算法。一 Pascal 程序形式：Program 程序名（程序參數(shù)表）；說明部分程序體1 每一個完整語句由分號結(jié)束。2 具體程序不一定包括全部說明，但如果出現(xiàn)，必須按這里所指定的前后次序編寫。3 程序體不可少，程序體以END.結(jié)束，且最后一個句號不能漏掉。4 END前一句語句的分號可有可無，有則編譯時多一個空行。Label 標號說明；Const常量說明；Type類型說明；Var變量說明；Function函數(shù)說明；Proced

43、ure過程說明；Begin程序語句；程序語句；End.二 基本程序結(jié)構(gòu)和幾個概念:例：program pname;const n=4;type ar=array 1.4 of integer;var i:integer; a:ar;begin for i:=1 to n do read(ai); readln; for i:=n downto 1 do write(ai:4); writeln;end. 以上是一個PASCAL程序。從鍵盤讀入4個數(shù)據(jù)，逆序輸出。 一般來說，一個PASCAL程序包括以下幾個部分： 程序頭：program pname; 其中，program是保留字，表示程序從這個

44、地方開始，pname是標識符，是程序的名字，可由程序員自定。保留字是PASCAL選定的，具有固定意義和用法的專用單詞或縮寫，這些單詞不允許作其它使用。如上，“program”就有“程序從這里開始”這樣一種特別的意義，而“const”就有“常量說明從這里開始”的意義。我們不能再用“program”、“const”來作為其它變量、常量等的名字。標識符是以字母開頭的字母數(shù)字串。用來表示常量、變量、類型、文件、過程、函數(shù)和程序的名字。如“pname”、“i”、“j”、“a1”就是合法的標識符；但“1a”、“#a”是非法的標識符。有一點要注意的是，在PASCAL中，字母除了作為字符值或字符串值之外，其大

45、小寫是無關的。如標識符“A1”和“a1”在PASCLA看來是同一標識符。在PASCAL中除了保留字和自定義的標識符外，還有一類有特殊含義的標識符，這類標識符稱為標準標識符。它們是用來標記程序中經(jīng)常引用的處理對象，如常量、函數(shù)。（PASCAL定義的保留字和標準標識符附后） 標識符在命名的時候要注意：1、名字要易記易讀，有意義。如8皇后問題程序名可以是“queen”也可以是“huanghou”等；2、不能用保留字、標準標識符作為自定義的標識符。 說明部分：const n=4; type ar=array 1.4 of integer; var i:integer; a:ar; 其中，const部分

46、是常量說明，說明一些在以下部分用到的，在整個程序執(zhí)行過程不改變值的量。這些量PASCAL稱為常量。在程序中用到這個值的地方均用常量名來代替。如上題中定義“n=4”指本程序處理4個數(shù)值，在下面的程序體中就用“n”來代替具體的值（如for i:=1 to n）。如果要改變處理數(shù)據(jù)個數(shù)，則只在常量說明部分修改“n=4”這一句就行了，而不用在程序中每一個用到的地方都加以修改。這樣不但在編寫程序的時候很方便，也增加了程序的可讀性，修改時更方便。 常量說明在保留字“const”下開始。可以有多個語句。常量說明語句的格式是：“常量名=值；”。如“n=4；”。n是常量名，4是該常量的值，“；”是語句分隔符。

47、type部分是類型說明，說明一些在以下部分用到的數(shù)據(jù)類型。如數(shù)組、記錄、指針等。 類型說明在保留字“type”下開始?？梢杂卸鄠€語句。類型說明語句的格式是：“類型名=類型說明；”。如“ar=array 1.4 of integer；”。ar是類型名，array 1.4 of integer是類型說明，“；”是語句分隔符。 var部分是變量說明。變量是指在程序執(zhí)行過程中可以通過賦值語句或讀語句來改變值的量。所有在程序中使用的變量都應該先在變量說明部分說明。PASCAL中引用的每個變量都有“名字”和“類型”屬性。變量說明“說明”的主要工作是告訴PASCA下面程序中要用到這個名字的量，同時這個量的類

48、型是什么。 變量說明在保留字“var”下開始?？梢杂卸鄠€語句。變量說明語句的格式是：“變量名：變量類型；”。其中，如果有多個變量同一類型，則變量名與變量名之間用逗號分隔，變量名與變量類型之間用冒號分隔。如“i：integer；”（i是變量名，integer是類型名）、“i、j：integer；”（i、j是變量名，integer是類型名） 變量說明要注意：1、變量名稱必須以字母開頭；2、在同一個有效范圍內(nèi)變量名稱必須唯一。 各個說明部分均以該部分的保留字開始。如“const”開始常量說明；“type”開始類型說明；“var”開始變量說明。一個程序包含多少種類型的說明，看需要而定，不是每一個程序都必須同時包含這三種說明。如果程序不須要用到常量，則常量說明部分可以省略；如果不須要用到類型說明，則類型說明可省 PASCAL還有一條規(guī)則：先說明后引用。即所有在程序體中用到的“名字”必須都在說明部分說明過才能引用，否則就會出錯，通不過編譯，也執(zhí)行不了。如上，類型“ar”先在類型說明中定義，然后在變量說明中引用；變量i在變量說明中定義，在程序中引用。 程序體：begin for i:=1 to n do read(ai); readln; for i:=n downt