(3)把算法设计成循环结构 *6-13背包问题。设有一个背包可以放入物品的重量为s,现有n件物品,重量分别为 w0],w[1]-…,n-1]l问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之 和正好等于s。如果存在一种符合上述要求的选择,则称此背包问题有解;否则称此背包问 题无解。试用分而治之的算法设计方法设计求解背包问题的函数 提示:此背包问题的递推定义如下(其中True表示有解, False表示无解): True s=0 此时问题有解 False s<0 总重量不能为负数 KNAP(S, n)= False s>0且n<1物品件数不能为负数 KMAP(s,n-1)s>0且n≥1所选物品不包括{n-1时 KNAP(s-{m-1n-1)s>0且n≥1所选物品包括n-1时 上机实习题 6-14折半査找问题。折半査找问题的描述见61节,折半查找问题的递归算法见例6-2 要求: (1)设计折半査找问题的循环结构算法 (2)设计一个查找成功的例子和一个查找不成功的例子,并设计测试主程序 *(3)设计一个包含10000个数据元素的查找成功的例子,然后分别调用循环结构的查 找算法和递归结构的査找算法,并测试出两种算法在计算机上的实际运行时间。 *6-15八皇后问题。设在初始状态下在国际象棋棋盘上没有任何棋子(这里的棋子指皇 后棋子)。然后顺序在第1行,第2行,…,第8行上布放棋子。在每一行中共有8个可选 择位置,但在任一个时刻棋盘的合法布局都必须满足3个限制条件:1)任意两个棋子不得 放在同一行上:2)任意两个棋子不得放在同一列上:3)任意两个棋子不得放在同一正斜线 和反斜线上 (1)试用回溯法的算法设计方法编写一个函数,求解并输出此问题的一个合法布局 (2)试用回溯法的算法设计方法编写一个函数,求解并输出此问题的所有合法布局 提示:在第ⅰ行布放棋子时,从第1列到第8列逐列考察。当在第ⅰ行第j列布放棋子 时,需要考察布放棋子后在行方向、列方向、正斜线方向和反斜线方向上的布局状态是否合 法,若该棋子布放合法,再递归求解在第计1行布放棋子:若该棋子布放不合法,移去这个 棋子,恢复布放该棋子前的状态,然后再试探在第i行第j+1列布放棋子（3）把算法设计成循环结构。 *6-13 背包问题。设有一个背包可以放入物品的重量为 s，现有 n 件物品，重量分别为 w[0],w[1],...,[n-1]。问题是能否从这 n 件物品中选择若干件放入此背包中使得放入的重量之 和正好等于 s。如果存在一种符合上述要求的选择，则称此背包问题有解；否则称此背包问 题无解。试用分而治之的算法设计方法设计求解背包问题的函数。 提示：此背包问题的递推定义如下（其中 True 表示有解，False 表示无解）： 上机实习题： 6-14 折半查找问题。折半查找问题的描述见 6.1 节，折半查找问题的递归算法见例 6-2。 要求： （1）设计折半查找问题的循环结构算法； （2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序； *（3）设计一个包含 10000 个数据元素的查找成功的例子，然后分别调用循环结构的查 找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。 *6-15 八皇后问题。设在初始状态下在国际象棋棋盘上没有任何棋子（这里的棋子指皇 后棋子）。然后顺序在第 1 行，第 2 行，…，第 8 行上布放棋子。在每一行中共有 8 个可选 择位置，但在任一个时刻棋盘的合法布局都必须满足 3 个限制条件：1）任意两个棋子不得 放在同一行上；2）任意两个棋子不得放在同一列上；3）任意两个棋子不得放在同一正斜线 和反斜线上。 （1）试用回溯法的算法设计方法编写一个函数，求解并输出此问题的一个合法布局； （2）试用回溯法的算法设计方法编写一个函数，求解并输出此问题的所有合法布局。 提示：在第 i 行布放棋子时，从第 1 列到第 8 列逐列考察。当在第 i 行第 j 列布放棋子 时，需要考察布放棋子后在行方向、列方向、正斜线方向和反斜线方向上的布局状态是否合 法，若该棋子布放合法，再递归求解在第 i+1 行布放棋子；若该棋子布放不合法，移去这个 棋子，恢复布放该棋子前的状态，然后再试探在第 i 行第 j+1 列布放棋子。          − − −   − −   −    = = 且 所选物品包括 时 且 所选物品不包括 时 且 物品件数不能为负数 总重量不能为负数 此时问题有解 ( [ 1], 1) 0 1 [ 1] ( , 1) 0 1 [ 1] 0 1 0 0 ( , ) KNAP s w n n s n w n KNAP s n s n w n False s n False s True s KNAP s n