讀程序?qū)懡Y(jié)果(精華版).doc

讀程序?qū)懡Y(jié)果之基礎(chǔ)篇讀程序?qū)懡Y(jié)果，大致可以考察學(xué)生幾方面的能力：一是程序設(shè)計(jì)語言的掌握情況；二是相關(guān)算法的掌握情況；三是數(shù)學(xué)的知識面及運(yùn)算能力；四是細(xì)心、耐心的心理品質(zhì)。在NOIP初賽中所占的分值，近幾年一直維持在（48）分。對于參賽選手，又快又準(zhǔn)地完成這類題，顯得尤為重要。本系列文章將全面分析這類題的常用解題方法與技巧，敬請期待。本講，我們簡要說明一下閱讀程序?qū)懡Y(jié)果，或者說參與NOIP初賽，要了解并掌握的一些語言基礎(chǔ)（以Pascal語言為例），以及解決此類型題目的最基本解法。一、 Pascal相關(guān)知識備忘（以free Pascal 2.04為語言載體）熟練掌握并靈活使用以下Pascal語言相關(guān)知識：（一）、常用運(yùn)算：1、算術(shù)運(yùn)算：+、*、DIV、MOD2、字符串運(yùn)算：+ （字符串連接）3、集合運(yùn)算：+（并集）、*（交集）、一（差集）、in2、關(guān)系運(yùn)算：、=、=、=3、邏輯運(yùn)算：NOT、AND、OR、XOR（二）、常用子程序 1、 求絕對值函數(shù)abs(x) 如：abs(3)返回值為3；abs(-3.1)返回值為：3.12、 取整函數(shù)int(x) 定義：functionInt(X:Real):Real;如 int(3.6)返回值為：3.0；int(-3.6)返回值為：-3.03、 截尾函數(shù)trunc(x) 定義：functionTrunc(X:Real):Longint如 trunc(3.6)返回值為：3；trunc(-3.6) 返回值為：-34、 四舍五入函數(shù)round(x)如 R:=round(123.456);123 R:=round(12.56);13 R:=round(-123.456);-123 R:=round(-12.56);-135、 取小數(shù)函數(shù)frac(x)如R:=Frac(123.456);0.456; R:=Frac(-123.456);-0.4566、 求平方根函數(shù)sqrt(x)和平方函數(shù)sqr(x) 如：R:=sqrt(4);2.0; R:=sqr(4);167、 求以e為底冪函數(shù)exp(x) ： 8、 求以e為底對數(shù)函數(shù)ln(x) ： 9、 隨機(jī)數(shù)函數(shù)function random(range:word):randomize 隨機(jī)數(shù)初始化語句random 返回 之間的隨機(jī)實(shí)數(shù)random(range) 返回隨機(jī)整數(shù)10、 求字符x對應(yīng)序號函數(shù)ord(x) 如R:=ord(A);6511、 求序號x對應(yīng)字符函數(shù)chr(x) 如R:=chr(65);A12、 將字符串小寫轉(zhuǎn)換為大寫函數(shù)upcase(st) 如R:=upcase(AbcD);ABCD13、 求前趨函數(shù)pred(x) 如R:=pred(B);A14、 求后繼函數(shù)succ(x) 如R:=succ(B);C15、 判斷x是否為奇數(shù)函數(shù)odd(x) 如R:=odd(7);TRUE; 如R:=odd(8);FALSE16、 字符轉(zhuǎn)換為數(shù)值過程val(str,a,b)如，執(zhí)行語句val(2.4,a,b); 后，a值為：2.4 執(zhí)行語句val(2c4,a,b); 后，a為：0，b為：217、 數(shù)值轉(zhuǎn)換為字符過程Str（a,st）如，執(zhí)行語句str(12, st); 后，st值為：12 18、 求字串st長度函數(shù)length(st) 如R:=length(ABC);319、 函數(shù)Pos(st1,st)：查找st1在st里的起始位置，整型。如R:=pos(cd,abcde”); 320、 函數(shù)Copy(st,a,b)：提取st里第a個位置的b個字符。如R:=copy(abcdef,2,3);bcd21、 過程Delete(st,a,b)：刪除st中第a個位置的b個字符如，執(zhí)行語句:st=abcdef; delete(st,2,3);后，st值為：aef22、 過程Insert(st1,st,a)：把st1插入st的第a個位置中如，執(zhí)行語句:st=abcdef; insert(xy,st,3);后，st值為：abxycdef23、 過程Fillchar(x,y,a) ：按字節(jié)填充。常用Fillchar(a,sizeof(a),0)對數(shù)組的所有元素進(jìn)行清零。24、 過程Inc(i) 使i:=i+1;Inc(I,b) 使I:=I+b;25、 過程dec(i) 使i:=i-1; dec(I,b) 使I:=I-b;26、 EOF：判斷當(dāng)前打開的文件是否已到文件尾 27、 EOLN：判斷是否為行尾（三）、位運(yùn)算1、 SHR：x SHR n 把x換成二進(jìn)制后向右移n位2、 SHL：x SHL n 把x換成二進(jìn)制后向左移n位3、 and ：位與。（1可視為真；0為假）。在其它領(lǐng)域可用符號、表示。4、 or ：位或。在其它領(lǐng)域可用符號、+表示5、 xor：位異或。在其它領(lǐng)域可用符號表示6、 not：按位取反。在其它領(lǐng)域可用符號表示例：Var i,j:byte;begin i:=10; (10)10= (0000 1010)2 j:=12; (12)10= (0000 1100)2 writeln(i shr 2); (0000 1010)2向右移兩位，高位補(bǔ)零：(0000 0010)2，輸出2 writeln(i shl 2); (0000 1010)2向左移兩位，低位補(bǔ)零：(0010 1000)2，輸出40writeln(i and j); (0000 1010)2 (0000 1100)2=(0000 1000)2 ，輸出8 writeln(i or j); (0000 1010)2 (0000 1100)2=(0000 1110)2，輸出14 writeln(i xor j); (0000 1010)2 (0000 1100)2=(0000110)2 ，輸出6 writeln(not i); (0000 1010)2 =(1111 0101)2，輸出245 end.（四）、幾個語句及幾個符號1、 break：退出循環(huán)2、 continue：直接回到循環(huán)體頂部執(zhí)行3、 exit：退出當(dāng)前子程序。若是主程序，結(jié)束運(yùn)行。4、 halt：結(jié)束運(yùn)行，回到操作系統(tǒng)5、 記錄的定義及使用、開域語句with6、 指針的定義與使用： ：定義指向某類型的指針變量，該變量存放內(nèi)存地址。 取出該變量存放的內(nèi)存地址所指向內(nèi)存變量的值 ：取變量的內(nèi)存地址。常用于對指針變量賦值。這些最基本的語言基礎(chǔ)，是“讀程序?qū)懡Y(jié)果”的立根之本。只有熟練掌握這些語言基礎(chǔ)，才能看懂與之相關(guān)的程序。二、 基本解法NOIP初賽“讀程序?qū)懡Y(jié)果”有比較多的基礎(chǔ)題，特別是近三四年，經(jīng)常出現(xiàn)。這類題，只要在了解語言，特別是了解以上介紹的這些基礎(chǔ)知識，再通過“人腦模擬程序”的方式，進(jìn)行簡單的數(shù)學(xué)運(yùn)算，就可以得出答案?？疾榈氖沁x手對語言基礎(chǔ)的掌握情況，以及計(jì)算的細(xì)心與耐心。以下，選例講解：選例一 NOIP2008提高組第一題var i,a,b,c,d:integer; f:array0.3 of integer;begin解答過程如下： for i:=0 to 3 dof0f1f2f3 read(fi);9192939 a := f0 + f1 + f2 + f3;a=9+19+29+39=96 a := a div f0;a=96 div 9=10 b := f0 + f2 + f3;b=9+29+39=77 b := b div a;b=77 div 10=7 c := (b * f1 + a) div f2;c=(7*19+10) div 29=4 d := f(b div c) mod 4;d=f77 div 4 mod 4=f2=19 if (f(a + b + c + d) mod 4 f2) thenf(10+7+4+19) mod 4=f0 beginf0=929=f2 條件不成立 a := a + b; writeln(a); end else begin c := c + d;c=4+19=23 writeln(c);輸出答案 23 end;end.輸入：9 19 29 39 輸出：_簡析這種題，近三四年每年都出現(xiàn)，基本上可以說是增加選手信心的送分題。細(xì)心順著語句，簡單模擬一遍，答案自然就出來了。需要強(qiáng)調(diào)的是，解題過程中千萬別“看輕”這類題，掉以輕心、粗心大意。務(wù)必仔細(xì)認(rèn)真，特別是看清楚變量，不要張冠李戴、以桃代李。如果大家都能得分的，不小心失分了，那是最大的損失！建議，如上把解答的過程直接詳盡清晰地寫在程序的右邊，不容易錯，也便于檢查。選例二 NOIP2007提高組第二題program s402;var a,b:integer; x,y:integer;procedure fun(var a,b:integer);var k:integer;begin k:=a; a:=b; b:=k;end;begin a:=3; b:=6; x:=a; y:=b; fun(x,y); write(No.1:,a,b, ); fun(a,b); writeln(No.2:,a,b);end.輸出:簡析主要考查的是指針的簡單使用以及子程序的值參概念。為取變量的內(nèi)存地址，x:=a，也即x 存放的就是變量a的內(nèi)存地址。x表示的是，內(nèi)存地址為x的整型變量的值，其實(shí)也即變量a的值。所以，變量a與變量x是完全等價(jià)的，也即兩個調(diào)用是完全一樣的。結(jié)合值參概念，容易知道其結(jié)果是：No.1:3,6 No.2:3,6這題的關(guān)鍵是指針的基本使用，尤其是取地址。請思考以下程序的輸出結(jié)果：program s402;type point=integer;var a,b:integer; x,y:point;procedure fun(a,b:point);var k:integer;begin k:=a; a:=b; b:=k;end;begin a:=3; b:=6; write(No.1:,a,b, ); x:=a; y:=b; fun(x,y); writeln(No.2:,a,b);end.輸出:選例三 Program ex3;var n,i,j:Longint; s:Array 1.100 of integer;begin readln(n);i:=0; Repeat inc(i); if odd(n) then si:=1 else si:=0; n:=n SHR 1; Until n=0; for j:=i downto 1 do write(sj);writeln;end.輸入：2009程序運(yùn)行的結(jié)果是：簡析本題的關(guān)鍵是清楚子程序inc(i)、odd(n)的含義，以及運(yùn)算符shr的運(yùn)算結(jié)果，特別是運(yùn)算符shr的含義，如果不知道，那這題就沒得做了。函數(shù)odd(n)是判斷n是否為奇數(shù)，而shr是按位右移，高位補(bǔ)零?！爸弊g”程序的意思是：n為奇數(shù)si為1，否則si為0；接著用右移運(yùn)算，消去n化為二制進(jìn)后的最低位。直到n為零。 其實(shí)，每次消化的n的二進(jìn)制位最低位，就直接保存在數(shù)組s中。由此可知，其實(shí)輸出的就是n轉(zhuǎn)換為二進(jìn)制后的結(jié)果：11111011001.小結(jié)：全面掌握語言基礎(chǔ)，是“讀程序?qū)懡Y(jié)果”的立根之本。如果碰到哪個函數(shù)不清楚，哪個運(yùn)算符或符號不了解的，那么相關(guān)題目就會當(dāng)場掛掉?！白x程序?qū)懡Y(jié)果”，一題就是8分，因這種原因而失分是痛中之痛。基于這點(diǎn)，在NOIP初賽前，全面復(fù)習(xí)相關(guān)基礎(chǔ)知識是必要的、也是重要的。讀程序?qū)懡Y(jié)果之起步篇上一講我們?nèi)娼榻B了語言基礎(chǔ)，本講將進(jìn)入實(shí)質(zhì)的“技巧化”訓(xùn)練?！白x程序?qū)懡Y(jié)果”，解決這類問題的方法，總體說來有兩大類：一是從宏觀上，了解程序的目的和大致算法；二是從微觀上，人腦模擬程序的實(shí)際執(zhí)行過程。在實(shí)際應(yīng)用中，常常要綜合運(yùn)用。為了便于探討，下面列舉了八種技巧。需要說明的是，每種技巧也不是獨(dú)立的，在實(shí)際使用過程中，經(jīng)常需要交叉混合應(yīng)用。技巧一：人工模擬，列表跟蹤變量的變化過程選例四 NOIP2001提高組第二題program gao7_2；var p，q，s，t：integer；beginreadln(p)；for q：=p+1 to 2*p dobegint:=0；s:=(p*q)mod(q-p)；if s=0 then begin t:=p+q+(p*q)div(q-p)； write(t：4)； end； end；end.輸入12輸出解析：考查的是，學(xué)生對基本語句的閱讀理解能力。通過簡單的手工模擬可迅速得到答案。由于變量的遞變次數(shù)較多，為了讓手工模擬計(jì)算機(jī)執(zhí)行過程更清晰，建議建立如下變量值遞變列表：q131415161718s12*13 mod 112*14 mod 212*15 mod 312*16 mod 412*17 mod 512*18 mod 6s為零是是是是否是t181110877666續(xù)表：q192021222324s12*19 mod 712*20 mod 812*21mod 912*22mod 1012*23mod 1112*24mod 12s為零否是是否否是t626160也即輸出結(jié)果為：181 110 87 76 66 62 61 60列表的好處就是可以清晰的表示各變量在不同時刻的遞變情況。在變量不是太多，循環(huán)體執(zhí)行次數(shù)有限的情況下，可大力提倡這種方法。技巧二：化整為零，分割處理閱讀程序時，有些程序比較長，依據(jù)循環(huán)或子程序可以明顯地將其分為幾個“段”，這時我們可以化整為零，充分利用程序結(jié)構(gòu)將其分割成若干個子程序段，再集中精力，分別對每個程序段進(jìn)行獨(dú)立處理、理解，逐一解決。選例五 NOIP2002八屆提高組第二題1program Gxp2;2 var i , j , s ,sp1 : integer ;3 p : boolean ;4 a : array1.10 of integer ;5 begin6 sp1:=1; a1:=2; j:=2;7 while sp10 dobegin j:=j-1； bj：=m mod 10； m:=m div 10end；for h:=j to 10 do n:=n+bh；end； writeln(n)；end.輸入1234輸出：解析：手工模擬部分： For循環(huán)，i為循環(huán)變量；M:=N、J:=11：暫不能理解；while循環(huán)。這個循環(huán)的作用大部分同學(xué)也較清楚，就是把M進(jìn)行拆位，并把各位數(shù)字依次存入數(shù)組A。由此也知：以上M:=N是為了保護(hù)N的值，J:=11是表示數(shù)組A的下標(biāo)。如M=1234，執(zhí)行到退出while循環(huán)時，J的值為7，A的值為：H78910B（H）1234for h:=j to 10 do：也是循環(huán)。容易理解該循環(huán)的功能是在N的基礎(chǔ)上累加數(shù)組A中下標(biāo)從J到10的各值。該循環(huán)退出，N的值為1234+1+2+3+4，即：1244；結(jié)束外重循環(huán)，返回，i=2；重新執(zhí)行語句（M:=N；J:=11），這時M的值為“1244”，J的值還是11，容易得：數(shù)組A的值為：H78910A（H）1244所以K=2時，N的值為1244+1+2+4+4，即：1255。至此應(yīng)該可以理解程序的執(zhí)行目的：即把N的數(shù)位拆開，再加起來，對新的N做同樣的操作，反復(fù)10次。如果還進(jìn)行“機(jī)械模擬”的話，會影響解題的速度，同時也增加人為失誤的可能性。所以無需再“模擬”程序，可迅速手算出最后結(jié)果。“超越” 手算部分：K345678910N1255+1+2+5+5（1268）1268+1+2+6+8（1285）130113061316132713401348也即本例輸出結(jié)果為：1348技巧四：善于把握關(guān)鍵語句（段）或過程名稱算法發(fā)展至今，許多功能實(shí)現(xiàn)的程序段是經(jīng)典而通用的。如：選例五的判斷素?cái)?shù)、選例六的拆位（即進(jìn)制轉(zhuǎn)換的本質(zhì)），還有累加、累乘、排序、求最大值最小值，以及一些經(jīng)典算法。碰到類似這樣的程序段，我們可以有依據(jù)地判斷其程序目的。“可讀性”是程序優(yōu)劣的一個重要指標(biāo)。程序書寫，為了其可讀性，很多時候，變量名及子程序的名稱，往往能“見文生義”。通過這些名稱，有時很容易猜到子程序的功能（或變量的含義），起到“事半功倍”的效果。選例七 NOIP1998提高組第二題program ex5;const n=10;var s,i:integer;function co(i1:integer):integer;var j1,s1:integer;begin s1:=n; for j1:=n-1 downto n-i1+1 do s1:=s1*j1 div (n-j1+1); co:=s1;end;begin s:=n+1; for i:=2 to n do s:=s+co(i); writeln(s=,s);end.解析：程序結(jié)構(gòu)簡單，關(guān)鍵是弄清楚子函數(shù)co的功能。手工模擬一下：co(2)：j1：=9 downto 9 s1=10*9/2co(3)：j1：=9 downto 8 s1=10*9/2*8/3其實(shí)，到這應(yīng)該可以知道程序的目標(biāo)了，再結(jié)合函數(shù)名稱為co，容易想到組合數(shù)。再看一個：co(4)：j1：=9 downto 7 s1=10*9/2*8/3*7/4 =10*9*8*7/(4*3*2*1)=C(10，4)循環(huán)變量i是從2開始，累加到n。s的初值為1+n。如果我們能聯(lián)想到C(n,0)=1、C(n,1)=n，則該程序輸出即為：C(n,0)+ C(n,1)+ C(n,2)+ C(n,n)=小結(jié)：人工模擬的目的是為了理解程序的目的。為此，我們在模擬的過程中，應(yīng)該結(jié)合自己已有的知識，并明察秋毫地接收一切有用的信息（包括函數(shù)名變量名），大敢而又細(xì)致地猜測并驗(yàn)證程序的目的。在了解并確定程序目的后，許多時候就可以超越程序本身，直接寫出程序的執(zhí)行結(jié)果。所以，了解程序的目的是關(guān)鍵。讀程序?qū)懡Y(jié)果之進(jìn)階篇 上一講，我們就“讀程序?qū)懡Y(jié)果”解題的一般方法，做了個簡單的探討與總結(jié)。本講，我們共同來研究兩個特例：有關(guān)“字符（串）的操作與遞歸調(diào)用。技巧五：字符串的處理字符串操作，無論是NOIP初賽還是復(fù)賽，近些年來，頻頻出現(xiàn)，非常明確地提醒了選手，在準(zhǔn)備NOIP競賽時，必須充分地重視并認(rèn)真徹底地把字符（串）操作了解清楚。在Pascal中，有關(guān)字符的類型有兩種：char、string。特別要注意類型string與字符數(shù)組的異同點(diǎn)：（假設(shè)變量說明為： a:string; b:array1.100 of char）相同點(diǎn)：都可以用下標(biāo)變量（形如ai、bi）進(jìn)行訪問。不同點(diǎn)：ord(a0)的值，固定為字符串a(chǎn)的長度（操作影響到字符串長度時，應(yīng)注意保持該值的有效性）；字符串a(chǎn)可以進(jìn)行整體輸出輸入并可以使用系統(tǒng)有關(guān)字符串的過程與函數(shù)，而字符數(shù)組不行；類型string所能表示的字串長度為1到255，而字符數(shù)組不受此限制。有關(guān)字符（串）的函數(shù)與過程，請參閱“基礎(chǔ)篇”。值得一提的是，常用字符的ASCII碼為（括號內(nèi)為ASCII碼，從小到大排列）：0(30H)9A(41H)Za(61H)z對字符（串）的處理，要求選手能結(jié)合字符（串）有關(guān)知識，靈活使用前面講過的技巧。以下選例說明字符（串）操作在“讀程序?qū)懡Y(jié)果”中的應(yīng)用。選例八 NOIP2008提高組第四題1var s:string;2 i,j,len,k:integer;3begin read(s);len:=length(s);4 for i:=1 to len do5 if (ord(si)=ord(A) and (ord(si)=ord(Z) then6 si := chr(ord(si) - ord(A) + ord(a);7 for i:=1 to len do8 if (ord(si)ord(x) then si:= chr(ord(si)+3)9 else si:= chr(ord(si)-23);10 write(s);write(/);11 for j:=1 to 3 do begin12 i:=1;13 while i=len-j do begin14 si:=si+j;15 i:=i+j;16 end;17 end;18 writeln(s);19end.輸入：ABCDEFGuvwxyz輸出：_解析：應(yīng)該算基礎(chǔ)題。程序有點(diǎn)長，我們可以根據(jù)結(jié)構(gòu)分為以下幾個程序段進(jìn)行分析：第4至6行：這個循環(huán)是依次判斷字符是否為大寫字母，若是，則改為小寫。執(zhí)行后s的值為：abcdefguvwxyz；第7至9行：注意分界點(diǎn)（對比對象）是字母x，運(yùn)算后，s為：defghijxyzabc第10行：輸出：defghijxyzabc/第11至17行：循環(huán)遞變，j的值比較小，直接列表模擬！注意15行：變量i的步長。變量j123遞變前的sdefghijxyzabcefghijxyzabccgfihxjzybaccc遞變后的sefghijxyzabccgfihxjzybaccchfizxjaybcccc實(shí)現(xiàn)功能依次移位奇數(shù)位移位1471013第21行：輸出：hfizxjaybcccc雖然本程序給人第一感覺：程序長、似乎挺難的，但經(jīng)過簡單的分割處理，可以看出，每個程序段的功能都是顯而易見的。“一切反動派都是紙老虎”！在戰(zhàn)略上可以藐視這類題，但在戰(zhàn)術(shù)上應(yīng)該重視細(xì)節(jié)。克服長程序給人的心理壓力，沉下心來，仔細(xì)分析，認(rèn)真運(yùn)算，一切就迎刃而解。選例九 1Program t4;2var n,i,j:integer;str:string;3 a:Array 1.21 of string;4 t1,t2:longint;code:integer;5begin6 readln(str);7 n:=0;8 while str do begin9 i:=pos( ,str);10 n:=n+1;11 if i0 then12 begin an:=copy(str,1,i-1);delete(str,1,i);end13 else begin an:=str;str:= end;14 end;15 for i:=1 To n-1 do16 for j:=1 To n-i do begin17 val(aj+aj+1,t1,code);val(aj+1+aj,t2,code);18 if t1t2 then begin19 a21:=aj;aj:=aj+1;aj+1:=a21;20 end;21 end;22 for i:=1 To n do write(ai);writeln;23end.輸入：9 3 34 321程序運(yùn)行的結(jié)果是：解析這題用到的字符（串）子程序比較多，有需要的，請參閱“基礎(chǔ)篇”。第8至14行構(gòu)成循環(huán)的功能是什么呢？第9行，取空格的位置；繼而，如果空格存在的話，把空格前的字符串賦予an，并在串str中把至空格為止的字符全部刪除；若空格不存在，則把str賦予an，令str為空串。所以，實(shí)際上，它是以空格為分隔，把各數(shù)字字串，分別置于數(shù)組a中，即a=9、3，34，321。第15到21行，冒泡排序經(jīng)典程序段，不同的是，大小的評價(jià)標(biāo)準(zhǔn)不一樣。它是以相鄰兩數(shù)字字串連接在一起的數(shù)值大小為衡量標(biāo)準(zhǔn)。以aj= 3、aj+1= 34為例，執(zhí)行完第17行的語句后可求得t1=334、t2=343，由于t1=14 then w(num div 14); write(num);end;begin w(2009);end.程序運(yùn)行的結(jié)果是：解析具體執(zhí)行過程如下：（注意箭號順序）12345三個write語句，依次輸出：101432009本例應(yīng)用大括號的方式全部展開遞歸調(diào)用的過程，只要謹(jǐn)記所調(diào)用的子程序執(zhí)行完畢方能返回調(diào)用該子程序的程序中繼續(xù)執(zhí)行，嚴(yán)格把關(guān)語句的執(zhí)行順序就可以了。只是，很多時候，我們沒法，或者很難手工全部展開遞歸的詳細(xì)過程，這時，一般可以采用“自底向上”，從遞歸邊界出發(fā)，遞推出結(jié)果。如：選例十一 function s(n,k:integer):longint; begin if (n=k) or (k=1) then s:=1 else s:=s(n-1,k-1)+k*s(n-1,k); end;begin writeln(s(7,5); end.輸出結(jié)果：解析 程序很短很簡單，但是如果我們用類似上例的方法來模擬展開該遞歸的執(zhí)行調(diào)用過程，會碰到前所未有的困難。原因很簡單，遞歸調(diào)用的次數(shù)太多了。碰到這種情況時，我們可以從遞歸的邊界出發(fā)，進(jìn)行遞推求解。具體求解過程如下：1、邊界賦值：sn,n=1；sn,1=12、遞推求解過程：S3,2=s2,1+2*s2,2=3S4,2=s3,1+2*s3,2=7；s4,3=s3,2+3*s3,3=6S5,3=s4,2+3*s4,3=25；s5,4=s4,3+4*s4,4=10s6,4=s5,3+4*s5,4=65；s6,5=s5,4+5*s5,5=15S7,5=s6,4+5*s6,5=65+5*15=140整個遞推過程，可記錄如下表格：kn1234511211313141761512510161651571140也即本例輸出結(jié)果為：140值得注意的是，我們只要求出表格中的數(shù)據(jù)即可，其它空白的，無需求解。為了節(jié)省時間，避免不必要的人為錯誤，所做的運(yùn)算越少越好。那么哪些是該算的、哪些是無需計(jì)算的，也即如何只進(jìn)行有效計(jì)算呢？這問題，留給讀者自己思考。小結(jié)：字符（串）操作，除了要求選手要有扎實(shí)的語言基礎(chǔ)并了解相關(guān)字符串知識點(diǎn)外，多數(shù)還體現(xiàn)了對選手細(xì)心、耐心及毅力品質(zhì)的考核。題目一般不會引用高深的算法或理論，需要的就是“靜心分析、耐心計(jì)算”。 而子程序的調(diào)用，考查的除了子程序調(diào)用本身的一些知識點(diǎn)外，多數(shù)還會揉合一些其它綜合知識。比如，選例十一，其實(shí)就是第二類Stirling數(shù)。讀程序?qū)懡Y(jié)果之提高篇 “讀程序?qū)懡Y(jié)果”有時會考查選手經(jīng)典算法的掌握情況及數(shù)學(xué)知識的應(yīng)用能力。這類題，要求選手有較高的綜合素質(zhì)。下面共同探討一下這兩個方面：技巧七：計(jì)算經(jīng)典問題的重現(xiàn)同一個問題，考慮的角度不一樣，往往可以寫出風(fēng)格完全不一樣，甚至算法完全不同的程序，結(jié)果卻是相同的：殊途同歸。正因?yàn)檫@樣，有些經(jīng)典問題經(jīng)常會被拿出來“重寫”。在讀程序時，應(yīng)該善于把剛剛看到的“程序”與自己腦海里的信息進(jìn)行匹配。一旦找到自己已有信息里類似、甚至相同的問題時，面對的問題也就迎刃而解。這些經(jīng)典問題有：素?cái)?shù)、排序、約瑟夫問題、楊輝三角、最大公約數(shù)（輾轉(zhuǎn)相除法）、高精度計(jì)算、二分法、求最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑、歐拉回路、哈密頓回路、最小生成樹、搜索問題等等。選例十二 NOIP2007提高組第三題1program S403;2var a1:array1.50 of integer;3var i,j,t,t2,n,n2:integer;4begin5 n:=50;6 for i:=1 to n do a1i:=0;7 n2:=round(sqrt(n);8 for i:=2 to n2 do9 if(a1i=0) then10 begin11 t2:=n div i;12 for j:=2 to t2 do a1i*j:=1;13 end;14 t:=0;15 for i:=2 to n do16 if (a1i=0) then17 begin18 write(i:4); inc(t);19 if(t mod 10=0) then writeln;20 end;21 writeln;22 end.輸出：解析第7行，求n的平方根，干嘛用呢？a1i原來都為0，第8至13行循環(huán)里嵌套了第12行循環(huán)：為什么要把i的倍數(shù)的下標(biāo)變量都改為1呢？其實(shí)，這就是經(jīng)典的篩選法求素?cái)?shù)！第14至20行循環(huán)，輸出這些素?cái)?shù)。變量t用來控制一行輸出10個素?cái)?shù)。因此，本例輸出結(jié)果為：（注意場寬、對齊） 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47選例十三 NOIP2007提高組第四題program S404;const n=12; ch2:array0.12 of char =(q,A,S,O,R,T,E,X,A,M,P,L,E);var k:integer; ch:array0.12 of char;procedure shift(k,n:integer);var v:char; j:integer;begin v:=chk; j:=k+k; while (j=n) do begin if (jn) and (ord(chj)ord(chj+1) then inc(j); if (ord(v)ord(chj) then begin chj div 2:=chj; j:=j*2; end else exit; chj div 2:=v; end;end;procedure hpsrt;var k:integer; tmp:char;begin for k:=n div 2 downto 1 do shift(k,n); write(No.1: ); for k:=1 to n do write(chk); writeln; for k:=n downto 1 do begin tmp:=ch1; ch1:=chk; chk:=tmp; shift(1,k-1); end;end;begin for k:=0 to n do chk:=ch2k; hpsrt; write(No.2: ); for k:=1 to n do write(chk); writeln;end.輸出：解析基礎(chǔ)扎實(shí)并有靈性的選手，看完題就可以馬上寫出結(jié)果。本程序至少有以下非常容易讓人聯(lián)想的符號或代碼：過程名：shift 移動？ hpsrt 堆排序？for k:=n div 2 downto 1 do shift(k,n) ：典型的建堆語句本例即輸出建立最大堆后的狀態(tài)，及從小到大堆排序后的結(jié)果：No.1: XTORSEAAMPLENo.2: AAEELMOPRSTX要注意的是，下標(biāo)為0的對象（即q），沒有參與操作。技巧八：巧用數(shù)學(xué)知識推理 有些程序，我們粗讀一遍就可以知道其循環(huán)執(zhí)行的次數(shù)非人工模擬能夠忍受，或根本就沒法模擬，這時應(yīng)該想一想能否運(yùn)用數(shù)學(xué)知識，推理得出程序執(zhí)行的結(jié)果。當(dāng)然，這要求選手要有扎實(shí)的數(shù)學(xué)功底。選例十四 NOIP2002提