pascal语言程序设计四步辅导法(编辑修改稿)

pascal语言程序设计四步辅导法(编辑修改稿)内容摘要：

从图中可以看出，从城市 A到城市 H要经过若干个城市。 求出一 条经过城市最少的一条路线。 12 图 8 看到图 8 很容易想到用邻接距阵来表示， 0 表示能走， 1 表示不能走。 如图 9： 图 9 用队来解题，我们可以 a 记录搜索过程， 记录经过的城市， 记录前趋元素，这样就可以倒推出最短线路。 具体过程如下 将城市 A入队，队首、队尾都为 1。 将队首所指的城市所有可直通的城 市入队（如果这个城市在队中出现过就不入队，可用一个集合来判断），将入队城市的 pre指向队首的位置。 然后将队首加 1，得到新的队首城市。 重复以上步骤，直到城市 H 入队为止。 当搜到城市 H 时，搜索结束。 利用 pre 可倒推出最少城市线路。 PASCAL 源程序： const ju:array[1..8,1..8] of 0..1=( (1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1))。 type r=record {记录定义 } city:array[1..100] of char。 pre:array[1..100] of integer。 end。 var h,d,i:integer。 a:r。 s:set of 39。 A39。 ..39。 H39。 procedure out。 {输出过程 } begin write([d])。 repeat d:=[d]。 write(39。 39。 ,[d])。 until [d]=0。 13 writeln。 halt。 end。 procedure doit。 begin h:=0。 d:=1。 [1]:=39。 A39。 [1]:=0。 s:=[39。 A39。 ]。 repeat {步骤 2} inc(h)。 {队首加一，出队 } for i:=1 to 8 do {搜索可直通的城市 } if （ ju[ord([h])64,i]=0） and （ not（ chr（ i+64） in s）） then {判断城市是否走过 } begin inc(d)。 {队尾加一，入队 } [d]:=chr(64+i)。 [d]:=h。 s:=s+[[d]]。 if [d]=39。 H39。 then out。 end。 until h=d。 end。 begin {主程序 } doit。 end. 输出： HF—A 通过数学方式重新审题 有些问题有很多精妙的数学解法，选手可以从数据角度（多角度）审题，如能归纳出数学公式解题，效率和准确性会有很大的提高。 例如前文提到的一题： 计算从 1开始的前 100个自然数的和”的算法。 运用图 4 所列出的公式（ S 的值来源于等差数列，用求等差级数前 N 项和的公式），可以轻松求解。 这种方法只需做一次加法和二次乘法，所以数学公式算法比其它算法运算量小，效率高。 再如：“栈”一题（问题略，可参见 2020 年普及组复赛试题三） 此题可以用动态规划求解，但在审题中，我们分析出：若设 入栈为 1，出栈为 0（不入栈为 10），对于任意一种方案，与 2n 位的 01 序列一一对应（在前任意位， 1的个数总是大于等于 0的个数）。 可以证明，在 2 的 0 任意排列中，不符合要求的个数为： ，则可产生出的序列数： ，即为 n 的 Catalan 数。 14 选手写阶乘的程序比较容易， PASCAL 程序如下： program stacks。 var n,m:longint。 function jc(n:integer):longint。 var i,s:longint。 begin s:=1。 for i:=1 to n do s:=s*i。 jc:=s。 end。 function jm(n,m:integer):real。 begin jm:=jc(n)/(jc(m)*jc(nm))。 end。 begin write(39。 input n:39。 )。 readln(n)。 writeln(jm(2*n,n)/(n+1))。 readln end. （二）建模 运用已经掌握的知识，快速与命题建立联系 穷举法是常用的算法， 穷举是穷举出所有可 能满足题意的情形，并从中找出符合要求的解，是最直观的循环算法。 在讲解 LOGO、 BASIC、 PASCAL 语言中都要讲到，这个基础算法可以被选手熟练掌握，当遇到类似问题时，就会很容易产生联系，便于建立模型。 如穷举法的经典例题，百鸡百钱问题：用 100钱买 100只鸡。 其中母鸡 5 钱一只，公鸡 3 钱一只，小鸡 1 钱三只，试编程求可买母鸡、公鸡、小鸡各多少只。 LOGO 语言源程序： TO B FOR X 0 20[FOR Y 0 33[FOR Z 0 100 [ IF AND :X+:Y+:Z=100 5*:X+3*:Y+:Z/3=100 THEN (PR :X :Y :Z)]] ] END 这个模型在此不再赘述，当选手在遇到类似的结构描述时，就会很快建立解题的模型，如： 找出 n个自然数 (1,2,3,„ ,n)中 r个数的组合。 例如，当 n=５ ,r=3时，所有组合为 ： ５ ４ ３ ５ ４ ２ ５ ４ １ ５ ３ ２ ５ ３ １ ５ ２ １ ４ ３ ２ ４ ３ １ 15 ４ ２ １ ３ ２ １ total=10 {组合的总数 } 此题中， n 个数中 r 的组合，其中每 r 个数中，数不能相同。 另外，任何两组组合的数，所包含的数也不应相同。 例如，５、４、３与３、４、５。 为此，约定前一个数应大于后一个数。 将上述两 条不允许为条件，当 r=3时，因为有前面 百鸡百钱的知识，选手比较容易建立模型，即 三重循环进行穷举： PASCAL 程序： program qje。 const n=5。 var i,j,k,t:integer。 begin t:=0。 for i:=n downto 1 do for j:=n downto 1 do for k:=n downto 1 do if (ij)and(ik)and(ij)and(jk) then begin t:=t+1。 writeln(i:3,j:3,k:3)。 end。 writeln(39。 total=39。 ,t)。 end. 所以，对于经典例题的模型的辅导是比较重要的，是学生建模的知识积累。 根据运算量及数据范围，确定存储结构、数据结构 PASCAL 语言解题的过程之前一定要进行数据的存储，良好的存储结构和数据结构是建模的基础，好的数 据结构是成功求解的关键。 如回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构， 其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。 具体的算法描述如下： 非递归算法： Type Node(节点类型 )＝ Record Situtation:TSituation（当前节点状态）。 WayNO:Integer（已使用过的扩展规则的数目）。 End Var List(回溯表 ):Array[1..Max(最大深 度 )] of Node。 pos(当前扩展节点编号 ):Integer。 Init List0。 pos1。 List[1].Situation初始状态。 Main Program While (pos0(有路可走 )) and ([未达到目标 ]) do Begin If pos=Max then (数据溢出 ,跳出主程序 )。 List[pos].WayNO:=List[pos].WayNo+1。 If (List[pos].WayNO=TotalExpendMethod) then (如果还有没用过的扩展规则 ) Begin 16 If (可以使用当前扩展规则 ) then Begin (用第 way 条规则扩展当前节点 ) List[pos+1].Situation:=ExpendNode(List[pos].Situation, List[pos].WayNO)。 List[pos+1].WayNO:=0。 pos:=pos+1。 EndIf。 EndIf Else Begin pos:=pos1。 EndElse EndWhile。 递归算法： Procedure BackTrack(Situation:TSituation。 deepth:Integer)。 Var I :Integer。 Begin If deepthMax then (空间达到极限 ,跳出本过程 )。 If Situation=Target then (找到目标 )。 For I:=1 to TotalExpendMethod do Begin BackTrack(ExpendNode(Situation,I),deepth+1)。 EndFor。 End。 回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。 如八皇后问题： 问题描述： 求出在一个 nn的棋盘上，放置 n个不能互相捕捉的 “皇后 ”的所有布局。 算法分析 ： 这是来源于国际象棋的一个问题。 皇后可以前、后、左、右和沿着对角线方向相互捕捉。 一个合适的解应是在每列、每行确实有一个皇后，且在一条对角线上最多只有一个皇后。 在写程序之前，设定表示棋盘的数据结构是一个 n n 数组。 每一个位置代表棋盘上的一个方格。 然而考虑到一个合理的解中每列、每行只能放置一个皇后，棋盘也可用一个一维数组来表示。 数组的每一个元素代表棋盘的一列，该元素的值是皇后在该列上的行位置。 为找到一个解，必须从空布局开始，每放置一个皇后要检查布局是否合理。 在合理的情况下，试探找下一个皇后的位置；如果布局不合理，就改变布局。 重复检查、试探或检查、改变位置，直到找到最后一个皇后的合理位置 ，这时就找到一个合理的布局。 重复以上过程直到无法再改变皇后位置为止，就可找到所有合理的布局。 PASCAL 的源程序为： program j。 const n=8。 var x:array [1..100] of integer。 cont:integer。 17 procedure print。 var i:integer。 begin cont:=cont+1。 for i:=1 to n do write(x[i])。 writeln(39。 S:39。 ,cont)。 end。 function try(i,k:integer):boolean。 var j:integer。 begin j:=1。 while jk do begin if(x[j]=i)or(abs(x[j]i)=abs(jk)) then begin try:=false。 exit end。 j:=j+1。 end。 try:=true。 end。 procedure place(k:integer)。 var i:integer。 begin if kn then print else for i:=1 to n do if try(i,k) then begin x[k]:=i。 place(k+1)。 end。