如何有效地计算第n的n位回文？ [英] How to calculate nth n-digit palindrome efficiently?
问题描述
我觉得这个问题很简单，以understand.For更清楚我给的例子：
I think the question is simple enough to understand.For more clarity I'm giving example :
在2位数字回文名单，第七届回文是77（第一是11，第二个是22等）。
显然存在蛮力解决方案，但它的效率不高。
Obviously a brute force solution exists but it's not efficient.
任何人都可以提出我一些更好的解决方案来解决这个问题？
Can anyone suggest me some better solution to solve the problem ?
推荐答案
首先，我们可以简化这个问题，因为我们只需要看看第一个数字的一半（四舍五入，如果有数字为奇数）。我会打电话给第一组数字的显著数字，然后剩下的非显著数字
First, we can simplify the problem because we only need to look at the first half of the digits (rounding up if there are an odd number of digits). I will call the first set of digits significant digits and the rest non-significant digits.
这是因为在非显著数字必须符合显著数字（反向）。这是不可能的，以具有相同的领先显著数字和不同的非显著位数另一个回文号码。在显著数字确定整个回文数。
This is because the non-significant digits must match the significant digits (in reverse). It is not possible to have another palindrome number with the same leading significant digits and different non-significant digits. The significant digits determine the entire palindrome number.
现在，我们只需要拿出一个算法生成的第n个有效的显著数字。这会更容易些，如果我们允许前导零，所以我们会拿出算法，允许前导零，那么调整的算法。
Now, we just need to come up with an algorithm to generate the nth valid significant digits. This would be easier if we allowed for leading zeros, so we'll come up with the algorithm that allows for leading zeros, then tweak the algorithm.
最初的几个回文（显著位）将是：
The first few palindromes (significant digits) would be:
- 1：0000
- 2：0001
- 3：0002
- ...
- 100：0099
因此，我们可以通过找到十进制再$ P $的psentation找到的第n个编号的显著数字（N-1）。
So we can find the significant digits of the nth number by finding the decimal representation of (n-1).
要调整算法时，不允许前导零的工作，我们将开始与一个为龙头的数字：
To tweak the algorithm to work when not allowing leading zeros, we would start with a one as the leading digit:
- 1：1000
- 2：1001
- 3：1002
- ...
- 100：1099
这可以归结为寻找小数重$ P $的（N-1）+ 1000 = N + 999 psentation，扩大成一个完整的回文
This boils down to finding the decimal representation of (n-1) + 1000 = n + 999 and expanding into a full palindrome:
示例：查找长度9的113回文
Example: Find the 113th palindrome of length 9.
- 确定的位数来看看：向上舍（9/2）= 5 - >只看前5位 。
- 查找号码添加摆脱的前导零：10 ^（5-1）= 10000
- 使用公式：（113 - 1）+ 10000 = 10112
- 扩展入回文：101121101
- Determine number of digits to look at: Round up(9 / 2) = 5 --> only look at first 5 digits.
- Find number to add to get rid of leading zeros: 10^(5-1) = 10000
- Use formula: (113 - 1) + 10000 = 10112
- Expanded into palindrome: 101121101
在一个侧面说明，这种算法也可以推广到寻找符号（或字母）的任何一组有序的第n个回文。
On a side note, this algorithm could also be generalized to finding the nth palindrome of any ordered set of symbols (or alphabet).
通用算法
由于：寻找回文数的 N 的，回文拥有的 M 的是数字符号，有 P 的符号（十进制10个符号）
Given: finding palindrome number n , palindrome has m symbols as digits , there are p symbols (10 symbols in decimal)
- 我们的问： =上限（ M 的/ 2）
- 在我们的偏移的= P ^（问：的 - 1）
- 在我们的号的=（的 N 的 - 1）+ 偏移的
- 在我们的的答案的是号的展开为回文
- Let q = ceiling(m / 2)
- Let offset = p ^ (q - 1)
- Let number = (n - 1) + offset
- Let answer be number expanded as a palindrome
这篇关于如何有效地计算第n的n位回文？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
