您所在位置：网站首页 > 医学/心理学 > 基础医学pascal中级教程第一章回溯法

pascal中级教程第一章回溯法

24页

卖家[上传人]：壹****1

文档编号：464535478

上传时间：2023-12-17

文档格式：DOC

文档大小：87.50KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

20 金贝

/ 24 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第一章回溯法1.1 马拦过河卒源程序名 knight.?（pas, c, cpp）可执行文件名 knight.exe输入文件名 knight.in输出文件名 knight.out【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【输入】一行四个数据，分别表示B点坐标和马的坐标。【输出】一个数据，表示所有的路径条数。【样例】knight.in knight.out6 6 3 36【算法分析】从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行

2、会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。1.2出栈序列统计源程序名 stack1.?（pas, c, cpp）可执行文件名 stack1.exe输入文件名 stack1.in输出文件名 stack1.out【问题描述】栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，n，经过一系列操作可能得到的输出序列总数。【输入】一个整数n（1=nY被用来表示当集合X中的域被赋值后，集合Y的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号”（S）、“姓名”（N）、“地址”（A）、“电话”（P）的域，并且每个人都与某个特定的互不相同的S值相对应，根据域S就可以确定域N、A、P的值。这就记作S-NAP。写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如，如果组里包括依赖A-B、B-C和A-

3、C，那么第三个依赖是冗余的，因为域C可以用前两个依赖得到（域A确定了域B的值，同样域B确定了域C的值)。在A-B、B-C、C-A、A-C、C-B和B-A中，所有的依赖都是冗余的。现在要求你编写一个程序，从给定的依赖关系中找出冗余的。【输入】输A的文件第一行是一个不超过100的整数n，它表示文件中函数依赖的个数。从第二行起每一行是一个函数依赖且互不重复，每行包含用字符“-”和“”隔开的非空域列表。列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如A-A）。虽然文件中没有对函数依赖编号，但其顺序就是编号1到n。【输出】每一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的，先是一个FD，然后是依赖函数号，接着是is redundant using FDs：”最后是说明的序列号。如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些函数依赖中不包含冗余依赖，则输出“No redundant FDs”信息。【样例1】【样例2】redund.inredund.out redund.in redund.out3FD 3

4、is redundant using FDs: 1 2 6 FD 3 is redundant using FDs: 1A-BD即C可以通过1、2得到 P-RST FD 5 is redundant using FDs: 4 6 2BD-C VRT-SQPA-C PS-TQ-TRQS-PSR-V【算法分析】一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？假设判断的依赖为“a-b”，先找出所有形式为“a-*”的依赖，再由*开始找相关依赖，直到出现“#-b”为止(这里a、b、*、#都表示任意一个域名)。如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗余(如果有的话)还不说明工作就已结束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的(最短的也可能并不惟一，因此本题答案有可能并不惟一)，最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证明序列中就有可能还有冗余依赖。1.5走迷宫源程序名 maze.?（pas, c, cpp）可执行文件名 maze.exe输入文件名 maze.in输出文件名 maze.out【问题

5、描述】有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。【输入】第一行是两个数m，n(1m，n”表示方向。如果没有一条可行的路则输出-1。【样例】maze.in5 61 0 0 1 0 11 1 1 1 1 10 0 1 1 1 01 1 1 1 1 01 1 1 0 1 11 15 6maze.out(1,2)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(3,4)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,

《pascal中级教程第一章回溯法》由会员壹****1分享，可在线阅读，更多相关《pascal中级教程第一章回溯法》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源

河南省宏力学校级高二地理世界地理复习专题东南亚教学案

XXHDPE中空壁缠绕管研制与开发项目可行性分析报告正文电大考试必备小抄

淮北船舶电气设备销售项目建议书_参考模板

用友NC基本介绍

2023关于奉献的演讲稿锦集七篇

数学语言在初中数学教学中的重要性

小升初总复习第十一讲——典型应用题

最新人教版英语九年级下册教案全册

导师推荐信范文

幼儿园卫生保健2023年度工作总结（2篇）.doc

建设工程施工合同

湛江钢铁项目可能会对环境资源造成破坏

2020年医德医风个人年终总结-

2011中考英语句型

金属材料热处理课程设计说明书(凹模)

垫环螺栓规格

湖南省湘潭市高三数学第四次模拟考试试卷理湘教版

2022年会计专科考前难点冲刺押题卷含答案248

家具采购合同集锦15篇

驻村工作自我鉴定

点击查看更多

新上传的WORD文档

森兰变频器在自来水厂的恒压供水系统解决方案时域和频域信道估计比较12页除尘工理论鉴定考试题室内设计色彩搭配学大全市场营销经济环境调查赵县双庙资料餐厅经理下半年工作计划范本.doc 尽早识字的意义与价值海拔高程换算 ss数对字化轻便式轨道几何状态检测仪可研报告二乙氨乙基纤维素层析简介教师课题研究活动总结 40B万能粉碎机操作、维护、保养规程我对社团工作感想和建议东北大学21秋《工程材料学基础》平时作业一参考答案45