java – 找到一个整数n> 0,其中包含以下三个条件
起动器的一些定义:flip(n)是七段显示字体数字的180度旋转,所以一个2分之七的字体将被翻转到2. 0,1,2,5,8将被映射到自己. 6 – > 9,9→ 6和3,4,7没有定义.因此,任何包含3,7的数字都不会被忽略.更多示例:flip(112)= 211,flip(168)= 891,flip(3112)=未定义.
(顺便说一句,我确定翻转(1)应该是未定义的,但是作业说翻转(168)= 891,所以关于这个赋值翻转(1)被定义) 最初的挑战:找到整数n> 0,其中有以下三个条件: > flip(n)被定义,flip(n)= n 我们可以在下面找到的解决方案似乎是有效的,但至少没有找到答案.如果我正在使用1991(我搜索了一些可以解决问题的“基数”),我得到了一个很快的答案说1515151是一个.所以这个基本概念似乎是有效的,但不是在作业中给出的“基础”.我在这里遗漏了什么吗? 用伪代码编写的解决方案(我们在Small Basic中有一个实现,我在Java中创建了一个多线程): for (i = 1; i < Integer.MaxValue; i++) { n = i * 2011; f = flip(n,true); if (f != null && flip(n*n,false) != null) { print n + " is the number"; return; } } flip(n,symmetry) { l = n.length; l2 = (symmetry) ? ceil(l/2) : l; f = ""; for (i = 0; i < l2; i++) { s = n.substr(i,1); switch(s) { case 0,8: r = s; break; case 6: r = 9; break; case 9: r = 6; break; default: r = ""; } if (r == "") { print n + " is not flippable"; return -1; } elseif (symmetry && r != n.substr(l-i-1,1)) { print n + " is not flip(n)"; return -1; } f = r + f; } return (symmetry) ? n : f; } 解决方法
实际上(毫无疑问,最小化的实验,主要是直觉的),不太可能会在数学上优化搜索技术(例如采用建筑方法来构建一个不包含3,4的完美平方) 7并且是易于对称的,而不是优化计算,这不会以显着的量改变复杂性):
我将从一个满足2个标准的所有数字的列表开始(数字和翻转是相同的,即可以对称的,它是2011年的倍数),小于10 ^ 11:
有46个数字,根据2011年的定义和倍数,10 ^ 11以下,均可以对称.满足这种情况的2011年似乎是倍数将变得越来越少,因为随着数字的增加,统计学上的数字越少,将成为回文. 即对于任何给定的范围,说[1,10 ^ 11](如上),有46.对于相等宽度的相邻范围:[10 ^ 11 1,2 * 10 ^ 11],我们可能会猜到找到另外46或周围但是当我们继续使用10的较高功率的相同宽度的间隔时,数字的数量是相同的(因为我们分析相等的宽度间隔),尽管由于数字数增加,回文条件现在更多的数字.所以接近无限远,我们预计任何固定的回文数量都会接近0.或者,对于每个正值N,更准确地(但没有证据),概率为0,给定间隔(预定宽度)将具有多于N个倍数2011年是回文. 所以我们可以找到的回文数量将减少,因为穷举搜索继续.根据对于任何找到的回文的可能性,广场将是可以轻易的,我们假设回归平方的均匀分布(因为我们没有分析来告诉我们,否则没有理由相信),然后任何给定的方形的概率的数字长度将是可笑的是(7/10)^ d. 我们从我们发现的最小的这样的平方开始 192555261 ^ 2 = 37077528538778121 它已经是17位数字,给它约0.002(约1/430)的可能性被定义的可能性.但是当我们到达列表的最后一刻时, 98986298686 ^ 2 = 9798287327554005326596 它是24位数字长,并且具有小于被限定的1/5000的概率. 因此,随着搜索数量的增加,回文数量减少,任何找到的回文平方的可能性也可能下降 – 一个双刃刃. 剩下的是找到一些密度比例,因此看看寻找解决方案的可能性是如何的…虽然直观地看到,找到一个解决方案的概率不太可能(这绝对不排除那个甚至是一个大的解决方案的数量(可能是无限数量)). 祝你好运!我希望有人能解决这个问题.与许多问题一样,解决方案通常不像在更快的机器上运行算法或者具有更多的并行性或更长的时间段,或者使用更先进的技术或更有创造性的方法来攻击该问题,自己进一步的领域.答案,一个数字,比用于推导它的方法要少得多(通常). (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |