高中信息技术 全国青少年奥林匹克联赛教案 深度优先搜索和广度优先搜索VIP免费

全国青少年信息学奥林匹克联赛搜索基础算法一、深度搜索（DFS）从一个简单题目开始。例1．输出n个元素的无重复的全排列。（1<=n<=9）在这里我们可以对每一个元素编号，形成1,2,…,8,9个数字的全排列。我们用一个一维数组来处理，相当于有9个位置，每个位置可以放1到9，再进行重复性判断，即在每个位置放一个数字时判断它前面是否已经使用该数字。通过数组中元素值的变化，产生全排列。下面给出非递归例程，其中，变量k是表示位置指针，数组x用来装每个位置的值。constn=5;varx:array[1..10]ofinteger;k:integer;{位置指针}functiontry:boolean;{判重函数}vari:integer;beginfori:=1tok-1doifx[i]=x[k]thenbegintry:=false;exit;end;try:=true;end;procedureout;{输出过程}vari:integer;beginfori:=1tondowrite(x[i]);writeln;end;begink:=1;x[1]:=0;whilek>0dobegininc(x[k]);{当前第k个位置中增加1}ifx[k]>nthen{判断当前第k个位置中是否超界，超界指针后移一位}dec(k)elseiftrythen{判重}begininc(k);x[k]:=0;{前进1位}ifk>nthen{判断指针是否超界，决定一个排列是否完成,完成指针后移一位}beginout;dec(k);end;end;end;end.下面是递归例程：constn=5;varx:array[1..10]ofinteger;functiontry(v1,k:integer):boolean;{判重函数,v1表示位置，k表示所放的值}vari:integer;beginfori:=1tov1-1doifx[i]=kthenbegintry:=false;exit;end;try:=true;end;procedureout;{输出过程}vari:integer;beginfori:=1tondowrite(x[i]);writeln;end;proceduresearch(v:integer);{v表示第v个位置}vari:integer;beginifv>nthenbeginout;exit;end;{若v超界，一个排列完成}fori:=1tondo{在第v个位置上分别放1到n}iftry(v,i)then{如果不重复，处理第v+1个位置}beginx[v]:=i;search(v+1);end;end;beginsearch(1);end.说明：使用非递归的好处是节约内存，当一些题目对内存消耗较大时，建议使用非递归方式；但使用递归方式在程序运行时间上要好一些，因为在每个节点扩展时，递归方式少一个范围超界判断。例题一简单的背包问题。设有一个背包，可以放入的重量为s。现有n件物品，重量分别为均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。分析：可以设定n个位置，每个位置只能放0和1，这样形成一个0和1可重复的排列，或者是产生一个n位的2进制数。例程：varw:array[1..20]ofinteger;x:array[1..20]ofinteger;n:integer;s:longint;procedureinit;vari:integer;beginreadln(n,s);fori:=1tondoread(w[i]);end;functiontry(v1,k:integer):boolean;{判断目标函数,v1表示位置，k表示所放的值}vari:integer;s1:longint;begins1:=w[k];fori:=1tov1-1dos1:=s1+x[i]*w[i];ifs1=sthenbeginfori:=1tov1-1doifx[i]=0thenwrite(w[i],'');writeln(w[k]);end;ifs1>=sthenbegintry:=false;exit;end;elsetry:=true;end;proceduresearch(v:integer);{v表示第v个位置}vari:integer;beginifv>nthenexit;{若v超界，一个排列完成,本次选择物品方案不成功，退出}fori:=0to1do{在第v个位置上分别放0到1}iftry(v,i)then{判断所选物品之和是否大于等于s,否则处理第v+1个位置}beginx[v]:=i;search(v+1);end;end;begininit;search(1);end.说明：本文用全排列进行引入DFS搜索,目的是表明DFS有一定的模式，如下：proceduresearch(v:integer；相关形参);{v表示当前扩展节点层数（或者叫深度）}{过程定义的变量表}beginif<超界条件>thenbeginout;exit;end;{若v超界，out来作超界处理}形成某种节点扩展程序段（例如：fori:=1tondo）if〈判断所到节点的算法函数或条件〉then{例如判重}begin当前节点处理；search(v+1);{处理下一个层数}end;end;例题二给出一个自然数n(),把n分解为若干个大于1的自然数之乘积。请编写程序找出所有的分解方案。分析：此题目的关键是怎样产生需要扩展的各个节点。不难看出乘积为n的若干自然数，刚好都是n的约数。因此其分解方案变成了求这些约数的不同组合（元素可重复），问题得到解决。例程：vary:array[1..50]oflongint;{用来存放n的所有约数}x:array[0..50]ofinteger;{用来存放组合数的对应n...