subject_21369.htm

一些关于vc的问答

<p>
序号：21369 发表者：Zerg 发表日期：2002-11-16 16:40:24
<br>主题：“仅有10％的专业程序员能把这个小程序写的完全正确”
<br>内容：《程序设计语言5：概念和机构》&nbsp;&nbsp;裘宗燕 译<BR><BR>书中的一段原话：<BR>例3.4&nbsp;&nbsp; Bently【1986】要求超过100个专业程序员把下面这段有关二分法的简要描述“写成一个程序，语言由他们自己选择.............<BR>他报告说，“我感到非常惊讶，给了他们充足的时间，仅有10％的专业程序员能把这个小程序写的完全正确”。<BR><BR>我们要确定在一个已经排好序的数组X[1...N]中是否包含元素T。二分法解决问题的方法是维持数组中可能包含T的区域的踪迹（如果元素T确实在数组中的某处）。在开始的区域就是整个数组，通过将元素T与数组的中间元素比较可以缩小范围，丢掉数组的一半。这个过程一直继续T被找到，或者是T可能存在的范围变空。<BR><BR>Berntley提出了如下建议：“绝大多数程序员都认为，只要手头上有了上面这段有<BR>关二分法的描述，写出代码是一件很容易得事。然而他们错了。如果你现在就把这篇文章放在一边，亲自动手写代码试一试。你就会相信这一点。”<BR><BR><BR>我是初学者在“亲自动手写代码试一试”之后我深深的“相信这一点”<BR>在《C++ Primer》中找到一个二分查找的函数：<BR>但我就得它不“完全正确”。<BR>非完全二分查找，有没有高手帮我写一个。。<BR>谢了！！！！！！！！！！<BR><BR><BR><BR>#include&lt;iostream&gt;<BR>#include&lt;vector&gt;<BR><BR>using namespace std;<BR><BR>int Numsear(vector&lt;int&gt;vec ,int val);<BR>const int notfound = -1;<BR>int main(int argc, char *argv[])<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;vector&lt;int&gt;num(10000);<BR>&nbsp;&nbsp;&nbsp;&nbsp;int value;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int size;<BR> <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;"Enter to size:&nbsp;&nbsp;&nbsp;&nbsp;"&lt;&lt;endl;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&gt;&gt;size;<BR>&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;"Enter to value:&nbsp;&nbsp;"&lt;&lt;endl;<BR>&nbsp;&nbsp;&nbsp;&nbsp;cin&gt;&gt;value;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int n=0; n&lt;size; ++n)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[n] = n;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//cout&lt;&lt;num[n]&lt;&lt;endl;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if( Numsear(num,value) &lt; 0 )<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;"The number notfound!"&lt;&lt;endl;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cout&lt;&lt;"The number found!"&lt;&lt;endl;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cout&lt;&lt;Numsear(num,value)&lt;&lt;endl;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;return 0;<BR>}<BR>////////////////////////////////////////////////////<BR>int Numsear(vector&lt;int&gt;vec,int val)<BR>{<BR><BR>int low =0;<BR>int high = vec.size() - 1;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while( low &lt;= high )<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int mid = ( low + high ) /2;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if( val == vec[mid] )<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return mid;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if( val &lt; vec[mid] )<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; high = mid -1;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low = mid + 1;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;return notfound;<BR>}<BR><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>
回复者：atang 回复日期：2002-11-18 05:59:36
<br>内容：VC里面没有vector.h,没法编译啊
<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>回复者：管理员 回复日期：2002-11-22 19:33:54
<br>内容：看到这么长的程序，不能不说是C＋＋和STL的悲哀。<BR>如果用C就不会这么长的代码。<BR><BR>回到正题，你在取中间值时记得比较一下结果<BR>int mid = ( low + high ) /2;<BR>并不表明数组中的 上一个，或下一个数就是 mid-1,mid+1<BR>争取除以2并不一定是整数。<BR><BR>还有，我不相信只有10％的人能对。<BR>最后，就算只有10％对也没有关系，因为开发包括：Coding and Debug。<BR><BR>完了。<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：Tuu Puu 回复日期：2002-11-22 21:02:32
<br>内容：关于代码长度我开始也跟楼上的admin一个观点，后来仔细看了一下其中好些是算法无关的，它的那个代码也不算太长，觉得说这个有点无聊
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>