电源列表的最后一位数字 [英] Last digit of power list
问题描述
问题大纲：
请注意我会滥用 ^ 并将其用作幂符号，尽管插入符号是JS中的按位XOR运算符。
Please note I will abuse the life out of ^ and use it as a power symbol, despite the caret symbol being the bitwise XOR operator in JS.
获取正整数列表，
[ x_0, x_1, ..., x_n ]
并找到等式的最后一位数
and find the last digit of the equation given by
x_0 ^ ( x_1 ^ (... ^ x_n ) ... )
我将调用此函数 LD （...）用于此问题的其余部分。
I'll call this function LD(...) for the rest of this question.
示例：对于整数列表 a = [ 2,2,2,2 并且鉴于 2 ^（2 ^（2 ^ 2））= 65536 ，很容易看到 LD（a）= 6 。
Example: For a list of integers a = [2, 2, 2, 2] and given that 2 ^ (2 ^ (2 ^ 2)) = 65536, it's easy to see that LD(a) = 6.
注意 0 ^ 0 === 1 对于这个问题，与 x ^ 0 === 1 一致，但与 0 ^ x === 0不一致。
Note that 0 ^ 0 === 1 for this question, consistent with x ^ 0 === 1, but not with 0 ^ x === 0.
到目前为止我取得的成就
它很容易得出结论 x ^ 0 === 1 ，无论如何。
It's easy to conclude that x ^ 0 === 1, no matter what.
这也很容易得出结论，如果你做了一些测试用例，那么权力的最后数字会循环：
It's also pretty easy to conclude that last digits of powers "loop" around if you do a few test cases:
LD(2 ^ 1) = 2,
LD(2 ^ 2) = 4,
LD(2 ^ 3) = 8,
LD(2 ^ 4) = 6,
LD(2 ^ 5) = 2, // Notice we've looped from hereon
LD(2 ^ 6) = 4,
LD(2 ^ 7) = 8,
...
因此，如果我们知道特定基数的循环中的数字的数量（上面的例子为4）基数2），我们可以使用该计数的模数计算出最后一位数。
So if we know the count of numbers that are in the loop for a particular base (4 for the above example of the base 2), we can use the modulus of that count to work out the last digit.
例如， LD（2 ^ 55）== = LD（2 ^（55％4））=== LD（2 ^ 3）
所以有了一些数学，我们可以为每个最后一个数字获得一个很好的数组数组，其中数组数组的索引是基数，每个数组的索引是循环长度的模数：
And so with a bit of maths, we can get ourselves a nice array-of-arrays for each last digit, where the index of the array-of-arrays is the base and the index of each array is the modulus of the loop length:
const p = [
[ 0 ], // 0^1=0, 0^2=0 ...
[ 1 ], // 1^1=1, 1^2=1 ...
[ 2,4,8,6 ] // 2^1=2, 2^2=4 ...
[ 3,9,7,1 ] // 3^1=3, 3^2=9 ...
[ 4,6 ]
[ 5 ]
[ 6 ]
[ 7,9,3,1 ]
[ 8,4,2,6 ]
[ 9,1 ]
];
使用示例： LD（3 ^ 7）=== p [ 3] [7-1％4] - 请注意，我们必须从指数中减去一，因为每个数组都是从0开始的。
Example of usage: LD(3^7) === p[3][7-1 % 4] - note that we have to subtract one from the exponent as each array is 0-based.
所以我们到达了JavaScript：
So we arrive at the JavaScript:
LD(Math.pow(a,b)) === p[a % 10][(b-1) % p[a % 10].length]
a％10 应该是显而易见的，它只需要基数的最后一位作为我们的数组数组中的索引，因为任何非单位都不会影响最后一位数。
The a % 10 should be obvious, it takes just the last digit of the base number as the index in our array-of-arrays, as any non-units do not affect the last digit.
对于像问题开头的 [1,2,3] 这样的清单，可以这样做递归。我们的初始值为1，如果是空列表，则为 x ^ 1 === x ，我们将列表反转以利用<$的累积c $ c> .reduce（）方法：
For a list like [1,2,3] from the beginning of the question, this can be made recursive. We have an initial value of 1, in case of empty lists, as x^1 === x, and we reverse the list to make use of accumulation of the .reduce() method:
[1,2,3].reduceRight( (a,v) =>
p[v % 10][(a-1) % p[v % 10].length], 1)
以下内容如下所示，如下所示：
Following through so that makes sense would look like the following:
- 首先，
a = 1（初始值），v = 3;然后p [3％10] === p [3] === [3,9,7,1]，因此[3 ，9,7,1] [（1-1）％[3,9,7,1] .length] === [3,9,7,1] [0％4] === 3。 - 然后，
a = 3（最后一次迭代），v = 2;所以p [2] === [2,4,8,6]，所以[2,4,8,6] [2 ％4] === 8。 - 最后，
a = 8，v = 1;p [1] === [1]，[1] [8％1] === 1。
- First up,
a = 1 (initial value), v = 3; thenp[3 % 10] === p[3] === [ 3,9,7,1 ], and thus[ 3,9,7,1 ][ (1-1) % [ 3,9,7,1 ].length] === [ 3,9,7,1 ][ 0 % 4 ] === 3. - Then,
a = 3 (last iteration), v = 2; sop[2] === [ 2,4,8,6 ], and so[ 2,4,8,6 ][ 2 % 4 ] === 8. - Finally,
a = 8, v = 1;p[1] === [ 1 ], and[ 1 ][ 8 % 1 ] === 1.
所以，我们得到 LD（[1,2,3]）=== 1 ，这不难验证： 1 ^（2 ^ 3）=== 1 ^ 8 === 1 。
So, we get LD([1, 2, 3 ]) === 1, which isn't hard to verify: 1 ^ (2 ^ 3) === 1 ^ 8 === 1.
问题：
这有效，所以只要指数不超过10并且之后没有另一次迭代。但是，如果有事情出错。让我解释一下：
This works, so long as the exponent is not over 10 and there isn't another iteration after that. However, if there is things go awry. Let me explain:
假设我们有数组， a = [2,2,2,2] 。由于 1 是我们的初始值，因此该列表最初为 a = [1,2,2,2,2] 。使用上面的减少：
Say we have the array, a = [ 2,2,2,2 ]. As 1 is our initial value, the list is initially a = [ 1,2,2,2,2 ]. Using the reduction above:
- 第一次迭代
a = 1，v = 2（记住我们的.reduce有1，因为它是初始值）：
-
p [2％10] [（1-1）％p [2％10] .length] -
= [2,4,8,6] [0％4] -
= 2 - 通过
2 ^ 1 = 2轻松验证，我们的列表是现在[2,2,2,2]
- First iteration
a = 1, v = 2(remembering that our.reducehas1as it's initial value):p[2 % 10][(1-1) % p[2 % 10].length]= [ 2,4,8,6 ][0 % 4]= 2- Easily verified by
2 ^ 1 = 2, our list is now [ 2,2,2,2 ]
-
p [2％10] [（2-1）％p [2％10]。长度] -
= [2,4,8,6] [1％4] -
= 4 - 通过
2 ^ 2轻松验证= 4，我们的列表现在是[4,2,2]
p[2 % 10][(2-1) % p[2 % 10].length]= [ 2,4,8,6 ][1 % 4]= 4- Easily verified by
2 ^ 2 = 4, our list is now [ 4,2,2 ]
-
p [2％10 ] [（4-1）％p [2％10] .length] -
= [2,4,8,6 ] [3％4] -
= 6 - 的Eas通过
2 ^ 4 = 16验证，我们的列表现在是[16,2]
p[2 % 10][(4-1) % p[2 % 10].length]= [ 2,4,8,6 ][3 % 4]= 6- Easily verified by
2 ^ 4 = 16, our list is now [ 16,2 ]
-
p [2％10 ] [（6-1）％p [2％10] .length] -
= [2,4,8,6 ] [5％4] -
= 4 -
2 ^ 16 = 65536轻易反驳。
p[2 % 10][(6-1) % p[2 % 10].length]= [ 2,4,8,6 ][5 % 4]= 4- Easily disproved by
2 ^ 16 = 65536.
如果你研究了一段时间，它就变得很明显了。最后一次迭代的第三步，
And if you study that for a while it becomes obvious why. The third step in the final iteration,
= [ 2,4,8,6 ][5 % 4] = p[ 2,4,8,6 ][1]应该是
= [ 2,4,8,6 ][15 % 4] = p[ 2,4,8,6 ][3]因此给出的结果不正确。
Therefore giving an incorrect result.
问题：
是否有一种方法可以捕获仅由前一个指数创建的偏移量传递上一次迭代的最后一位数字？我能以某种方式在最后一次迭代中以另一条信息传递
6，以便模数正确吗？Is there a way, based on the previous exponent, to capture that "offset" created by only passing on the last digit of the previous iteration? Can I somehow pass on the
6in that last iteration with another piece of information so that the modulus is correct?所以而不是仅仅返回
p[v % 10][(a-1) % p[v % 10].length)也许它可以返回
[ p[v % 10][fn(a[0], a[1]) % p[v % 10].length], **some other clever information here to use in the calculation to make the modulus correct** ]其中
fn（a [0]，a [1]）使用之前的累计值以及一些其他信息来计算正确的mod值。这不一定是数组，可能是@aec在评论中指出的对象或元组。where
fn(a[0], a[1])uses both the accumulated value from before, as well as some other information to calculate the correct mod value. This doesn't necessarily have to be an array, maybe an object or tuple as @aec pointed out in the comments.一个（可怕的）解决方案是跟踪在累加器中的前一次迭代（例如，对于最后一步，而不是返回
6，我可以返回16并将其用于下一次迭代，这将给出正确的索引）。但是，如果数字非常大，这是非常不切实际的！假设上一步的数字4142和623，计算4142 ^是不切实际的623然后传递它。One (terrible) solution would be to keep track of the previous iteration in the accumulator (e.g., for that last step, instead of returning
6, I could return16and use that for the next iteration, which would give the correct index). However, it's very impractical if the numbers were very large! Say the previous step had the numbers4142and623, it's not practical to calculate4142^623and pass that on.请注意我知道还有其他解决方案，但我很好奇我是否可以更改此代码在我编写的单个
.reduce语句中解决了这个问题。因此可以通过修改来解决这个问题：Please note that I understand there are other solutions to this, but I am curious if I can change this code to solve this problem in the single
.reducestatement I've written. So is it possible to solve this problem by modifying:array.reduceRight( (a,v) => p[v % 10][(a-1) % p[v % 10].length], 1)尽管讨论过累加器问题？它几乎可以工作，而且我认为我离它工作有一招！
despite the discussed accumulator problem? It nearly works, and I think I'm one trick away from it working!
请注意括号！列表
[3,14,16]相当于3 ^（14 ^ 16）！==（3 ^ 14）^ 16要检查的一些测试，可以验证函数调用
LU（数组），其中array是数字数组：A few tests to check against, which can be verified for function call
LU(array), wherearrayis the array of numbers:// Current attempt const p = [ [ 0 ], // 0^1=0, 0^2=0 ... [ 1 ], // 1^1=1, 1^2=1 ... [ 2,4,8,6 ], // 2^1=2, 2^2=4 ... [ 3,9,7,1 ], // 3^1=3, 3^2=9 ... [ 4,6 ], [ 5 ], [ 6 ], [ 7,9,3,1 ], [ 8,4,2,6 ], [ 9,1 ] ]; // CURRENT ATTEMPT let LU = array => array.reduceRight( (a,v) => a === 0 ? 1 : p[v % 10][(a-1) % p[v % 10].length] , 1); let LUTest = (array, expected) => console.log( (LU(array) === expected ? "Success" : "Failed"), "for", array, "got", LU(array), "expected", expected); LUTest([ 2, 2, 2 ], 6) LUTest([ 2, 2, 2, 2 ], 6) LUTest([ 3, 4, 5 ], 1) LUTest([ 6, 8, 10 ], 6) LUTest([ 2, 2, 0 ], 2) LUTest([ 12, 30, 21 ], 6) LUTest([ 0, 0 ], 1) // x^0 === 1 LUTest([ 0 ], 0)在这里测试： http://www.wolframalpha.com/widgets/view.jsp?id=56c82ccd658e09e829f16bb99457bcbc
感谢您的阅读！
其他想法：
有一个小突破！因此，对于作为指数基数的任何整数（即
xx 中的x），LD（x）=== LD（x％10）。这是因为经过第一个（从右到左）的数字不会影响指数结果的单位数（例如，LD（23 ^ 7）=== LD（3 ^ 7））Had a mini-breakthrough! So for any integer that is a base of an exponent (i.e., the
xinx^y),LD(x) === LD(x % 10). This is because the digits past the first (right-to-left) do not affect the unit digit of the exponent result (e.g.,LD(23 ^ 7) === LD(3 ^ 7))此外，如
const p = [...，数组 - 包含单位值循环的数组，所有数字都有一个长度为最小公倍数为4的循环。即，所有循环都是1,2或4个数字（例如，p [3] ] === [3,9,7,1]单位数组的长度为4）。Also, as in
const p = [ ..., the array-of-arrays containing the cycles of unit values, all numbers have cycles of a length with a lowest common multiple of 4. i.e., all cycles are either 1, 2 or 4 numbers (e.g., thep[3] === [ 3,9,7,1 ]unit array has length four).因此，我们可以得出结论
LD（（x％10）^（y％4））=== LD（x ^ y）。So, we can conclude
LD((x % 10) ^ (y % 4)) === LD(x ^ y).但是请注意，如果数字是4的倍数，则它变为零。我们大多数时候都不想要这个！您不希望
20在指数端变为0- 我们希望<$ c $的范围c> x 为1到10，y为1到4：Note however if a number is a multiple of 4, it becomes zero. We don't want this most of the time! You don't want
20to becomes0on the exponent side either - we want the range forxto be 1 through 10, and for y to be 1 through 4:所以，
LD（ （x％10 || 10）^（y％4 || 4））=== LD（x ^ y）。我们可以处理特殊情况So,
LD((x % 10 || 10) ^ (y % 4 || 4)) === LD(x ^ y). We can handle the special cases withif (x === 0) { return 0 // 0^anything = 0, including 0^0 for argument's sake. } else if (y === 0) { return 1 // anything ^ 0 = 1, excluding 0^0 } else { ... }这很有意思！这意味着现在计算
LD（x ^ y）是合理的，但我不知道如何处理这些信息。This is very interesting! It means it is now reasonable to calculate
LD(x ^ y), but I'm not sure what to do with this information.推荐答案
最后！在做了一些挖掘之后我意识到我可以修改最初的想法并得到我想要的答案：
Finally! after doing some digging about I realized I can modify the initial idea and get the answer I wanted:
let LD = (as) => as.reduceRight((acc, val) => Math.pow(val < 20 ? val : (val % 20 + 20), acc < 4 ? acc : (acc % 4 + 4)) , 1) % 10测试：
let LD = (as) => as.reduceRight((acc, val) => Math.pow(val < 20 ? val : (val % 20 + 20), acc < 4 ? acc : (acc % 4 + 4)) , 1) % 10 let LDTest = (array, expected) => console.log((LD(array) === expected ? "Success" : "Failed"), "for", array, "got", LD(array), "expected", expected); LDTest([ 2, 2, 2 ], 6) LDTest([ 2, 2, 2, 2 ], 6) LDTest([ 3, 4, 5 ], 1) LDTest([ 6, 8, 10 ], 6) LDTest([ 2, 2, 0 ], 2) LDTest([ 12, 30, 21 ], 6) LDTest([ 0, 0 ], 1) // x^0 === 1 LDTest([ 0 ], 0)为什么
modulo 20？因为在[2,2,2,2]的情况下，模数10会失去精度，当我们从问题示例到达最后一步时：So why
modulo 20? Because a modulus of 10 loses precision in the cases such as[ 2,2,2,2 ], when we hit the last step as from the question example:
第四次迭代，问题变得明显。
a = 6，v = 2：p [2％10] [（ 6-1）％p [2％10] .length]= [2,4,8， 6] [5％4]= 42 ^ 16 = 65536轻易反驳。通过简单地允许多达20的倍数，我们为每个数组计数提供LCM（最低公倍数），以及
p的长度，即10。（LCM（[1,2,4,10]）=== 20）。By simply allowing a multiple up to 20, we have the LCM (lowest common multiple) for each count of the array, as well as for the length of
p, which is 10. (LCM([ 1,2,4,10 ]) === 20).然而，由于指数现在从未高于
40 ^ 8（约6万亿），因为它在下一次迭代中被取为4的模数，我们可以简单地进行指数并且每次都返回答案。However, as the exponential is now never higher than
40^8(approximately 6 trillion), and as it is taken to the modulo of 4 in the next iteration, we can simply do the exponential and return the answer each time.当然要在最后的情况下得到数字，我们需要取10的模数才能返回最后一位数。
Of course to get the digit in the final case, we need to take modulo of 10 to just return that last digit.
我还有一些东西我不明白这里。
我们允许模数值下的任何值用三元运算符保留其值。例如，对于指数，
prev< 4？上一篇:(上一页％4 + 4）。不过我最初认为这是prev === 0？ 0 :(上一页％4 + 4）。We allow any value under the modulo value to retain its value with the ternary operators. E.g., for the exponent,
prev < 4 ? prev : (prev % 4 + 4). However I initially believed this to beprev === 0 ? 0 : (prev % 4 + 4).这是因为指数为零的结果数与模数的其他倍数不同，它总是等于1（
x ^ 0 === 1）。因此，通过添加4，我们得到一个具有相同最后一位数的值，并且通过单独保留零，我们仍然得到1为零指数。This is because th exponent of zero does not have the same ending digit as the other multiples of the modulo, it always equals 1 (
x ^ 0 === 1). So, by adding 4, we get a value that does have the same last digit, and by leaving zero alone we still get 1 for zero exponents.为什么
prev< 4？上一篇:(上一页％4 + 4）需要这个答案是否正确？为什么例如prev = 3，需要3而不是像其他人一样添加4？Why is it that
prev < 4 ? prev : (prev % 4 + 4)was required to make this answer correct? Why is e.g.,prev = 3, need to be3instead of adding 4 like the others?这篇关于电源列表的最后一位数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
-
