以项目欧拉＃36更好的解决方案？ [英] Better Solution to Project Euler #36?

问题描述

项目欧拉问题36 规定：

十进制数，585 = 1001001001（二进制），是回文在这两个基地。

The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.

查找所有号码的总和，不到一百万，这是回文在基地10和基地2个。

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

（请注意，回文数，在任一的基础上，可以不包括前导零。）

(Please note that the palindromic number, in either base, may not include leading zeros.)

已经有以这样的解决方案堆栈溢出，但我想要一个的更有效的解决方案。

例如，由于回文不能有前导0，无连号需要进行检查，只有奇数为其二进制的最后一位是1。这个简单的观察已经加快了蛮力检查每一个数字范围由2倍。

For example, since the palindrome cannot have leading 0's, no even numbers need to be checked, only odd numbers for which the last bit in binary is a 1. This simple observation already speeds up the brute force "check every number in the range" by a factor of 2.

不过，我想比这更聪明。理想的情况下，我想的算法与运行时间成比例的总和号的数目。我不认为这是可以做的更好。但也许那是不可能的。我们能不能​​例如，生成所有回文小数不足一万元的时间比例为十进制数，满足该属性的数量？ （我想答案是肯定的）。

But I would like to be more clever than that. Ideally, I would like an algorithm with running time proportional to the number of numbers in the sum. I don't think it's possible to do better than that. But maybe that is not possible. Could we for example, generate all palindromic decimal numbers less than one million in time proportional to the number of decimal numbers satisfying that property? (I think the answer is yes).

什么是最有效的算法来解决这个回文和问题我要考虑的运行时间参数被N：号码的范围的大小（在这种情况下，1元）， D：在的范围内的集合小数回文，以及B：该组中的范围二进制回文。我希望有一个运行时间为O（n）+ O（| D相交B |），或做不到这一点，O（分（| D |，| B |））

What is the most efficient algorithm to solve this palindrome sum problem? I would like to consider run-times parameterized by N: the size of the range of numbers (in this case 1 million), D: the set of decimal palindromes in the range, and B: the set of binary palindromes in the range. I hope for a run-time that is o(N) + O( |D intersect B| ), or failing that, O(min(|D|, |B|))

注意： 二进制和的小数的回文是公知的。

Note: The sequences of binary and decimal palindromes are well known.

例如。二进制回文＆LT; 100：0，1，3，5，7，9，15，17，21，27，31，33，45，51，63，65，73，85，93，99

e.g. binary palindromes < 100: 0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 85, 93, 99

。 。 .decimal回文＆LT; 100：0，1，2，3，4，5，6，7，8，9，11，22，33，44，55，66，77，88，99，

. . .decimal palindromes < 100:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99,

回文在两个基地：0，1，3，5，7，9，33，99

palindromes in both bases: 0, 1, 3, 5, 7, 9, 33, 99

33和99的二进制重新presentations是 10001 和 1100011 分别。 接下来的数字是在这两个回文是 585 = 1001001001 。

The binary representations of 33 and 99 are 10001 and 1100011 respectively. The next number which is a palindrome in both is 585 = 1001001001.

推荐答案

在基地的长度 B 回文数2 * K 是（B-1）* B ^（K-1），因为是长的回文数 2 * K -1 。因此，在回文任何基本不超过 N 的数量为O（开方（N））¹。所以，如果你生成所有回文在一个基地（不超过 N ），并检查它们是否也在其他基础回文，你有一个O（开方（N）*日志（N））的算法（日志因子来自回文检查）。这是O（N），但我不知道，但如果它也是O（| D相交B |）。

The number of palindromes in base b of length 2*k is (b-1)*b^(k-1), as is the number of palindromes of length 2*k-1. So the number of palindromes not exceeding N in any base is O(sqrt(N))¹. So if you generate all palindromes (not exceeding N) in one base and check if they are also palindromes in the other base, you have an O(sqrt(N)*log(N)) algorithm (the log factor comes from the palindrome check). That's o(N), but I don't know yet if it's also O(|D intersect B|).

这不是O（| D相交B |）:(只有32号至10 ¹⁰ 这是回文在这两个基地我没有看到任何模式，将只允许兴建。那些。

It's not O(|D intersect B|) :( There are only 32 numbers up to 10¹⁰ which are palindromic in both bases. I don't see any pattern that would allow constructing only those.

¹如果 N 的 D 数字（在基地 B ），回文不超过 N 的数量至多为 D-1 数字回文数之间并具有最 D 位（包括限制含）回文数。有（B-1）* B ^（K-1）具有完全数字氏/ code>数字（在基地 B ），其中（B-1）* B ^（楼（（K-1）/ 2）））是回文。求和给基地的数量 - B 回文至多 K 位为任 2 * （二^（K / 2）-1）（如 K 为偶数）或者（B-1）* b ^（（K-1）/ 2）+ 2 *（B ^（（K-1）/ 2）-1）（如 K 是奇数）。因此，给予或采取的系数2 * B ，回文数与在大多数D位是 B ^（D / 2）。因此回文不超过 N 的数量大约是 N R个0.5 ，由底座的倍数界的一个因素考虑的。

¹ If N has d digits (in base b), the number of palindromes not exceeding N is between the number of palindromes having at most d-1 digits and the number of palindromes having at most d digits (both limits inclusive). There are (b-1)*b^(k-1) numbers having exactly k digits (in base b), of which (b-1)*b^(floor((k-1)/2))) are palindromes. Summing gives the number of base-b palindromes with at most k digits as either 2*(b^(k/2)-1) (if k is even) or (b-1)*b^((k-1)/2) + 2*(b^((k-1)/2)-1) (if k is odd). Hence, give or take a factor of 2*b, the number of palindromes with at most d digits is b^(d/2). Thus the number of palindromes not exceeding N is roughly N^0.5, with a factor bounded by a multiple of the base considered.

这篇关于以项目欧拉＃36更好的解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！