subject_37283.htm

一些关于vc的问答

<p>
序号：37283 发表者：骁霄笑 发表日期：2003-04-23 17:29:35
<br>主题：求教！
<br>内容：1。对夫妻跳舞，每人都有舞伴，但夫妻不许为舞伴。问有多少种配合方法？<BR>2。平面上有条直线，无三条直线共点，问此条直线可以把该平面分为多少块区域？
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：骁霄笑 回复日期：2003-04-23 19:47:52
<br>内容：更正一下：1。有对n夫妻 2。有n条直线
<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>回复者：afanty 回复日期：2003-04-24 13:29:35
<br>内容：1、数学归纳法：<BR>&nbsp;&nbsp; 当n=1时，f(n)=0<BR>&nbsp;&nbsp; 当n=2时，f(n)=1<BR>&nbsp;&nbsp; 当n=3时，f(n)=2<BR>&nbsp;&nbsp; ...<BR>&nbsp;&nbsp; 对于任何一种合理的n-1对舞伴组合，增加一对夫妻时，将夫妻中的一人与任一对<BR>&nbsp;&nbsp; 舞伴中同性别的人进行置换都可以产生一种合理的n对舞伴组合，所以:<BR>&nbsp;&nbsp; f(n)=(n-1)f(n-1)；<BR><BR>&nbsp;&nbsp; 由此可用递归算法如下：<BR><BR>&nbsp;&nbsp; int f(int n)<BR>&nbsp;&nbsp; {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(n==1)return 0;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(n==2)return 1;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (n-1)*f(n-1);<BR>&nbsp;&nbsp; }<BR><BR>2、无确定解，因为题目没有给出直线能否平行<BR>&nbsp;&nbsp; 若无三条直线共点，也无两条直线平行，数学归纳法：<BR>&nbsp;&nbsp; 当n=1时，f(n)=2<BR>&nbsp;&nbsp; 当n=2时，f(n)=4<BR>&nbsp;&nbsp; 当n=3时，f(n)=7<BR>&nbsp;&nbsp; ...<BR>&nbsp;&nbsp; 当平面上已有n-1条直线时，增加一条直线，这条直线必然与n-1条直线都相交<BR>&nbsp;&nbsp; 与n-1个不同的交点，这条直线被n-1个交点分割成了n条线段，这n条线段必然<BR>&nbsp;&nbsp; 将其所在的区域一分为二，所以会新增n个区域，所以：<BR>&nbsp;&nbsp; f(n)=f(n+1)+n<BR><BR>&nbsp;&nbsp; 由此可用递归算法如下：<BR><BR>&nbsp;&nbsp; int f(int n)<BR>&nbsp;&nbsp; {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(n=1)return 2;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return f(n-1)+n;<BR>&nbsp;&nbsp; }
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：骁霄笑 回复日期：2003-04-25 10:55:00
<br>内容：多谢解答！这两道题是我们学校计算机系科技文化节的题目，对于第2题，如果考虑有直线平行的情况，不能给出解吗？原题就是这样的。<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>
回复者：afanty 回复日期：2003-04-25 12:22:52
<br>内容：如果有直线平行，不是无解，而是有很多种可能解，并且解的个数与平行直<BR>线的条数有关，而且两对平行线与三条直线相互平行的情况也不同，这样分<BR>析起来过于复杂，所以俺判断是出题人的疏忽。<BR><BR>递归算法本身并不复杂，就是一个函数反复调用自身，直到找到出口。<BR>递归算法往往要依赖数学归纳法，数学归纳法在高中数学里有详细介绍，难<BR>点在于找到f(n)与f(n+1)之间的关系，这个就要依靠个人分析问题、总结规<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>
回复者：骁霄笑 回复日期：2003-04-25 13:11:43
<br>内容：听君一席话，胜读十年书！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>