《算法与程序设计习题(杨建英)第4章.docx》由会员分享，可在线阅读，更多相关《算法与程序设计习题(杨建英)第4章.docx（1页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
习题.袋鼠跳河问题：一只袋鼠要从河这边跳到河对岸，河很宽。但是河中间打了很多桩子，每隔 一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳得更远。每个弹簧力量 不同，用一个数字代表它的力量，如果弹簧力量为5,就代表袋鼠下一跳最多能够跳5米； 如果为0,就会陷进去无法继续跳跃。河一共N米宽，袋鼠的初始位置在第一个弹簧上面, 跳到最后一个弹簧之后就算过河了，设计一个算法解决此问题。1 .集合划分问题：给定一个图G,图G中任意两点的距离，请你把图G的所有点分成两个 子集，要求两个子集之间的所有点的距离和最大。（对于图G中的每一个点，我们可以设一 个数组，用。和1表示属于哪个子集。）.布线问题：在MXN的方格阵列中，指定一个起点a、一个终点b,要求找到起点到终点的 最短布线方案（最短路径）。2 .一个数组保存了 N个火柴棍，问是否可以使用这N个火柴棍摆成一个正方形？回溯法 如何设计？如何设计递归函数？递归的回溯搜索何时返回真，何时返回假？普通的回溯搜索 是否可以解决该问题？如何对深度搜索进行优化？