`
阿尔萨斯
  • 浏览: 4106806 次
社区版块
存档分类
最新评论

用php解决一个数学题【已有很多高手解决,期待更好的算法的出现】

 
阅读更多
http://www.phpchina.com/html/00/54500_itemid_29653.html

一个六位数,当分别用2,3,4,5,6乘它后,得到的五个乘积都是一个六位数,而且这得到的五个数是由原来六个数字组成,只是顺序改变了!
求高手帮助解决下!




---------------

貌似大家都默认了一个现象
http://bbs.phpchina.com/viewthread.php?tid=54377&page=5#pid394850

之前提出的一个假设 貌似大家做算法的时候都不考虑这种情况的存在可能 如果哪位有论证过这种假设不成立或者楼主的题目本身就默认不考虑这种假设 请大侠们说明一下

如果没有论证或者题目没有明确说明不考虑这种假设 算法设计再好也是不合题意的无效算法


------------------------



写了两种算法:
第一种思路是判断相乘的数的各个位之和是否相等,不过效率不太好。
第二种算法换了一种思路,用了字符反方向验证,因为正向会有一部分高位的不必要的运算。代码很简洁,效率很不错,附上代码:

第一种算法,判断各个位数之和:


===========================================================

第二种算法,字符反方向查询:



第一个算法在我的PE2140@2.66GHz上需要440ms,第二种只需要180ms。




---------------------------------



我之前提过这个问题了http://www.phpchina.com/bbs/thread-54377-2-1.html

解决的方法有一个:
得出每一位,逐个位排除.
如得两个位数相同,则两个同时删除或更改.
比如:
'123451'和'123456'
逐位删除或更改的话,剩下的一位就不等了.





----------------------------------



for($i = 100000;$i < 166667;$i++)//数的范围
{
....
for($ii=2;$ii<7;$ii++)// 2-6的倍数
{
.....
for($j=0;$j<6;$j++) //数的个数
{
if(strpos($i,substr($i*$ii,$j,1)) === false)//判断组成的数字 各个数字是否和原来的数一致
{
$a=false;
break;
}
}
}
}



-----------------------------



前面有人说过了
既然这6个数字组合后能出现被3整除的数 那这6个数字之和也必然能被3整除 所以这个数字本身也必须能被3整除 所以找一个能被3整除的数字做起点 每次递增3
显而易见 100000*6=600000 也就是 这个数字乘以6以后必然是大于600000的 最高位是6~9 那么这个原数中至少存在一个6~9之间的数字 否则这个6倍的数是由原数的6位数字组成并且仍为6位数就不可能成立了 那个正则正是保证原数中至少有一位是6~9的
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics