信息學奧賽初賽全部知識

1、信息學奧林匹克信息學奧林匹克分區(qū)聯(lián)賽的基礎知識分區(qū)聯(lián)賽的基礎知識 初賽試題結構初賽試題結構第一部分 基礎知識第二部分 問題求解第三部分 閱讀程序第四部分 完善程序第一部分 一、計算機的發(fā)展與應用 二、計算機概述 三、多媒體技術應用 四、計算機網絡使用基礎 一、計算機的發(fā)展與應用 一、計算機的發(fā)展與應用1、下面列出的四項中，不屬于計算機病毒特征的是( ) A潛伏性 B激發(fā)性 C傳播性 D免疫性2、國產銀河型數字式電子計算機是屬于下列哪種類型計算機( ) A微型 B小型 C中型 D巨型3、計算機病毒是指( ) A能傳染給用戶的磁盤病毒 B已感染病毒的磁盤 C具有破壞性的特制程序 D已感染病毒的程序

2、4、最早的計算機的用途是用于( ) A科學計算 B自動控制 C輔助設計 D系統(tǒng)仿真5、操作系統(tǒng)在第幾代計算機開始應用( ) A第一代 B第二代 C第三代 D第四代第二代晶體管計算機(1956-1963) 1948年，晶體管的發(fā)明大大促進了計算機的發(fā)展，晶體管代替了體積龐大電子管，電子設備的體積不斷減小。1956年，晶體管在計算機中使用，晶體管和磁芯存儲器導致了第二代計算機的產生。第二代計算機體積小、速度快、功耗低、性能更穩(wěn)定。首先使用晶體管技術的是早期的超級計算機，主要用于原子科學的大量數據處理，這些機器價格昂貴，生產數量極少。 1960年，出現(xiàn)了一些成功地用在商業(yè)領域、大學和政府部門的第二代

3、計算機。第二代計算機用晶體管代替電子管，還有現(xiàn)代計算機的一些部件還有現(xiàn)代計算機的一些部件:打印機、磁帶、磁盤、打印機、磁帶、磁盤、內存、操作系統(tǒng)內存、操作系統(tǒng)等。等。計算機中存儲的程序使得計算機有很好的適應性，可以更有效地用于商業(yè)用途。在這一時期出現(xiàn)了更高級的COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等語言，以單詞、語句和數學公式代替了含混晦澀的二進制機器碼，使計算機編程更容易。新的職業(yè)(程序員、分析員和計算機系統(tǒng)專家)和整個軟件產業(yè)由此誕生。 1 什么是CISC機？什么是RISC機？2 計算機的發(fā)展

4、分為幾個階段？正在研制的新型計算機具有哪些特點？3 簡述“三金”工程的含義。4 什么是計算機病毒，它具有哪些特征，如何采取具體的防范措施？資 料CISC微處理器是臺式計算機系統(tǒng)的中心，這個核心中的核心就是運行指令的電路。指令由完成任務的多個步驟所組成，例如把數值傳送進寄存器或進行相加運算，都是需要指令的，這些指令被稱為微代碼（microcode），不同制造商的微處理器有不同的微代碼系統(tǒng)，制造商可按自己的意愿使微代碼做得簡單或復雜。指令系統(tǒng)越豐富，微處理器編程就越簡單，然而，執(zhí)行速度也相應越慢，而且設計這樣的處理器的代價也就越大，但是由于指令系統(tǒng)豐富，對上層的支持就比較好。下面我們來看看兩種處理

5、器的比較： 復雜指令系統(tǒng)計算機（CISC）包含一個豐富的微代碼系統(tǒng)，簡化了處理器上運行程序的編制。 精簡指令系統(tǒng)計算機（RISC）有一個精簡的指令系統(tǒng)。從而提高了微理器的效率，但需要更復雜的外部程序，也就是把在處理器層沒有完成的工作放到了上層進行，而處理器層少的這些成本可以用對物理器件速度的提高上去。RISC方案基于John Cocke在IBM公司的工作，他發(fā)現(xiàn)約20的計算機指令完成約80的工作。因此，RISC系統(tǒng)通常比CISC系統(tǒng)要快。他的8020規(guī)則促進了RISC體系結構的開發(fā)。大多數臺式微處理器方案如Intel和Motorola芯片都采用CISC方案；工作站處理器加MIDS芯片DEC A

6、lpha和IBM RS系列芯片均采用RISC體系結構。將來的處理器會在RISC和CISC之間尋找到一條合適的途徑來保證處理器的成本較小，而且功能比較合適。 二、計算機概述1. 世界上首先實現(xiàn)存儲程序的電子數字計算機是（ ）。 AENIAC B、UNIVAC C、EDVAC D、EDSAC2、計算機能直接執(zhí)行的指令包括兩部分，它們是( ) A源操作數與目標操作數 B操作碼與操作數 CASCII碼與漢字代碼 D數字與字符3、下列諸因素中，對微機工作影響最小的是( ) A塵土 B噪聲 C溫度 D濕度4、在計算機中，ASCII碼是幾位二進制代碼( ) A7 B8 C12 D165、下面四個不同進制的數

7、，最小的一個數是( ) A(11011001)2 B(37)8 C(75)10 D(A7)16 資 料1 簡述馮諾依曼型計算機的組成與工作原理。2 計算機硬件系統(tǒng)由哪五個基本部分組成？它們各自的功能是什么？3 機器指令由哪幾部分組成？按其功能分為哪幾種指令類型？4.在計算機中，帶符號數有幾種表示方法？它們之間的轉換關系是什么？各自有什么用途？5 ASCII碼由幾位二進制數組成？它能表示什么信息？6 二進制的計算規(guī)則。 三、多媒體技術應用1彩色顯示器所顯示的五彩斑斕的色彩，是由哪三色混合而成的（ ）。 A. 紅 B. 白 C. 藍 D. 綠 E. 橙2下面哪個部件對于個人桌面電腦的正常運行不是必

8、需的（ ）。 A.CPU B. 圖形卡（顯卡） C. 光驅 D. 主板 E. 內存3.下列哪個（些）不是個人計算機的硬件組成部分（ ）。A.主板 B.虛擬內存 C.電源 D.硬盤 E.總線4.一個文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角則以（80，25）表示，屏幕上每一個字符占用兩字節(jié)（byte），整個屏幕則以線性方式存儲在電腦的存儲器內，屏幕左上角開始，位移為0，然后逐列逐列存儲。求位于屏幕（X，Y）的第一個字節(jié)的位移是（）A.（Y*80+X）*2-1B.（Y-1）*80+X-1）*2C.（Y*80+X-1）*2D.（Y-1）*80+X）*2-11. 多媒體計算機系統(tǒng)

9、的基本配置包含了哪些設備？2 CD-ROM的功能大小取決于哪幾個參數？3 顯示存儲空間由哪幾個主要的因素決定？4 目前國際上有哪幾種壓縮數據的標準？資 料 四、計算機網絡使用基礎1、Internet的規(guī)范譯名應為( ) A英特爾網 B因特網 C萬維網 D以太網2、下列哪些計算機網絡不是按覆蓋地域劃分的( d ) A局域網 B都市網 C廣域網 D星型網3、以下列舉Internet的各種功能中，錯誤的是( ) A編譯程序 B傳送電子郵件 C查詢信息 D數據庫檢索4、計算機網絡最突出的優(yōu)點是( ) A傳送信息速度高 B共享資源 C內存容量大 D交互性好5、TCPIP協(xié)議共有( )層協(xié)議 A.3 B.

10、4 C.5 D.6 1 什么是WAN網？什么是LAN網，他們各自的功能是什么？2 什么是計算機網絡的拓撲結構？常見的拓撲結構有幾種？3. 什么是計算機網絡協(xié)議？說出OSI 的七層協(xié)議的名稱。4. 在Internet中，IP地址和域名的作用是什么？它們之間有什么異同？資 料第二部分 數學知識 組合、排列、集合等 數據結構 圖、樹等第三部分 閱讀程序 直接推理 有流程圖推斷算法 動態(tài)模擬 由底向上閱讀分析例一Var m,n,i:integer; t:extended;Begin read(n,m); t:=1; for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:

11、0:0);End.輸入：10 5輸出：1045120210252例二Label 10,20,30;Var s,p:string;I,k,n,j,m:integer;Begin readln(s);n:=length(s); readln(p);m:=length(p); i:=0;10: i:=i+1;j:=I;k:=1;例二（續(xù)）20: If s j p k then begin if in-m+1 then goto 10; i:=0; goto 30; end else if kmax then begin _(3)_; p1:=I;q1:=j;end; end;For i:=p1 to

12、 _(4)_ doBegin for j:=q1 to _(5)_do write(aI,j:3);writeln;end;readln end.例二例二Const maxm=10000;Var I,k,m,n,rest,start,temp:longint; a:array0.maxm of longint;Begin write(input m,n:); readln(m,n); for i:=0 to m-1 do ai:=random(100); writeln(before move); for i:=0 to m-1 do write(ai:5);writeln; rest:=m;

13、start:=0; while _(1)_do begin k:=start; repeat k:=(k+n) mod m until k=n; if b=n then find:=_(2)_ else find:=_(3)_End;例（續(xù)）例（續(xù)）Procedure p(n:integer);Var a:integer; begin a:=find(n); if first then begin write(a:4);first:=false;end else write(+,a:4); if a=0; X補=2(n+1)+X， 當-2n=X=1例如：X=+100101 X補=0 10010

14、1 X=100101 X補=1 011011特點:1.補碼的和等于和的補碼補碼的和等于和的補碼,符號位和數值位一樣參加符號位和數值位一樣參加運算運算,不必單獨處理不必單獨處理,即即 X補補+Y補補=X+Y補補 2.補碼相減: X補-Y補=X補+-Y補 Y補-Y補: 符號位連同數值位一起取反加1 3表示范圍：-128-+127 反碼表示法 當X=0時，X反=X 當X=0時，符號位為1，其余各位取反。 特點: 1.反碼的和等于和的反碼 2.有二個零 +0=000 -0=111 3.當最高位有進位而丟掉進位(即2)時,要在最低位加1(循環(huán)進位) 表示范圍：-127-+127原碼,反碼和補碼之間的轉換

15、 X反 符號位不變符號位不變數值位 不變不變(符號位為0) 變反(符號位為1) +,0,1 X真值 X原數值位不變數值位不變 數值位不變不變(符號位為0) 變反加1(符號位為1) 符號位不變符號位不變 X補當當X為正數，為正數，X反反=X原原=X補補=X，當當X為負數時，為負數時，X補補=X反反+1，X補補=X原原2 . 5 ASCII碼 ASCII碼是美國信息交換標準代碼的縮略語。是目前國際上最為流行的字符信息編碼方案。它包括數字09、大小寫字母和專用符號等95種可打印字符，還有33種控制字符。 一個字符ASCII碼通常占一個字節(jié)，用七位二進制編碼組成，ASCII碼最多可表示128個不同的符

16、號。字節(jié)的最高位被很多系統(tǒng)用做校驗碼，以便提高字符信息傳輸的可靠性。2 . 12 漢字信息編碼 3、漢字交換碼 （1）區(qū)位碼：GB2312-80信息交換用漢字編碼字符集，組成一個94*94的矩陣。每一行稱為一個區(qū)，每一列稱為一個位。一個漢字的區(qū)號和位號合在一起構成區(qū)位碼 （2）漢字交換碼（國標碼,GB2312-80 ）：國標碼收入6763個漢字，其中一級漢字（最常用）3755個(按拼音排序)，二級漢字3008個(按部首排序)，另外還包括682個西文字符、圖符。區(qū)位碼（十進制）的兩個字節(jié)分別轉換為十六進制后加20H 轉換成國際碼。 4、漢字機內碼：是計算機系統(tǒng)中對漢字的一種運行代碼，系統(tǒng)內部的存

17、儲、傳輸都是對機內碼進行的。它也和漢字存在著一一對應的關系。機內碼也占兩個字節(jié)，且最高位為1。同一個漢字，在同一種漢字操作系統(tǒng)中，內碼是相同的。 漢字機內碼是漢字交換碼兩個字節(jié)的最高位分別加1，即漢字交換碼的兩個字節(jié)分別加80H；或區(qū)位碼（十進制）的兩個字節(jié)分別轉換為十六進制后加A0H。 由于由于GB231280是是80年代制定的標準，在實際應用時常年代制定的標準，在實際應用時常常感到不夠，所以，建議處理文字信息的產品采用新頒布常感到不夠，所以，建議處理文字信息的產品采用新頒布的的GB18030信息交換用漢字編碼字符集，這個標準繁、信息交換用漢字編碼字符集，這個標準繁、簡字均處同一平臺，可解決

18、兩岸三地間簡字均處同一平臺，可解決兩岸三地間GB碼與碼與BIG5碼間碼間的字碼轉換不便的問題。的字碼轉換不便的問題。 字形存儲碼是指供計算機輸出漢字（顯示或打?。┯玫亩中未鎯Υa是指供計算機輸出漢字（顯示或打?。┯玫亩M制信息，也稱字模。通常，采用的是數字化點陣字模，進制信息，也稱字模。通常，采用的是數字化點陣字模，有有1616，2424，6464等，每一個點在存儲器中用等，每一個點在存儲器中用一個二進制位（一個二進制位（bit）存儲。例如，在）存儲。例如，在1616的點陣中，的點陣中，需需832 bit 的存儲空間，每的存儲空間，每8 bit為為1字節(jié)，所以，需字節(jié)，所以，需32字字節(jié)的存儲

19、空間。在相同點陣中，不管其筆劃繁簡，每個漢節(jié)的存儲空間。在相同點陣中，不管其筆劃繁簡，每個漢字所占的字節(jié)數相等。字所占的字節(jié)數相等。 2 . 6 二進制 采用二進制，優(yōu)點：（1）易于物理實現(xiàn)（2）二進制運算簡單（3）機器可靠性高（4）通用性強乘法 除法 整數轉換 小數轉換0+0=0 0+1=1 1+0=1 1+1=100*0=0 0*1=0 1*0=0 1*1=1數的定點表示和浮點表示(1) 定點小數格式任何一個M位的小數可以表示成：N=Ns . N-1N-2N-m (其中Ns 是符號位，其值表示的范圍|N|=1-2-m)(2) 定點整數格式任何一個N位帶符號的整數都可表示為：N=Ns Nn-

20、1Nn-2N0 (其中Ns 是符號位，其值表示的范圍|N|=2n-1)(3) 數的浮點表示浮點數是指小數點在數據中的位置可以左右移動的數。一個數N要用浮點表示可以寫成：N=MRE 其中M表示浮點數的尾數,E表示浮點數的指數或稱為階碼,R指的是在這個指數下的基數。浮點數通常表示成如下格式：1位 m位 n位M：浮點數的尾數，用定點小數表示，小數點在尾數最高位之前，是默認的。尾數用于表示浮點數的有效位，其位數N的大小反映了此浮點數的精度。E：浮點數的階碼，用定點整數表示。Ms：浮點數的符號位，也就是尾數的符號位，一般放在整個浮點數的最高位MsEM 信息在計算中的存儲地址所有的存儲單元都按順序排列，計

21、算機中以一個字節(jié)為單位處所有的存儲單元都按順序排列，計算機中以一個字節(jié)為單位處理，所以計算機對每個存儲單元進行了編號，這種編號稱為單理，所以計算機對每個存儲單元進行了編號，這種編號稱為單元地址。通過地址編號尋找在存儲器中的數據單元稱為元地址。通過地址編號尋找在存儲器中的數據單元稱為尋址尋址1、地址編號：用二進制數編碼，存儲器的總容量決定了地址的范地址編號：用二進制數編碼，存儲器的總容量決定了地址的范圍，也決定了地址編號的二進制數位數。圍，也決定了地址編號的二進制數位數。如存儲器的總容量為如存儲器的總容量為64MB，那么它的地址編碼為，那么它的地址編碼為0 64220-1；對應的二進制數是；對應

22、的二進制數是00 0000 0000 0000 0000 0000 000011 1111 1111 1111 1111 1111 1111；對應的十六進制；對應的十六進制數是數是00000003FFFFFF；需要用；需要用26位二進制來表示，也就是位二進制來表示，也就是需要需要26根地址線。根地址線。2、地址和容量的計算、地址和容量的計算（1）由地址線，求尋址空間。）由地址線，求尋址空間。若地址線有若地址線有32根，則它的尋址空間為根，則它的尋址空間為 232B = 222 KB = 212 MB = 4GB（2）由起始地址和末地址，求存儲空間。）由起始地址和末地址，求存儲空間。若編號為若編

23、號為4000H 4FFFH的地址中，包含的單元數的計算：的地址中，包含的單元數的計算：方法一：用十六進制計算。方法一：用十六進制計算。4FFFH4000H =FFFH1 = 1000H = 1 163 = 4096 =4KB方法二：轉換成十進制計算。方法二：轉換成十進制計算。4FFFH4000H =2047916384=4096=4KB（3）由存儲容量和起始地址，求末地址。）由存儲容量和起始地址，求末地址。若存儲器的容量若存儲器的容量32KB，地址起始編號為，地址起始編號為0000H， 末地址的計算：末地址的計算：方法一：用十六進制計算。方法一：用十六進制計算。0000H+32KB1H =00

24、00H+32 10241H =0000H+8000H1H= 7FFFH方法二：轉換成十進制計算。方法二：轉換成十進制計算。0+32KB1= 0+327681 = 32767=7FFFH方法三：轉換成二進制計算。方法三：轉換成二進制計算。0000 H +32KB1 H = 0000 H +32 2101 H= 0000 H +2151 H=0000 0000 0000 0000 B+ 1000 0000 0000 0000 B 0000 0000 0000 0001 B=0111 1111 1111 1111 B=7FFFH3 . 2 CD-ROM 光驅的技術指標光驅的技術指標(1)數據傳輸率(

25、Data Transfer Rate),即大家常說的倍速，它是衡量光驅性能的最基本指標。單倍速光驅就是指每秒可從光驅存取150KB數據的光驅?，F(xiàn)在年青一代的40或48倍速光驅每秒鐘能讀取6000KB和7200KB的數據。(2)平均尋道時間(AverageAccessTime),平均尋道時間是指激光頭（光驅中用于讀取數據的一個裝置）從原來位置移到新位置并開始讀取數據所花費的平均時間，顯然，平均尋道時間越短，光驅的性能就越好。(3)CPU占用時間(CPULoading)，CPU占用時間是指光驅在維持一定的轉速和數據傳輸率時所占用CPU的時間，它也是衡量光驅性能好壞的一個重要指標。CPU占用時間越少

26、，其整體性能就越好。 (4)數據緩沖區(qū)(Buffer)，數據緩沖區(qū)是光驅內部的存儲區(qū)。它能減少讀盤次數，提高數據傳輸率?，F(xiàn)在大多數光驅的緩沖區(qū)為128K或256K。3 . 3 顯示存儲空間 顯示存儲空間 =水平分辨率垂直分辨率色彩數目例如，若采用640 480，16色顯示模式，只需要150KB的存儲空間。但是，如果想在1280 1024，16M色的顯示模式下運行，4MB的顯示存儲空間是不可能運行的。3 .4 壓縮標準 目前，國際上的壓縮技術標準有 JPEG，MPEG 和P 4。 JPEG適合于連續(xù)色調、多級灰度、彩色或單色靜止圖象數據壓縮的國際標準?？色@得10：1到80：1的壓縮比。 MPEG

27、包括MPEGeg:mp4視頻、 MPEGeg:MP3音頻和MPEG系統(tǒng)三部分，處理活動影象中的視頻壓縮、音頻壓縮，以及多種壓縮后數據流的復合和同步問題?？色@得50：1到00：1的壓縮比。 P 4目標是針對可視電話和電視會議的。適應各種通道容量的傳輸。4 . 1 廣域網和局域網 1、廣域網WAN（wide area network）是跨地域性的網絡系統(tǒng)，大多數WAN都是網絡互連而成的，如著名的Internet網絡。2、局域網LAN（Local Area Network）一般由一個部門或公司組建，地理范圍僅在建筑樓內或單位內部。3、城域網：可以看成是廣域網的一種。4 . 2 計算機網絡拓撲結構 網

28、絡中各個站點相互連接的方法和形式稱之為網絡拓撲。把向工作站、服務器等網絡單元抽象成為“點”，把網絡中的電纜等通信媒體抽象為“線”，從而抽象出了絡系統(tǒng)的具體結構，即為邏輯結構。網絡拓撲結構有：計算機網絡拓撲結構4.3 網絡協(xié)議 計算機通信協(xié)議指雙方在通信中所應共同遵守的約定。計算機通信協(xié)議精確地定了計算機在彼此通信時的所有細節(jié)。它規(guī)定每臺計算機發(fā)送每條信息的格式和含義，規(guī)定哪些情況下應發(fā)送那些特殊的信息，以及接受方的計算機所應作出什么反映等等。 OSI七層協(xié)議 主機A 主機B1 應用層 應用層 2 表示層 表示層 3 會話層 會話層 4 運輸層 運輸層 5 網絡層 網絡層 6 數據鏈路層 數據鏈

29、路層 7 物理層 物理層應用層協(xié)議表示層協(xié)議會話層協(xié)議運輸層協(xié)議網絡層協(xié)議鏈路層協(xié)議物理層協(xié)議4.4 IP地址 Internet中的每臺主機都被分配一個唯一的32位地址，即IP地址。該地址由網絡號和主機號兩部分組成，其中網絡號表示一個網絡，而主機號表示這個網絡中的一臺計算機。 IP地址由4個十進制數字字段組成, 字段之間用點分開, 4個字段中的每個數字在0255之間，如210.30.240.11。IP地址類型 IP地址按網絡規(guī)模的大小主要可分成三類: A類地址、B類地址、C類地址。A類的第一個字段的值在1126之間，一般用于大型網絡；B類的第一個字段的值在128 191之間，一般用于中型網絡或

30、網絡管理器，如路由器等；C類的第一個字段在值在191 233之間，一般用于小型網絡。 網絡地址數 網絡主機數 主機總數 A類 126 16,38 7,064 2,064,770,064 B類 16,256 6 4,516 1,048,872,096 C類 2,064,512 254 524,386,048域名 用用IPIP地址標識主機既沒有規(guī)律，又很難記憶，用戶地址標識主機既沒有規(guī)律，又很難記憶，用戶很難用數字表示的很難用數字表示的IPIP地址與計算機的情況聯(lián)系起來，地址與計算機的情況聯(lián)系起來，給訪問給訪問InternetInternet帶來了很大的不便如果采用域名系帶來了很大的不便如果采用域

31、名系統(tǒng)，就可以很好地解決這些問題。統(tǒng)，就可以很好地解決這些問題。 域名系統(tǒng)是由域名系統(tǒng)是由TCP/IPTCP/IP提供的一種服務，可以將域名提供的一種服務，可以將域名翻譯成相應的翻譯成相應的IPIP地址。域名系統(tǒng)采用層次結構，按地址。域名系統(tǒng)采用層次結構，按地理域或組織域進行分層，各層間用圓點地理域或組織域進行分層，各層間用圓點“. .” 隔隔開。在主機的域名表示中，從左向右，域名依次從開。在主機的域名表示中，從左向右，域名依次從小到大，例如在小到大，例如在中，最高域中，最高域名為名為cncn，次高域名為，次高域名為comcom，最后一個域名為，最后一個域名為easthumaneasthuma

32、n。數學相關題目 1（第八屆）在書架上放有編號為1，2，.n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當放回去時要求每本書都不能放在原來的位置上。例如：n=3時,原來位置為1 2 3,放回去時只能為： 3 1 2 或 2 3 1 這兩種。 問題：求當n=5時滿足以上條件的放法共有多少種?(不用列出每種放法) 2.(第九屆) 某年級學生共選修6門課程，期末考試前，必須提前將這6門課程考完，每人每天只在下午至多考一門課程，設6門課程為C1，C2，C3，C4，C5，C6，S(Ci)為學習Ci 的學生集合。已知S(Ci)S(C6)，i=1，2，.，5，S(Ci)S(Ci+1)，i=1，2，3，4，S(

33、C5)S(C1)，問至少安排_天才能考完這6門課程。題目 3(第七屆)平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形? 4（第十屆）已知a, b, c, d, e, f, g七個人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個人都能與他身邊的人交談？如果可以，請以“a b”開頭寫出你的安排方案： 。從n個不同元素中,任取m個元素,按照一定的順序排成一列,叫做從n個不同元素中取

34、出m個元素的一個排列.2.2.組合的定義組合的定義: :從n個不同元素中,任取m個元素,并成一組,叫做從n個不同元素中取出m個元素的一個組合.3.3.排列數公式排列數公式: :4.4.組合數公式組合數公式: :1.1.排列的定義排列的定義: :)!(!)1()2)(1(mnnmnnnnPmn排列與組合的區(qū)別與聯(lián)系排列與組合的區(qū)別與聯(lián)系: :與順序有關的為排列問題與順序有關的為排列問題, ,與順序與順序無關的為組合問題無關的為組合問題. .)!(!)1()2)(1(mnmnmmnnnnPPCmmmnmn例例1 1 學校師生合影，共8個學生，4個老師，要求老師在學生中間，且老師互不相鄰，共有多少種

35、不同的合影方式？解解 先排學生共有 種排法,然后把老師插入學生之間的空檔，共有7個空檔可插,選其中的4個空檔,共有 種選法.根據乘法原理,共有的不同坐法為 種.88P47P4788PP結論結論1 1 插入法插入法: :對于某兩個元素或者幾個元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.分析分析 此題涉及到的是不相鄰問題,并且是對老師有特殊的要求,因此老師是特殊元素,在解決時就要特殊對待.所涉及問題是排列問題.解 因為女生要排在一起,所以可以將3個女生看成是一個人,與5個男生作全排列,有 種排法,其中女生內部也有 種排法,

36、根據乘法原理,共有 種不同的排法.例2 5個男生3個女生排成一排,3個女生要排在一起,有多少種不同的排法? 33P66P3366PP結論2 捆綁法捆綁法: :要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內部也可以作排列.分析 此題涉及到的是排隊問題,對于女生有特殊的限制,因此,女生是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個元素來解決問題.解 把所有的硬幣全部取出來,將得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3個5分或1個5分與1個1角,所

37、以共有 種取法.例3 袋中有5分硬幣23個,1角硬幣10個,如果從袋中取出2元錢,有多少種取法?110123323CCC結論3 剩余法剩余法: :在組合問題中,有多少取法,就有多少種剩法,他們是一一對應的,因此,當求取法困難時,可轉化為求剩法.分析 此題是一個組合問題,若是直接考慮取錢的問題的話,情況比較多,也顯得比較凌亂,難以理出頭緒來.但是如果根據組合數性質考慮剩余問題的話,就會很容易解決問題.例4 學校安排考試科目9門,語文要在數學之前考,有多少種不同的安排順序?解 不加任何限制條件,整個排法有 種,“語文安排在數學之前考”,與“數學安排在語文之前考”的排法是相等的,所以語文安排在數學之

38、前考的排法共有 種.99P9921P結論4 對等法對等法: :在有些題目中,它的限制條件的肯定與否定是對等的,各占全體的二分之一.在求解中只要求出全體,就可以得到所求.分析 對于任何一個排列問題,就其中的兩個元素來講的話,他們的排列順序只有兩種情況,并且在整個排列中,他們出現(xiàn)的機會是均等的,因此要求其中的某一種情況,能夠得到全體,那么問題就可以解決了.并且也避免了問題的復雜性.例5 某個班級共有43位同學,從中任抽5人,正、副班長、團支部書記至少有一人在內的抽法有多少種?解 43人中任抽5人的方法有 種,正副班長,團支部書記都不在內的抽法有 種,所以正副班長,團支部書記至少有1人在內的抽法有 種.543C540C540543CC結論5 排異法排異法: :有些問題,正面直接考慮比較復雜,而它的反面往往比較簡捷,可以先求出它的反面,再從整體中排除.分析 此題若是直接去考慮的話,就要將問題分成好幾種情況,這樣解題的話,容易造成各種情況遺漏或者重復的情況.而如果從此問題相反的方面去考慮的話,不但容易理解,而且在計算中也是非常的簡便.這樣就