i:integer; begin
if dep=n+1 then begin writeln(s);exit; end; for i:=1 to n do
if not used then begin
s:=s+chr(i+ord('0'));used:=true; solve(dep+1);
s:=copy(s,1,length(s)-1); used:=false; end; end;
2组合的生成(1..n中选取k个数的所有方案) procedure solve(dep,pre:integer); var
i:integer; begin
if dep=k+1 then begin writeln(s);exit; end; for i:=1 to n do
if (not used) and (i>pre) then begin s:=s+chr(i+ord('0'));used:=true; solve(dep+1,i);
s:=copy(s,1,length(s)-1); used:=false; end; end;
九.查找算法 1折半查找
function binsearch(k:keytype):integer; var low,hig,mid:integer; begin
low:=1;hig:=n;
mid:=(low+hig) div 2;
while (a[mid].key<>k) and (low<=hig) do begin if a[mid].key>k then hig:=mid-1 else low:=mid+1; mid:=(low+hig) div 2; end;
if low>hig then mid:=0; binsearch:=mid; end;
2树形查找
二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。 查找
function treesrh(k:keytype):pointer;
var q:pointer; begin
q:=root;
while (q<>nil) and (q^.key<>k) do if k 十、贪心 *会议问题 （1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。 解：按每项活动的结束时间进行排序，排在前面的优先满足。 （2）会议室空闲时间最少。 （3）每个客户有一个愿付的租金，求最大利润。 （4）共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。 十一、回溯法框架 1. n皇后问题 procedure try(i:byte); var j:byte; begin if i=n+1 then begin print;exit;end; for j:=1 to n do if a and b[j+i] and c[j-i] then begin x:=j; a[j]:=false; b[j+i]:=false; c[j-i]:=false; try(i+1); a[j]:=true; b[i+j]:=true; c[j-i]:=true; end; end; 2.Hanoi Tower h(n)=2*h(n-1)+1 h(1)=1 初始所有铜片都在a柱上 procedure hanoi(n,a,b,c:byte); {将第n块铜片从a柱通过b柱移到c柱上} begin if n=0 then exit; hanoi(n-1,a,c,b); {将上面的n-1块从a柱通过c柱移到b柱上} write(n,’moved from’,a,’to’,c); hanoi(n-1,b,a,c);{ 将b上的n-1块从b柱通过a柱移到c柱上 end; 初始铜片分布在3个柱上，给定目标柱goal h[1..3,0..n]存放三个柱的状态，now与nowp存最大的不到位的铜片的柱号和编号,h[I,0]存第I个柱上的个数。 Procedure move(k,goal:integer); {将最大不到位的k移到目标柱goal上} Begin If k=0 then exit; For I:=1 to 3 do For j:=1 to han[I,0] do If h[I,j]=k then begin now:=I;nowp:=j; end; {找到k的位置} If now<>goal then begin {若未移到目标} Move(k-1,6-now-goal); {剩下的先移到没用的柱上} Writeln(k moved from now to goal); H[goal,h[goal,0]+1]:=h[now,nowp]; h[now,nowp]:=0; Inc(h[goal,0]); dec(h[now,0]); Move(k-1,goal); {剩下的移到目标上} End; 十二、DFS框架 NOIP2001 数的划分 procedure work(dep,pre,s:longint); {入口为work(1,1,n)} {dep为当前试放的第dep个数,pre为前一次试放的数,s为当前剩余可分的总数} var j:longint; begin if dep=n then begin if s>=pre then inc(r); exit; end; for j:=pre to s div 2 do work(dep+1,j,s-j); end; 类似： procedure try(dep:integer); var i:integer; begin if dep=k then begin if tot>=a[dep-1] then inc(sum); exit; end; for i:=a[dep-1] to tot div 2 do begin a[dep]:=i; dec(tot,i); try(dep+1); inc(tot,i); end; end;{try} 十三、BFS框架 IOI94 房间问题 head:=1; tail:=0; while tail for k:=1 to n do if k方向可扩展 then begin inc(head); list[head].x:=list[tail].x+dx[k]; {扩展出新结点list[head]} list[head].y:=list[tail].y+dy[k]; 处理新结点list[head]; end; end; 十五、数据结构相关算法 1．链表的定位函数loc(I:integer):pointer; {寻找链表中的第I个结点的指针} procedure loc(L:linklist; I:integer):pointer; var p:pointer; j:integer; begin p:=L.head; j:=0; if (I>=1) and (I<=L.len) then while j 2．单链表的插入操作 procedure insert(L:linklist; I:integer; x:datatype); var p,q:pointer; begin p:=loc(L,I); new(q); q^.data:=x; q^.next:=p^.next; p^.next:=q;
相关推荐：
loading