answer_4.htm

软件设计师模拟试卷,点击里面的Exe文件可以随机出题

10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>stack</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>++top</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>6</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rep = 0<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span style='mso-bidi-font-size:10.5pt;font-family:
宋体;mso-hansi-font-family:"Times New Roman"'>【解析】试题提供了两种解决问题的方法，程序</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5.1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>是用递归的方法来解决背包问题，程序</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5.2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>使用非递归的方法来解决背包问题。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个<span
lang=EN-US>&quot;背包问题&quot;。程序从数组下标最大的物品开始考查，因此（</span></span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）处应该填<span lang=EN-US>&quot;</span></span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>knap</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>s-w</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>,n-1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）<span
lang=EN-US>&quot;，即将数组中第</span></span><span lang=EN-US style='mso-bidi-font-size:
10.5pt'>N</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-hansi-font-family:"Times New Roman"'>个物品放入背包，如果它能够放入到背包中，则该物品是构成解的元素之一；否则，将该物品从背包中取出，该物品不构成解的元素，在以后的考查中，它可以被排除，因此（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）处应该填<span
lang=EN-US>&quot;</span></span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>knap</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>s,n-1</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）<span
lang=EN-US>&quot;。在改程序中用栈来保存已经考查过的物品，结构</span></span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>KNAPTP</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示经过考查的物品，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>s</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示考查过该物品后背包所能够盛放的物品的重量；</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示该物品在数组</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>W</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>中的下标；</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>job</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示物品当前的状态：当</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>job</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>等于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，表示物品</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>可以放入背包；</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>job</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>等于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示物品</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>不能被放入到背包，那么在以后的选取中将不再考虑该物品。初始时</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>job</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>等于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，表示背包中没有任何放入任何物品。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>K</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为有解的标志。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Rep</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>为一个标志变量，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rep</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>等于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，表示结束当前的动作；</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rep</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>等于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示继续进行当前的动作。当栈顶物品不能放入背包时，将</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rep</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>设置为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，表示下一步不从数组</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>w</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>中取物品。其初值为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>。开始时，将数组中下标最大的物品放入栈中，然后开始考查该物品。该物品满足放入背包的条件，第（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>4</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）空将完成将物品放入背包的操作，因此（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>4</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）空填<span
lang=EN-US>&quot;</span></span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>x.s-w</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>x.n--</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］<span
lang=EN-US>&quot;，修改背包的可容纳物品的重量；（</span></span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>5</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）处填<span lang=EN-US>&quot;</span></span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>stack</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>++top</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］<span
lang=EN-US>&quot;，将下一个要考查的物品放入栈中。若该物品不满足放入背包的条件，则将该物品从背包中取出，因此将</span></span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rep</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>置为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，结束循环</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>while</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>!k&amp;&amp;rep</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）。将物品从背包中取出，即释放该物品在背包中所占的重量，并标记为不能放入到背包（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>job=2</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>），再将其放入到栈中；然后继续考查数组</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>w</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>中的下一个物品，因此需要结束循环</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>while</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>top&gt;=1&amp;&amp;rep</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>），将</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>rep</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>置为</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，所以第（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>6</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>）处应该填<span
lang=EN-US>&quot;</span></span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>rep=0</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>&quot;。在第三处要求给出循环结束的条件，即可以继续选取物品的条件，在此处填&quot;</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>top&gt;=1&amp;&amp;!k</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>&quot;。</span><span style='font-size:8.5pt;font-family:"MS Sans Serif";
mso-font-kerning:0pt;mso-ansi-language:ZH-CN'><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

</div>

</body>

</html>