需要记忆的算法(1).doc

需要记忆的算法：pascal 运算优先级1 not2 and * / div mod3 or xor + -4 in = = = free pascal 数据类型标识符名称范围Range2进位字节shortint短整型-12812781integer整型-3276832767162Byte字节型025581Word字型065535162longint长整型-21474836482147483647324longword长字型0.4294967295324qword64字型0.18446744073709551615648Int6464整型-9223372036854775808.9223372036854775807648实型:数值范围:占字节数:有效位数real:2.9e-39.1.7e38:6:11.12single:1.5e-45.3.4e38:4:7.8double:5.0e-324.1.7e308:8:15.16extended:3.4e-4951.1.1e4932:10:19.20comp:-2*63+1.2*63-1:8:19.20常用的pascal内置函数和过程(1)自变量必须为整型的标准函数:(A)前趋函数：Pred(x)，函数结果类型为整型，如：Pred(4)=3(B)后继函数：Succ(x)，函数结果类型为整型，如：Succ(4)=5(C)奇函数：odd(x)，结果为布尔型。如：Odd(13)=True(D)字符函数：Chr(x)其中x为ASCII码，函数结果为字符型。如：Chr(65)=A(2)自变量为整型(或实型)，但函数值类型为实型的标准函数；(A)平方根函数：Sqrt(x)(B)整数函数：Int(x) 取整数部分，如：INT(3.85)= 3.0(C)小数函数：Frac(x)(D)正弦函数：Sin(x)(E)余弦函数：Cos(x)(F)反正切函数：Arctan(x)，单位为弧度Pascal中无正切函数，用Sin(x)/ Cos(x)代替(G)指数函数：Exp(x)，即求ex(H)对数函数：Ln(X)，即求x的自然对数logex幂运算 xy=eylnx ， xy =Exp(y*ln(x)注意：在FreePascal中,幂的表示: xy=power(x,y) 或 xy=x*y(I)随机函数：Random(x:word)，无x时，函数值取0,1)之间的随机小数；有x 且为Word类型时，函数值取0,x)之间的随机整数。前面加上：Randomize语句。(J)圆周率函数PI=3.1415926536(3)自变量为整型(或实型)，但函数值类型与x一致的标准函数(A)Abs(x)：绝对值函数，如：Abs(-2)=2 Abs(-2.0)=2.0000000000E+00(B)Sqr(x)：平方函数如，如：Sqr(4)=16 Sqr(4.0)= 1.6000000000E+01(4)自变量为整型(或实型)，但函数值类型为整型的标准函数(A)Trunc(x)：取整数部分，如：Trunc(3.85)=3(B)Round(x)：四舍五入，如：Round(2.8)=3 Round(-2.8)=-3(5)加1函数:inc(x) 如：inc(5)=6,inc(5,8)=13(6)减1函数 dec(x) 如：dec(5)=4 dec 5,3)=2文件函数：(1) Eof(f)或 Seekeof(f)未读到文件结束符“Chr(26) ”或 “Ctrl+Z”时，函数值为false; 读到文件结束符时，函数值为true;(2) Eoln(f)或SeekEolf(f)未读到行结束符“Chr(13) ”时，函数值为false; 读到行结束符或文件结束符时，函数值为true;字符函数(1)小写字母转为大写字母Upcase(x) ，如：Upcase (a)=A(2)前趋函数：Pred(x)，函数结果为字符型，如：Pred(4)=3(3)后继函数：Succ(x)，函数结果为字符型，如：Succ(A)=B(4) 序数函数：Ord(x), 函数结果为整型,求字符对应的ASCII码，如：Ord(A)=65(5)字符函数：Chr(x) ，x为整型，函数结果为字符型，,求ASCII码对应得字符，如：Chr(65)=A字符串函数(1)求长度length定义：function Length(S: String): Integer;(2)复制子串copy定义： function Copy(S: String; Index: Integer; Count: Integer): String;注意：S 是字符串类型的表达式。Index和Count是整型表达式。Copy 返回S中从Index开始，Count个字符长的一个子串。(3)插入子串insert定义：procedure Insert(Source: String; var S: String; Index: Integer);注意：Source 是字符串类型的表达式。 S 是任意长度字符串类型变量。Index 是整型表达式。Insert 把 Source插在S中Index处。如果结果字符串的长度大于255，那么255之后的字符将被删除。(4)删除子串delete定义：procedure Delete(var S: String; Index: Integer; Count:Integer);注意：S 是字符串类型变量。 Index和Countare是整型表达式。Delete 删除S中从Index开始的Count个字符。如果Index大于S的长度，则不删除任何字符；如果Count大于S中从Index开始的实际字符数，则删除实际的字符数。(5)字符串转为数值val定义： procedure Val(S; var V; var Code: Integer);在这里:S 是由一系列数字字符构成的字符串类型变量；。V 是整型或实型变量；Code 是Integer型变量注意：Val将S转为它的数值形式。(6)数值转为字符串str定义： procedure Str(X : Width : Decimals ; var S:string);注意：将数值X转成字符串形式。(7)求子串起始位置pos定义：function Pos(Substr: String; S: String): Byte;注意：Substr和S字符串类型表达式。Pos在S中搜索Substr并返回一个integer值。这个值是Substr的第一个字符在S中的位置。如果在S中没有找到Substr，则Pos返回0。(8)字符完全串连+联定义：操作符加号+把两个字符串联在一起。(9)字符串压缩空格串连-定义：操作符减号-去掉第一个字符串最后的空格后，将两个字符串联在一起。(10) 将数组批量填入初值，Fillchar(x,sizeof(x),0),将0填入到x数组中，sizeof(x)表示填入的个数 3个重要的退出语句HALT结束程序，返回操作系统EXIT结束过程或函数，返回调用处(在主程序中同HALT)BREAK 是用来退出其所在的循环语句(CONTINUE是继续当前循环)文件的输入和输出：begin assign(input,p1.in); reset(input); assign(output,p1.out); rewrite(output); for i:=1 to 20 do readln(ai); sum:=0; for i:=1 to 20 do sum:=sum+ai; writeln(sum); close(input); close(output);end.0. 最大公约数（GCD）Function gcd(a,b:longint):longint;Var r:longint begin repeat r:=a mod b; a:=b; b:=r; until r=0; exit(a); end; 最大公约数（gcd）和最小公倍数（lcm）的关系： gcd(a, b) * lcm(a, b) = ab1. 素数的判断： function ok(x:longint):boolean; var i:longint; begin for i:=2 to trunc(sqrt(x) do if x mod i=0 then exit(false); exit(true); end;筛选法求素数的算法: (1) 取最小的素数2，筛去它的所有倍数； (2) 取未被筛最小的数（一定是素数），再筛去它的所有倍数；(3) 重复(2)直至全部都是素数。（取最小数只需到 sqrt(n) ）程序代码可以各种各样，思路对了就行。2.选择排序 For i:=1 to n-1 do For j:=i+1 to n do If ajai then begin t:=aj;aj:=ai;ai:=t;end;3.二进制枚举法:Fillchar(b,sizeof(b),0);while b0=0 do begin j:=m; 第m位为最低位。 while bj=1 do dec(j); 从最低位开始找非1 的位子； bj:=1; 该位置1； for i:=j+1 to m do bi:=0; 把刚才经过的1全部置0； 已经产生一种2进制数 处理 End;4.快排：procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a(i+j) div 2; 取一个数； repeat while aix do inc(i); 左边起比x小的数不动，i停在不比x小的位子； while xaj do dec(j); 右边起比x大的数不动，j停在不比x大的位子； if ij; 直至i与j交叉；x已经在交叉的位置了。 if lj then qsort(l,j); 左边还有数(lj)，递归; if ir then qsort(i,r); 右边还有数（ir then exit(false); l与r交叉，表示没有找到。 mid:=(l+r) div 2; 取中间位置； if x=amid then exit(true); X等于该位置的数找到了！ if xamid then exit(find(x,mid+1,r); X大于该位置的数，则在右边找（递归）； end;6.高精加：i:=1;x:=0; fillchar(c,sizeof(c),0); while (i=la) or (i0 then lc:=i else lc:=i-1; lc记录结果的长度；7.高精减：i:=1; fillchar(c,sizeof(c),0); while i=la do begin if ai1) do dec(lc);8.高精乘：fillchar(c,sizeof(c),0); for i:=1 to lb do begin x:=0; for j:=1 to la do begin ci+j-1:=bi*aj+x+ci+j-1; x:=ci+j-1 div 10; ci+j-1:=ci+j-1 mod 10; end; ci+j:=x; end; lc:=la+lb; while (clc=0) and (lc1) do dec(lc);9.单精乘高精（100！）readln(n); c1:=1;l:=1;x:=0; for i:=1 to n do begin x:=0; for j:=1 to l do begin cj:=cj*i+x; x:=cj div 10; cj:=cj mod 10; end; while x0 do begin inc(l); cl:=x mod 10; x:=x div 10; end; end; for i:=l downto 1 do write(ci);10.单精除高精For i:=1 to la do Begin Ci:=(x*10+ai) div b; X:=(x*10+ai) mod b; End;J:=1;While (cj=0) and (j0) do dec(i); write(ci); for j:=i-1 downto 1 do begin if cj1000 then write(0); if cj100 then write(0); if cj10 then write(0); write(cj); end; writeln;end;begin a1:=1; b1:=1; for i:=3 to 2000 do begin c:=sum(a,b); a:=b;b:=c; write(i, ); print(c); / readln; end; end.10 深度搜索算法Procedure try(k:integer,其他参数表)；k表示深度 Begin If 到达目标 then begin 处理目标；exit; end; For i:=1 to 儿子数 do If 儿子合法（含边界判断） then Begin 记录状态； Try(k+1,其他参数传递)； 恢复状态； End; End;如果将该算法用在“洪水”，不必目标处理，走过做标记，不必恢复。整个程序退出即完成。11 广度搜索算法 Procedure bfs; begin 初始化，初始状态入队； Head:=0;tail:=1; 设置头尾指针 While headwi then if fi-1,jfi-1,j-wi+pi then fi,j:=fi-1,j else fi,j:=fi-1,j-wi+pi else fi,j:=fi-1,j; writeln(fn,m);（二）一维表for i:=1 to n do for j:=m downto wi do if fjwi then if fi-1,jfi,j-wi+pi then fi,j:=fi-1,j else fi,j:=fi,j-wi+pi else fi,j:=fi-1,j; writeln(fn,m);跟01背包只差一个地方（请关注蓝色标注）（二）一维表 （课本的一维算法好像有问题！）for i:=1 to n do for j:=wi to m do if fjb i,1 ) and (b j,2 L) then begin L:=b j,2 ; k:=j end; 所有比bI,1大的中连接数最大的记录下来if L0 then begin b i,2 :=L+1; b i,3 :=k; end; 连接数+1，k为连接前一个节点 end; 注：bx,1 原数列 ，bx,2 从x算起到n 的最长序列的长度 bx,3 序列连接指针，指向下一个节点的下标。依靠它可以把最长序列的每一个元素都找出来。拦截导弹、合唱队形、轮船问题都可以用此算法。合唱队形代码：var a,f1,f2:array1.10000 of longint; i,j,n,ans:longint;function max(a,b:longint):longint; begin if ab then exit(a) else exit(b) end;begin readln(n); for i:=1 to n do read(ai); for i:=1 to n do for j:=1 to i-1 do if ajai then f1i:=max(f1i,f1j+1); for i:=n downto 1 do for j:=i+1 to n do if ajai then f2i:=max(f2i,f2j+1); ans:=0; for i:=1 to n do ans:=max(ans,f1i+f2i+1); writeln(n-ans);end.动规转化方程： f(i)=max f(j) +1 (1=ji ajai) 从左往右16 骑士游历问题 （书p264）问中国象棋的马从（x1,y1）到（x2,y2）共有几条路？（马只能往右跳）mapx,y= map I, j +mapx,y | (x,y) 在界内 （I,j）包含可达（x,y）的坐标集雷同 网格路径（只能往右、往下）有多少种？ 11111123456136101521141020355617 挖地雷 （书 p260）从某处开始，沿着指出的连线，（仅一条路经），挖出最多地雷。路径都是单向的，无后效性。可以动规！F(i)= max w( i ) + f( j ) ( ij=n, a( i, j)=true表示有通路 )边界： f(n)=w(n)从后往前推！输入：65 10 20 5 4 51 21 42 43 44 54 65 60 0 输出：3-4-5-6 3417 砝码称重 (书 p265)设有1g、2g、3g、5g、10g、20g 各若干，求能组成多少种不同的重量？（最多1000g）.分析: 按照第1种, 第2种,第6种砝码顺序分析，在分析第I种砝码的放置方案时，依次在现有的不同重量基础上，加1、2、。aI枚，产生新的不同重量。 For I:=1 to 6 do For j:=1 to 已经产生的种数 doFor k:=1 to aI do (第I种有aI枚) Begin Total:=n j +k*num I ; (记录，要判重) end18 机器分配（书 p293）fI,j 表示前I 个公司分配 j 台机器的最大赢利。 以下取最大的一个： fI-1,0 + valueI,j fI-1,1 + valueI,j-1 fI-2,2+ valueI,j-2 fI-1,j-1+valueI,1 fI-1,j +valueI,0状态方程：fI,j=max fI-1,k+valueI,j-k (1=I=n, 1=j=m, 0=k=j)19传小球问题算法：f(i,k)表示经过k次传到编号为i的人手中的方案数f(i,k)=f(i-1,k-1)+f(i+1,k-1) （i=1或n时，需单独处理）边界条件：f(1,0)=1结果在f(1,m)中20表达式 用递归分治的方法：var s:string; i,j:longint;procedure error; begin writeln(error);halt end;function cal(st:string):longint; var j,min,p,k,len,i,r1,r2:longint; code:integer; begin len:=length(st);k:=0;min:=1000; for i:=1 to len do /整个串扫一遍，记录P和min case sti of (:inc(k); ):begin dec(k);if k0 then error;end; +,-:if k*10+1min then begin min:=k*10+1;p:=i;end; *,/:if k*10+2min then begin min:=k*10+2;p:=i;end;end; /p为最低优先级运算符的位置 /min 包含第k层括号内的最小优先级 if k0 then error; if min=1000 then /纯数据(没有运算符发生) begin val(st,j,code); if code0 then error; cal:=j; end else begin while min10 do /如果最外层有多层括号，去掉！ begin dec(min,10);dec(p); delete(st,1,1);delete(st,len,1); len:=len-2; end; r1:=cal(copy(st,1,p-1); /递归求p左右两边的值r1,r2 r2:=cal(copy(st,p+1,len-p); case stp of /将r1和r2按stp运算。 +:cal:=r1+r2; -:cal:=r1-r2; *:cal:=r1*r2; /:begin if r2=0 then error else cal:=r1 div r2 end; end; end; end; begin readln(s); writeln(cal(s); end.21插入排序法（线性链接表）： type pointer=node; node=record data:integer; next:pointer; end;var head,p,q,i:pointer; x:integer;begin read(x); new(head); new(q); head.data:=0; head.next:=q; q.data:=x; q.next:=nil; read(x); while x9999 do begin new(q); q.data:=x; p:=head; while (p.nextnil)and(p.next.datax) do p:=p.next; q.next: