编程基本能力和技巧.doc

编程基本能力和技巧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: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);删除：删除点以后的每个元素往前移动一个位置，如：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=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)=ll2)delete若s=Hello, my friend;执行delete(s,4,4)后s=Helmy friend;3)s1=Hi,;s2=Alan;则s1+s2=Hi,Alan4.与数字互化s=1234;执行val(s,v,code)后v=1234; code=0; code=0说明成功的将字符串转化为了数字，否则code0v=4567;执行str(v,s)后s=4567;5.字符的ASCII码请自己看有关的书籍，一定要掌握！注意：对于时间要求严格的题目，字符串操作的时间问题也不能忽视。6.一个例子：输入k个字符串（中间可能有多个空格），把他们反着连在一起输出。如：输入：abc d e f 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 整数的处理主要是利用数学工具了。下面举几个例子。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=13765 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 exit; 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 ai1)and(a1=0) do delete(a,1,1);while (length(b)1)and(b1=0) do delete(b,1,1);初始化积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); p0时i:=0;while p0 dobegininc(i);ai:=p mod n;p:=p div n;end;for j:=i downto 1 dowrite(aj);N进制转化成10进制：p:=0;for i:=1 to len dop:=p*n+ai;这次复赛（其实是N年以前的ACM题目）考了负数进位制，其实还有复数进位制和fibinacci进制的!他们都是基于定义的。利用类似的（广义）除法和取模运算，最后都能够得出正确的进制表示。说到应用，主要是数学题，例如tower of hanoi，还有压缩存储。例如拯救大兵瑞恩和补丁vs错误