subject_62262.htm

vc

<p>
序号：62262 发表者：Romantic 发表日期：2003-11-25 17:31:07
<br>主题：算法初学，有几个问题不明白，请各位编程高手的哥哥姐姐帮帮忙
<br>内容：1.设a[0：n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。<BR><BR>2.考虑国际象棋棋盘上的某个位置的一个马，它是否能只走63步，正好走过除起点的其他63个位置各一次？如果有一种这样的走法，则称所走的路线为一条马的周游路线。试设计一个分治算法找出这样的一条马的周游路线。<BR><BR>3.在一个圆形的操场的周围摆着n堆石子。现要将石子有次序的合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。<BR><BR>4.给定n种物品和一背包。物品i的重量是wi,体积是bi，其价值为vi，背包的容量为C，容积为D。问如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？在选择装入背包的物品物品时，对每种物品只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解此问题的动态规划算法。<BR><BR>5.设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1&lt;=i&lt;=n，应如何安排n个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是每个顾客等待服务时间的总和。<BR><BR>6. 给定一个n位正整数a，去掉其中任意k&lt;=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。<BR><BR>7.设某一机器由n个部件组成，每个部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。<BR><BR>8.罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处在一个m×n的迷宫中，每个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是密闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入未封闭的房间。罗密欧位于迷宫的（p,q）方格中，他必须找出一条通向朱丽叶所在的（r,s）方格的路。在抵达朱丽叶方格之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶方格的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出一条道路。<BR><BR>9.栈式分支限界法将活结点表以后进先出(LIFO)的方式存储于一个栈中。试设计一个解0-1背包问题的栈式分支限界法，并说明栈式分支限界法与回溯法的区别。<BR><BR>10.试修改解装载问题和解0-1背包问题的优先队列式分支限界法，使<BR>其仅使用一个最大堆来存储活结点，而不必存储所产生的解空间树。<BR><BR>11.已知一个任务集合I={W,...Wn}(其中Wi是正整数)每个式作日可以划分m个时间段T={t1,t2...tm}要求将工作的任务在最少的工作日内安排我，Wi是任务的持续时间。<BR>（提示：<BR>{W1,W2...Wk}&nbsp;&nbsp; W1+W2+...+Wk1≤T<BR>每一列变成0-1背包）<BR><BR>
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：Romantic 回复日期：2003-11-25 17:31:28
<br>内容：第11题图
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：黑羽 回复日期：2003-11-25 18:44:11
<br>内容：第1道：作者：lbb(李彬彬)<BR>我把答案放在下面，可直接运行，我试过了，数据你可以自已改动一下，你用一下：<BR>#include &#34;stdafx.h&#34;<BR>#include &lt;math.h&gt;<BR>#include &lt;stdio.h&gt;<BR><BR>double a[100];//5是数组的长度，可以自已更改<BR>double x=62.5;//给x和a[100]赋值，然后下面是主要程序<BR><BR>void binary_search(int n1,int n2)<BR>{<BR><BR>int m;<BR>if(n1&gt;n2)<BR>{<BR>printf(&#34;error!&#34;);<BR>}<BR>else<BR>{ <BR>&nbsp;&nbsp;m=(int)((n1+n2)/2);<BR>if(a[m]==x)<BR>{<BR>&nbsp;&nbsp;printf(&#34;x在a中的位置为%d&#34;,m);<BR>}<BR>else<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;if((a[m]&lt;x)&amp;&amp;(a[m+1]&gt;x))<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;printf(&#34;x在a中的位置为%d 与 %d之间&#34;,m,m+1);<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;if(a[m]&gt;x)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{ <BR>&nbsp;&nbsp; binary_search(n1,m-1);<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;binary_search(m+1,n2);<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>}<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>void main()<BR>{<BR>int i;<BR>for(i=0;i&lt;100;i++)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;a[i]=i;<BR>}<BR>binary_search(0,99);<BR>} <BR> 
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>