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

1、.编程基本能力和技巧1 数组及其应用这里还是只讲一些应用，基础知识自己看书或我提供的几个INTERNET资源。1.下标的灵活运用例如对称的情形，可以把下标设成：a:array-5.5 of integer;只要ai:=a-i;就进行了一次“对称”的赋值。2.常量数组善用可以减少不少程序量。例如P1-9公式变形。我的参考程序只有三十多行，主要是因为灵活的应用了数组，包括一个常量数组一个变量数组，减少了不少麻烦。典型的常量数组有：增量型：如在国际象棋棋盘上“马”的八个方向的活动可以用两的增量数组表示：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个方向只需要：x:=x+dxd;y:=y+dyd;枚举型：例如平年一年第N个月的天数：dcount:array1.12 of shortint=(31,28,31,30,31,30,31,31,30,31,30,31);便于修改。3.避免下标越界方法是$R+4.数组的插入与删除虽然数组应该避免频繁的插入与删除，但有时不可避免。方法如下：插入：插入点以后每个元素往后移动一个位置，再插入：for i:=len downto p doai+1:=ai;ap:=x;inc(len);删除：删除点以后的每个元素

3、往前移动一个位置，如：for i:=p to last doai:=ai+1;dec(len);2 字符串处理字符串处理因为其灵活性常使初学者头疼！我以前也怕它，不过很快就适应了。一般常用的处理是：(以下的例子中s是一个字符串)1.扫描字符第i个字符是si例如s='Hello, world!'则s1='H', s6=',', s7=' ' s13='!'s的长度是length(s)那么把字符串反转后输出的方法就是for i:=length(s) downto 1 dowrite(si);2.定位就是查找子串例如s1

4、='Hello, my friend!'s2='my'则pos(s2,s1)=8,即s2在s1的第8个字符处出现但pos('him','history')=0,因为'him'在'history'中并不出现3.分割,合并,删除仅举几个例子。1)copycopy('Hello, my friend!',3,2)='ll'2)delete若s='Hello, my friend'执行delete(s,4,4)后s='Helmy friend'

5、'3)s1='Hi,'s2='Alan'则s1+s2='Hi,Alan'4.与数字互化s='1234'执行val(s,v,code)后v=1234; code=0; code=0说明成功的将字符串转化为了数字，否则code<>0v=4567;执行str(v,s)后s='4567'5.字符的ASCII码请自己看有关的书籍，一定要掌握！注意：对于时间要求严格的题目，字符串操作的时间问题也不能忽视。6.一个例子：输入k个字符串（中间可能有多个空格），把他们反着连在一起输出。如：输入：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); 找第一个空格;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 整数的处理主要

7、是利用数学工具了。下面举几个例子。1.求最大公约数gcd（greatest common divisor）用欧几里德辗转相除法：function gcd(a,b:longint):longint;beginif a mod b=0 then gcd:=belse gcd:=gcd(b,a mod b);end;2.求最小公倍数利用(a,b)*a,b=a*b 即可。例如：100和140的最大公约数为20,那么最小公倍数=100*140 div 20=7003.分离数字很简单，涉及到数字的问题都可以借助于字符串。例如反转各位数字：(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.素数的测试一般是: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;对于大的素数（在longint范围内）可以采用先生成一个小的素数表，在 * 改为测试2到trunc(sqrt(k)内的所有素数。当然要保证素数表足够大。(到46341为止)更快的测试方法将在后面介绍。一定要注意是否运算结果可能溢出。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);算法时间复杂度为O(N2).它的最正确，平均，最差情况是几乎一样的选择排序：每次选最小的，然

10、后把它去掉以后再选最小的.2.O(nlogn)排序归并排序：分成两堆，分别排序，再合并。快速排序：选择一个支撑点，把比它小的放在左边，比他大的放在右边，分别排序。在“分治法”部分，我会再提到快速排序和它的一些类似的问题的。3.不基于比较的排序如果数字都小于等于一个定值M，可以考虑数组排序：令bi为i出现的次数，则：fillchar(b,sizeof(b),0);for i:=1 to n doinc(bai);那么b中非零的数就组成了排好序的序列，也就是：for i:=1 to m dofor j:=1 to bi dowriteln(i);如果bi是一个链表，就成了桶排序。5 高精度数的处理

11、注意：只要你会笔算，照搬到这里就可以了。常用数据结构（这里我只讲一种）：数组,每个元素是一位数字。如：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进制，把10换成N就可以了。乘法（单精度与多精度）就是：g:=0;for i:=len downto 1 dobegins:=ai*b+g;ci:=s mod 10;g:=s

12、 div 10;end;注意：b不一定只是一位数。高精度乘法（字符串形式）我推荐使用多项式乘法的方式。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; 结果在第几位inc(tmpp-k ,vai*vbj mod 10); 加到这一位上inc(tmpp-k-1,vai*vbj div 10);end;整理结果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 进位制大家应该比较熟吧。运算可以按高精度数处理，而进制转换嘛，也不难。10进制换成N进制：readln(p); p<>0时i:=0;while p>0 dobegininc(i);ai:=p mod n;p:=p div n;end;for