[建筑]編程基本能力和技巧

1、.編程基本能力和技巧1 數(shù)組及其應(yīng)用這里還是只講一些應(yīng)用，基礎(chǔ)知識自己看書或我提供的幾個(gè)INTERNET資源。1.下標(biāo)的靈活運(yùn)用例如對稱的情形，可以把下標(biāo)設(shè)成：a:array-5.5 of integer;只要ai:=a-i;就進(jìn)行了一次“對稱”的賦值。2.常量數(shù)組善用可以減少不少程序量。例如P1-9公式變形。我的參考程序只有三十多行，主要是因?yàn)殪`活的應(yīng)用了數(shù)組，包括一個(gè)常量數(shù)組一個(gè)變量數(shù)組，減少了不少麻煩。典型的常量數(shù)組有：增量型：如在國際象棋棋盤上“馬”的八個(gè)方向的活動(dòng)可以用兩的增量數(shù)組表示：dx:array1.8 of shortint=(1,2,2,1,-1,-2,-2,-1);dy:

2、array1.8 of shortint=(-2,-1,1,2,2,1,-1,-2);移動(dòng)第d個(gè)方向只需要：x:=x+dxd;y:=y+dyd;枚舉型：例如平年一年第N個(gè)月的天數(shù)：dcount:array1.12 of shortint=(31,28,31,30,31,30,31,31,30,31,30,31);便于修改。3.避免下標(biāo)越界方法是$R+4.數(shù)組的插入與刪除雖然數(shù)組應(yīng)該避免頻繁的插入與刪除，但有時(shí)不可避免。方法如下：插入：插入點(diǎn)以后每個(gè)元素往后移動(dòng)一個(gè)位置，再插入：for i:=len downto p doai+1:=ai;ap:=x;inc(len);刪除：刪除點(diǎn)以后的每個(gè)元素

3、往前移動(dòng)一個(gè)位置，如：for i:=p to last doai:=ai+1;dec(len);2 字符串處理字符串處理因?yàn)槠潇`活性常使初學(xué)者頭疼！我以前也怕它，不過很快就適應(yīng)了。一般常用的處理是：(以下的例子中s是一個(gè)字符串)1.掃描字符第i個(gè)字符是si例如s='Hello, world!'則s1='H', s6=',', s7=' ' s13='!'s的長度是length(s)那么把字符串反轉(zhuǎn)后輸出的方法就是for i:=length(s) downto 1 dowrite(si);2.定位就是查找子串例如s1

4、='Hello, my friend!'s2='my'則pos(s2,s1)=8,即s2在s1的第8個(gè)字符處出現(xiàn)但pos('him','history')=0,因?yàn)?#39;him'在'history'中并不出現(xiàn)3.分割,合并,刪除僅舉幾個(gè)例子。1)copycopy('Hello, my friend!',3,2)='ll'2)delete若s='Hello, my friend'執(zhí)行delete(s,4,4)后s='Helmy friend'

5、'3)s1='Hi,'s2='Alan'則s1+s2='Hi,Alan'4.與數(shù)字互化s='1234'執(zhí)行val(s,v,code)后v=1234; code=0; code=0說明成功的將字符串轉(zhuǎn)化為了數(shù)字，否則code<>0v=4567;執(zhí)行str(v,s)后s='4567'5.字符的ASCII碼請自己看有關(guān)的書籍，一定要掌握！注意：對于時(shí)間要求嚴(yán)格的題目，字符串操作的時(shí)間問題也不能忽視。6.一個(gè)例子：輸入k個(gè)字符串（中間可能有多個(gè)空格），把他們反著連在一起輸出。如：輸入：abc d e f

6、 gh輸出:ghfedabc分析：只要把空格刪除，就可以得到這些字符串。varp:integer;s,s2:string;beginreadln(s);s2:=''repeatwhile s1='' do delete(s,1,1); 刪去開頭的多余空格p:=pos(' ',s); 找第一個(gè)空格;if p=0 then s2:=s+s2 沒有找到else begins2:=copy(s,1,p-1)+s2; 加入到s2的前面delete(s,1,p); 刪去end;until p=0; 沒有空格了writeln(s2);end.3 整數(shù)的處理主要

7、是利用數(shù)學(xué)工具了。下面舉幾個(gè)例子。1.求最大公約數(shù)gcd（greatest common divisor）用歐幾里德輾轉(zhuǎn)相除法：function gcd(a,b:longint):longint;beginif a mod b=0 then gcd:=belse gcd:=gcd(b,a mod b);end;2.求最小公倍數(shù)利用(a,b)*a,b=a*b 即可。例如：100和140的最大公約數(shù)為20,那么最小公倍數(shù)=100*140 div 20=7003.分離數(shù)字很簡單，涉及到數(shù)字的問題都可以借助于字符串。例如反轉(zhuǎn)各位數(shù)字：(13765->56731)vara:longint; a=1

8、3765 b:longint; b will be 56731s1,s2:string;i,code:integer;begina:=13765;str(a,s1);s2:=''for i:=length(s1) downto 1 dos2:=s2+s1i;val(s2,b,code);now, b=56731!end.4.素?cái)?shù)的測試一般是:function isprime(k:longint):boolean;vari:longint;beginisprime:=false;for i:=2 to trunc(sqrt(k) do *if k mod i=0 then exi

9、t; isprime:=true;end;對于大的素?cái)?shù)（在longint范圍內(nèi)）可以采用先生成一個(gè)小的素?cái)?shù)表，在 * 改為測試2到trunc(sqrt(k)內(nèi)的所有素?cái)?shù)。當(dāng)然要保證素?cái)?shù)表足夠大。(到46341為止)更快的測試方法將在后面介紹。一定要注意是否運(yùn)算結(jié)果可能溢出。4 排序以下均是：a:array1.n of integer; 要求升序排列。1.O(N2)排序冒泡排序for i:=1 to n-1 dofor j:=i+1 to n doif ai<aj then swap(ai,aj);算法時(shí)間復(fù)雜度為O(N2).它的最正確，平均，最差情況是幾乎一樣的選擇排序：每次選最小的，然

10、后把它去掉以后再選最小的.2.O(nlogn)排序歸并排序：分成兩堆，分別排序，再合并?？焖倥判颍哼x擇一個(gè)支撐點(diǎn)，把比它小的放在左邊，比他大的放在右邊，分別排序。在“分治法”部分，我會再提到快速排序和它的一些類似的問題的。3.不基于比較的排序如果數(shù)字都小于等于一個(gè)定值M，可以考慮數(shù)組排序：令bi為i出現(xiàn)的次數(shù)，則：fillchar(b,sizeof(b),0);for i:=1 to n doinc(bai);那么b中非零的數(shù)就組成了排好序的序列，也就是：for i:=1 to m dofor j:=1 to bi dowriteln(i);如果bi是一個(gè)鏈表，就成了桶排序。5 高精度數(shù)的處理

11、注意：只要你會筆算，照搬到這里就可以了。常用數(shù)據(jù)結(jié)構(gòu)（這里我只講一種）：數(shù)組,每個(gè)元素是一位數(shù)字。如：123456789123456789儲存成：a:array1.len=(0,0,0.0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9);加法就是：g:=0;for i:=len downto 1 dobegins:=ai+bi+g;ci:=s mod 10;g:=s div 10;end;如果是N進(jìn)制，把10換成N就可以了。乘法（單精度與多精度）就是：g:=0;for i:=len downto 1 dobegins:=ai*b+g;ci:=s mod 10;g:=s

12、 div 10;end;注意：b不一定只是一位數(shù)。高精度乘法（字符串形式）我推薦使用多項(xiàng)式乘法的方式。constmaxn=100;typebign=stringmaxn;procedure mul(a,b:bign; var c:bign); vartmp:array1.maxn*2 of integer;i,j,g,p,k:integer;begin刪除多余的零while (length(a)>1)and(a1='0') do delete(a,1,1);while (length(b)>1)and(b1='0') do delete(b,1,1)

13、;初始化積p:=length(a)+length(b);for i:=1 to p dotmpi:=0;乘法：每兩位相乘for i:=1 to length(a) dofor j:=1 to length(b) dobegink:=p-i-j; 結(jié)果在第幾位inc(tmpp-k ,vai*vbj mod 10); 加到這一位上inc(tmpp-k-1,vai*vbj div 10);end;整理結(jié)果g:=0;c:=''for i:=p downto 1 dobeginc:=ch(tmpi+g) mod 10+c;g:=(tmpi+g) div 10;end;刪除多余的零while (length(c)>1)and(c1='0') do delete(c,1,1);end;下面是一篇英文文章(PDF) Big numbers6 進(jìn)位制大家應(yīng)該比較熟吧。運(yùn)算可以按高精度數(shù)處理，而進(jìn)制轉(zhuǎn)換嘛，也不難。10進(jìn)制換成N進(jìn)制：readln(p); p<>0時(shí)i:=0;while p>0 dobegininc(i);ai:=p mod n;p:=p div n;end;for