cs5.htm

文章说明的程序设计

&quot;Times New Roman&quot;">、</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:
8.0pt">【背包问题】设有一个背包可以放入的物品的重量为</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">s</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">，现有</span><span lang="EN-US" style="mso-font-kerning:8.0pt">n</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">件物品，重量分别为</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">w[1], w[2], </span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:
8.0pt">…</span><span lang="EN-US" style="mso-font-kerning:8.0pt">, w[n]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">。问能否从这</span><span lang="EN-US" style="mso-font-kerning:8.0pt">n</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:
8.0pt">件物品中选择若干件放入此背包中，使得放入的重量之和正好为</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">s</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">。如果存在一种符合上述要求的选择，则称此背包问题有解</span><span lang="EN-US" style="mso-font-kerning:8.0pt">(</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">或称其解为真</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">；否则称此背包问题无解</span><span lang="EN-US" style="mso-font-kerning:8.0pt">(</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">或称其解为假</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：）</span><span lang="EN-US" style="mso-font-kerning:8.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height: 150%"><span lang="EN-US" style="mso-font-kerning:8.0pt"><span style="mso-tab-count:2">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</span><span style="mso-text-raise:-43.0pt"><!--[if gte vml 1]><v:shapetype id="_x0000_t75"
 coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe"
 filled="f" stroked="f">
 <v:stroke joinstyle="miter"/>
 <v:formulas>
  <v:f eqn="if lineDrawn pixelLineWidth 0"/>
  <v:f eqn="sum @0 1 0"/>
  <v:f eqn="sum 0 0 @1"/>
  <v:f eqn="prod @2 1 2"/>
  <v:f eqn="prod @3 21600 pixelWidth"/>
  <v:f eqn="prod @3 21600 pixelHeight"/>
  <v:f eqn="sum @0 0 1"/>
  <v:f eqn="prod @6 1 2"/>
  <v:f eqn="prod @7 21600 pixelWidth"/>
  <v:f eqn="sum @8 21600 0"/>
  <v:f eqn="prod @7 21600 pixelHeight"/>
  <v:f eqn="sum @10 21600 0"/>
 </v:formulas>
 <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
 <o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:326.25pt;
 height:77.25pt' o:ole="" fillcolor="window">
 <v:imagedata src="file:///C:/DOCUME~1/wangsj/LOCALS~1/Temp/msoclip1/01/clip_image001.wmz"
  o:title=""/>
</v:shape><![endif]-->
<img src="../tp/cs5.ht6.gif" v:shapes="_x0000_i1025" width="435" height="103"></span><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
  DrawAspect="Content" ObjectID="_1083003495">
 </o:OLEObject>
</xml><![endif]-->
<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height: 150%"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height: 150%"><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">、</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:
8.0pt">【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">(</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">皇后</span><span lang="EN-US" style="mso-font-kerning:8.0pt">)</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">。然后顺序在第</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">1</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">行，第</span><span lang="EN-US" style="mso-font-kerning:8.0pt">2</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">行，…。第</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">8</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">行上布放棋子。在每一行中有</span><span lang="EN-US" style="mso-font-kerning:8.0pt">8</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">个可选择位置，但在任一时刻，棋盘的合法布局都必须满足</span><span lang="EN-US" style="mso-font-kerning:8.0pt">3</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:
8.0pt">个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。</span><span lang="EN-US" style="mso-font-kerning:8.0pt">(</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">提示：用回溯法。在第</span><span lang="EN-US" style="mso-font-kerning:
8.0pt">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-font-kerning:8.0pt">行第</span><span lang="EN-US" style="mso-font-kerning:8.0pt">j</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第</span><span lang="EN-US" style="mso-font-kerning:8.0pt">j+1</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;
mso-font-kerning:8.0pt">列。</span><span lang="EN-US" style="mso-font-kerning:8.0pt">)<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="line-height: 150%"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>

</body>

</html>