注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

PASCAL语言程序设计——程序设计与基本算法(二)  

2015-03-18 20:06:21|  分类: 教书育人 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

第二节 回溯算法

 

在一些问题求解进程中,有时发现所选用的试探性操作不是最佳选择,需退回一步,另选一种操作进行试探,这就是回溯算法。

 

[6.6] 中国象棋半张棋盘如下,马自左下角往右上角跳。现规定只许往右跳,不许往左跳。比如下图所示为一种跳行路线。编程输出所有的跳行路线,打印格式如下:

<1>  (0,0)—(1,2)—(3,3)—(4,1)—(5,3)—(7,2)—(8,4)

                 PASCAL语言程序设计——程序设计与基本算法(二)  - 东埠中学----信息技术 - 东埠中学----信息技术

解:按象棋规则,马往右跳行的方向如下表和图所示:
PASCAL语言程序设计——程序设计与基本算法(二)  - 东埠中学----信息技术 - 东埠中学----信息技术

水平方向用x表示垂直方向用y表示。右上角点为x=8, y=4, 记为(8, 4) 用数组tt存放x方向能成行到达的点坐标;用数组t存放y方向能成行到达的点坐标;

①以(tt(K), t(k))为起点,按顺序用四个方向试探,找到下一个可行的点(x1, y1);

②判断找到的点是否合理 (不出界),若合理,就存入tt和t中;如果到达目的就打印,否则重复第⑴步骤;

③如果不合理,则换一个方向试探,如果四个方向都已试过,就退回一步(回溯),用未试过的方向继续试探。重复步骤⑴;

④如果已退回到原点,则程序结束。

Pascal程序:

Program Exam66;

   Const  xxarray[1..4] of 1..2 =(1,2,2,1);

          yyarray[1..4] of -2..2=(2,1,-1,-2);

   Var pinteger;

      ttt array[0..10] of integer;

   procedure Prn(kinteger);

       Var iinteger;

       Begin

           inc(p);  write(p2 >   :40,0);

           for i:=1 to k do

               write( ( tt[ I ] t[ I ]) );

           writeln

       End;

   Procedure Sub(kinteger);

       Var x1y1iinteger;

       Begin

           for I:=1 to 4 do

               Begin

                   x1:=tt[k-1]+xx[ i ];  y1:=t[k-1]+yy[ i ];

                   if not( (x1 > 8) or (y1 < 0) or (y1 > 4) ) then

                       Begin

                           tt[k]:=x1;  t[k]=y1;

                           if (y1=4) and (x1=8) then prn(k);

                           sub(k+1);

                       end;

               end;

       end;

   Begin

       p:=0;  tt[0]:=0;  t[0]:=0;

       sub(1);

       writeln(  From 0,0 to 8,4  All of the ways are p);

       readln

   end.

 

[6.7] 输出自然数1到n所有不重复的排列,即n的全排列。

解:①在1~n间选择一个数,只要这个数不重复,就选中放入a数组中;

②如果这个数巳被选中,就在d数组中作一个被选中的标记 (将数组元素置1 );

③如果所选中的数已被占用(作了标记),就另选一个数进行试探;

④如果未作标记的数都已试探完毕,那就取消最后那个数的标记,退回一步,并取消这一步的选数标记,另换下一个数试探,转步骤①;

⑤如果已退回到0,说明已试探全部数据,结束。

Pascal程序:

Program Exam67;

   Var p,ninteger;

       a,darray[1..500] of integer;

   Procedure prn (t integer);

       Var iinteger;

       Begin

           write( < p:3 >   :10);

           for I:=1 to t do

               write(a[ I ]:4);

           writeln;

       end;

   Procedure pp(kinteger);

       var xinteger;

       begin

           for x:=1 to n do

               begin

                   a[k]:=xd[x]:=1;

                   if k < n then pp(k+1)

                   else

                       begin

                           p:=p+1;

                           prn(k);

                       end;

              end;

       end;

   Begin

       write(Input n=);  readln(n);

       for p:=1 to n do d[p]=0;

       p:=0;

       pp(1);

       writeln(All of the ways are p:6);

   End.

 

[6.8] 设有一个连接n个地点①—⑥的道路网,找出从起点①出发到过终点⑥的一切路径,要求在每条路径上任一地点最多只能通过一次。

PASCAL语言程序设计——程序设计与基本算法(二)  - 东埠中学----信息技术 - 东埠中学----信息技术

 

解:从①出发,下一点可到达②或③,可以分支。具体步骤为:

⑴假定从起点出发数起第k个点Path[k],如果该点是终点n就打印一条路径;

⑵如果不是终点n,且前方点是未曾走过的点,则走到前方点,定(k+1)点为到达路径,转步骤⑴;

(3)如果前方点已走过,就选另一分支点;

(4)如果前方点已选完,就回溯一步,选另一分支点为出发点;

(5)如果已回溯到起点,则结束。

为了表示各点的连通关系,建立如下的关系矩阵:

PASCAL语言程序设计——程序设计与基本算法(二)  - 东埠中学----信息技术 - 东埠中学----信息技术
 

 

第一行表示与①相通点有②③,0是结束标志;以后各行依此类推。

 

集合b是为了检查不重复点。

 

Program Exam68;

const n=6;

    roadnetarray[1..n1..n] of 0..n=( (2,3,0,0,0,0),

                                            (1,3,4,0,0,0),

                                                  (1,2,4,5,0,0),

                                                  (2,3,5,6,0,0),

                                                  (3,4,6,0,0,0),

                                                  (4,5,0,0,0,0) );

var bset of 1..n;

   patharray[1..n] of 1..n;

   pbyte;

 procedure prn(kbyte);

 var ibyte;

 begin

   inc(p)write(<p:2> :4);

   write (path[1]:2);

   for I:=2 to k do

    write (--path[ i ]:2);

   writeln

 end;

 procedure try(kbyte);

 var jbyte;

 begin

   j:=1;

   repeat

   path[k]:=roadnet [path [k-1]j ];

   if not (path [k] in b) then

      begin b:=b+[path [k] ];

       if path [k]=n then prn (k)

        else try(k+1);

       b:=b-[path [k] ];

      end;

   inc(j);

   until roadnet [path [k-1]j ]=0

 end;

begin

  b:=[1]p=0path[1]:=1;

  try(2);

  readln

end.

 

 

习题[6.2]

  1. 右下图所示的是空心框架,它是由六个单位正方体组成,:从框架左下外顶点走到右上内顶点共有多少条最短路线?

 

PASCAL语言程序设计——程序设计与基本算法(二)  - 东埠中学----信息技术 - 东埠中学----信息技术

2.有M×N张(M行N列)邮票连在一起,

    但其中第X张被一个调皮的小朋友控掉了。下图是3×5的邮票的形状和编号。从这些邮票中撕出四张连在一起的邮票,问共有多少种这样四张一组的邮票?注:因为给邮票编了序号,所以1234和2345应该看作是不同的两组。
 

 1

 2

 3

 4

 5

 6

 X

 8

 9

10

11

12

13

14

15

  3.八皇后问题。在8*8的国际象棋盘上摆上8个皇后。要求每行,每列,各对角线上的皇后都不能互相攻击,给出所可能的摆法。

  评论这张
 
阅读(133)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017