[VBA基础算法赛题] 组合

HYY514

<p><font size="3">小明买了9卷书，放在一个双层的书架中。<font color="#000000">上层放 第<font color="#d52b2b">6.7.2.9</font>卷，下层放 <font color="#cc3333">1.3.4.5.8</font>卷，</font></font></p><p><font color="#000000"><font size="3">他发现了一个有趣的问题，<font color="#000000">这样便得到一个分数<font color="#dd2222">6729</font>/<font color="#dd2222">13458</font>=1/2，<strong>正好用了这九个数字</strong>。</font></font></font><font color="#000000"><font color="#000000"><br/><font size="3">而且他发现这几卷书还可摆成其它很多个分子为4位，分母为5位的分数，可以让其结果等于1/2、1/3、1/4……1/52……1/66等等。</font></font></font></p><p><font size="3"><strong>问题</strong>：请用VBA求解出让分子结果可以为1的所有摆放组合？</font></p><p><font size="3">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 如：6729/13458=1/2</font></p><p><font size="3">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;5823/17469=1/3</font></p><p><font size="3">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ……</font></p><p><font size="3"><strong>尾注</strong>：<font color="#1a1ae6">1、请用回复可见跟贴。</font></font></p><p><font color="#1a1ae6" size="3">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2、无论常规穷举或者递归，代码在我本机运行时间在2秒内的，15金币奖励，</font></p><p><font color="#1a1ae6" size="3">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; 其余答案正确的酌情奖励。一星期后结贴并发布参考代码。</font></p><p><font size="3"><font color="#1a1ae6">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3、结果请用Debug.Print方法输出到立即窗口，结果按1/2…1/3…1/68…分母排序，格式如下</font>：</font></p><p><font size="3">6729/13458=1/2<br/>6792/13584=1/2<br/>6927/13854=1/2<br/>7269/14538=1/2<br/>7293/14586=1/2<br/>7329/14658=1/2<br/>7692/15384=1/2<br/>7923/15846=1/2<br/>7932/15864=1/2<br/>9267/18534=1/2<br/>9273/18546=1/2<br/>9327/18654=1/2<br/>5823/17469=1/3<br/>5832/17496=1/3<br/>3942/15768=1/4<br/>4392/17568=1/4<br/><br/>……</font></p><p><font size="3">……<br/>1432/75896=1/53<br/>1592/84376=1/53<br/>1746/92538=1/53<br/>1254/73986=1/59<br/>1283/79546=1/62<br/>1528/94736=1/62<br/>1269/83754=1/66<br/>1452/98736=1/68<br/>Count:187&nbsp;&nbsp;&nbsp;&nbsp; Time:1.826499999979</font></p><p>-------------------------------------------------------------------------------------------</p><p>把我的解法发上来，相互交流、学习。楼下已发的帖的可以继续完善自己的贴子。一星期结贴后总结发币币。</p><p>

游客，如果您要查看本帖隐藏内容请回复

[此贴子已经被作者于2010-8-5 20:11:39编辑过]

吕?布

游客，如果您要查看本帖隐藏内容请回复

HYY514

<p>我的代码是递归+穷举，吕布你的代码是递归+换位，代码非常快！非常好的思路，循环道数比我的少几倍，为什么不加进排序，符合题目要求。</p><p>用我当前的电脑，你的代码未有排序代码:</p><p>9523/76184=1/8<br/>9627/48135=1/5<br/>9723/48615=1/5<br/>9156/73248=1/8<br/>9158/73264=1/8<br/>9182/73456=1/8<br/>&nbsp;187 <br/>&nbsp;<font color="#ee1111">.829624999998487</font><br/>&nbsp;</p><p>我的代码已排序：</p><p>1243/65879=1/53<br/>1432/75896=1/53<br/>1592/84376=1/53<br/>1746/92538=1/53<br/>1254/73986=1/59<br/>1283/79546=1/62<br/>1528/94736=1/62<br/>1269/83754=1/66<br/>1452/98736=1/68<br/>Count:187&nbsp;&nbsp;&nbsp;&nbsp; Time:<font color="#ee1111">1.03274999999849</font></p><p>你的代码加进排序优化后时间还是少于我的</p>

[此贴子已经被作者于2010-8-4 21:37:46编辑过]

HYY514

按照你的思路，代码还可以优化，你的这种结构是我目前发现的全排位比较快的一种了

HYY514

<p>希望更多人参与进来!</p>

吕?布

<p>象这种字串换位，是对这题取巧了(1-9个数字，一位占一个)，如果用数组的话，会慢很多。</p><p>没排序是因为不知道怎么在中间排序，如果先记录在数组中再排序感觉不是可能出题的本意。还有实际上不太看得是按哪几项排序的(明确的是最后分母)</p>

cafkyy

<p>

游客，如果您要查看本帖隐藏内容请回复

</p><br/>

cafkyy

<p>为了赶进度，未进行优化，如果把分母的循环放在外面，就可以排序了。回复之前没注意还有排序。老师要扣分了。</p>[em03]

HYY514

<div class="msgheader">QUOTE:</div><div class="msgborder"><b>以下是引用<i>吕?布</i>在2010-8-5 8:20:00的发言：</b><br/><p>象这种字串换位，是对这题取巧了(1-9个数字，一位占一个)，如果用数组的话，会慢很多。</p><p>没排序是因为不知道怎么在中间排序，如果先记录在数组中再排序感觉不是可能出题的本意。还有实际上不太看得是按哪几项排序的(明确的是最后分母)</p></div><p>确实，如果是不同长度数据排位，你的代码要做较多改动，效率衰减也较快。但针对这道题你的代码没有问题。取巧并不是坏事，正因为有取巧意识才有创新思维。人们因为走路累，想偷懒才发明了汽车。 </p><p>仅按分母 1/2……1/68排序即可。静态存在的数据和动态数据的排序有本质的不同，怎样把排序思路融合到代码结构中提高效率是有很多技巧的，并没有偏离题意。</p>

HYY514

<div class="msgheader">QUOTE:</div><div class="msgborder"><b>以下是引用<i>cafkyy</i>在2010-8-5 9:09:00的发言：</b></div><p>[em17]代码很快，采用的不是全排列求解，但符合此题的条件，这是我意想不到的。这说明了单个人考虑问题容易产生定势。欢迎更多不同的思路。</p>