搜索
基本算法说明：红色的代码可以只看懂不背排序快速排序难度系数：**快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束.(必考，常用)例:输入一组数据小到大排序.程序1:programkspv;vara:array[1..100]ofinteger;i:integer;procedurequicksort(s,t:integer);//总的思想就是第s个节点派到它最后应该排的位置；vari,j,x,t1:integer;begini:=s;j:=t;x:=a[i];whileijdobeginwhile(a[j]=x)and(ji)doj:=j-1;ifjithenbegint1:=a[i];a[i]:=a[j];a[j]:=t1;end;while(a[i]=x)and(ij)doi:=i+1;ifijthenbegint1:=a[j];a[j]:=a[i];a[i]:=t1;endend;b[i]:=x;i:=i+1;j:=j-1;ifsjthenquicksort(s,j);ifitthenquicksort(i,t);end;beginwhilenoteof(input)dobeginreadln(n);fori:=1tondoread(a[i]);quicksort(a,1,n);fori:=1tondowrite(a[i]:5);end;end.快速是经常用的，要自己多多练习，最好是自己给自己几个题目，做到不看书都可以写出来。堆排序难度系数：***堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有Ri=R2i和Ri=R2i+1(或=)堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。堆排序的思想是：1）建初始堆（将结点[n/2],[n/2]-1,...3,2,1分别调成堆）2）当未排序完时输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。程序如下：programProject2;usesSysUtils;vara:array[1..100]ofinteger;n,i:integer;proceduresift(l,m:integer);vari,j,t:integer;begini:=l;j:=2*i;t:=a[i];whilej=mdobeginif(jm)and(a[j]a[j+1])thenj:=j+1;//当前节点跟两个子节点说我只跟你们之中最小的比ifta[j]thenbegina[i]:=a[j];i:=j;j:=2*i;//注意i和j已经改变了endelseexit;a[i]:=t;end;end;beginwhilenoteof(input)dobeginreadln(n);//输入的数组元素个数fori:=1tondoread(a[i]);//输入数组的元素fori:=(ndiv2)downto1dosift(i,n);{思考为什么要对第(ndiv2)个元素开始排序？具体自己写出测试的数据，跟踪，如果一个节点左右子节点都比它大，就什么都不做了，但是最小的那个可能在子节点的子，这样就达不到选择最小的目的，所以我们要保证当前要处理的节点的两棵子树已经完成了最小节点在根的工作。完成了以上的for循环之后我们才算完成了对排序，这个时候我们不能保证从第一层往下一个个的节点列出来结果是从小到大的，（注意，对排序只能保证根节点是最小的，这个对于任何一棵子树都适应），所以如果你要得到从小到大的结果就要不断的保存最小的结果（根）}fori:=ndownto2dobeginwrite(a[1]:4);a[1]:=a[i];{第一个已经最小了，我们要做的工作是处理剩下元素，所以把最后的一个元素覆盖第一个，然后排序.}sift(1,i-1);{这个时候第一个根节点的左右子树已经标准的堆排序树了，也就是说只要对第一个节点进行堆排序就行了，这个时候就要好好研究上面sift(l,m:integer)函数的具体跟踪工作了。}end;writeln(a[1]:4);end;end.堆排序有两个比较明显的优点：优点1.只要排好了之后，以后要找到最小的（或是最大的），只要在根的两个子节点找，但是如果你只是要找到不难两个选一个就行了，但是你如果还要继续找剩下最小的啊，所以你不能一走了之，你应该把当前的子节点（刚到根的最后的节点）派到它应该在的位置，为的就是达到堆排序树的状态，方便下来的找最小的节点。优点2.实现动态排序，如果其中一个节点被改变了，我们可以让它派到适当的位置，当然初学可能体会不了这一点。简单的搜索搜索没有加截支就是傻瓜搜索，基本没有这样的搜索谓的截支就是避免不必要的搜索）；几乎所有的搜索都跟宽度或深度有关，本人认为搜索加截支就是回溯了。所以20个算法里面没有回溯。题目难度系数：***PrblemAChessGuessA、B、C、D四名选手进行象棋比赛，赛前甲、乙、丙、丁四位棋迷对选手名次作了预测，他们的预测数据存储在文件guess.in中，每人的数据放一行，每行含四个数，分别表示A、B、C、D的名次，各个数用空格隔开，0代表不预测。如甲的数据若为：2431表示甲预测A第2名、B第4名、C第3名、D第1名。又如乙的数据若为：0304表示乙预测B第2名、D第4名，不对A、C作预测。若某棋迷猜中了n个选手的名次，称其成绩为n，比赛结束后发现各棋迷的成绩一样，此成绩存放在guess.in的第5行，请编程根据以上数据求出A、B、C、D的名次，用空格隔开写成文件guess.out的一行，例如若guess.in内容为：31042431102413421则guess.out内容为：2314programProject1;{$APPTYPECONSOLE}usesSysUtils;vara,b,c,d,n,i:integer;a1:array[1..4]ofinteger;b1:array[1..4]ofinteger;c1:array[1..4]ofinteger;d1:array[1..4]ofinteger;functiontf(varp,q:integer):integer;beginifp=qthentf:=1elsetf:=0;end;functiongoal:boolean;begingoal:=false;if(tf(a,a1[1])+tf(b,b1[1])+tf(c,c1[1])+tf(d,d1[1])=n)and(tf(a,a1[2])+tf(b,b1[2])+tf(c,c1[2])+tf(d,d1[2])=n)and(tf(a,a1[3])+tf(b,b1[3])+tf(c,c1[3])+tf(d,d1[3])=n)and(tf(a,a1[4])+tf(b,b1[4])+tf(c,c1[4])+tf(d,d1[4])=n)thengoal:=true;end;beginwhilenoteof(input)dobeginfori:=1to4doreadln(a1[i],b1[i],c1[i],d1[i]);readln(n);fora:=1to4doforb:=1to4doifabthenforc:=1to4doif(ab)and(ac)and(bc)thenbegind:=10-a-b-c;ifgoalthenbeginwriteln(a,'',b,'',c,'',d);end;end;end;end.题目难度系数：*****数码难题：283123164-8475765要求输出步数（其实可以输出整个过程的呢）程序如下：programnum8;usesSysUtils;typea33=array[1..3,1..3]of0..8;a4=array[1..4]of-1..1;node=recordch:a33;si,sj:1..3;pnt,dep:byte;end;constgoal:a33=((1,2,3),(8,0,4),(7,6,5));start:a33=((2,8,3),(1,6,4),(7,0,5));di:a4=(0,-1,0,1);dj:a4=(-1,0,1,0);vardata:array[1..100]ofnode;//用以保存产生得状态temp:node;r,k,ni,nj,head,tail,depth:integer;functioncheck(k:integer):boolean;//是否可以产生下一个状态beginni:=temp.si+di[k];nj:=temp.sj+dj[k];if(ni=1)and(ni=3)and(nj=1)and(nj=3)thencheck:=trueelsecheck:=false;end;functiondupe:boolean;//判断是否和已经产生的状态中复vari,j,k:integer;buf:boolean;beginbuf:=false;i:=0;repeatinc(i);buf:=true;forj:=1to3dofork:=1to3doifdata[i].ch[j,k]data[tail].ch[j,k]thenbuf:=false;untilbufor(i=tail-1);dupe:=buf;end;functiongoals:boolean;//判断是否为目标状态vari,j:byte;begingoals:=true;fori:=1to3doforj:=1to3doifdata[tail].ch[i,j]goal[i,j]thengoals:=false;end;proceduresolve;//这里有一种宽度搜索的思想beginwhilehead=taildobegininc(head);temp:=data[head];depth:=temp.dep;forr:=1to4doifcheck(r)thenbegininc(tail);data[tail]:=temp;withdata[tail]dobeginch[si,sj]:=ch[ni,nj];ch[ni,nj]:=0;si:=ni;sj:=nj;pnt:=head;dep:=depth+1;end;ifdupethendec(tail)elseifgoalsthenbeginwriteln(data[tail].dep);//readln;//如果要看结果就去掉//readln前面得”//”exit;end;end;end;end;beginhead:=0;tail:=1;withdata[1]dobeginch:=start;si:=3;sj:=2;pnt:=0;dep:=0;end;solve;end.这道题是在这里算难的了，理解可以在脑海中构造一棵搜索树（四叉树，一个点有四个子点）。简单的动态规划：“练好动态规划就练好了内功”，呵呵，动态规划确实是好东西。这里我们只是要求对动态规划（dynamicprogramming简称dp）有个基本的了解。【例题】难度系数：**数字三角形问题。738810277455265示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。如输入：5738810277445265输出：30【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序（这里采用逆推的方法）如下：prog