问题概述：
请注意，我将滥用^的生命并将其用作幂符号，尽管插入符号是 JS 中的按位 XOR 运算符。
取一个正整数列表，
[ x_0, x_1, ..., x_n ]
并找到公式的最后一位数字
x_0 ^ ( x_1 ^ (... ^ x_n ) ... )
我将在这个问题的其余部分调用此函数LD(...)。
示例：对于a = [2, 2, 2, 2]的整数列表，并给定该2 ^ (2 ^ (2 ^ 2)) = 65536，很容易看到该LD(a) = 6。
请注意，这个问题0 ^ 0 === 1，与x ^ 0 === 1一致，但与0 ^ x === 0不一致。
到目前为止我取得了什么成就
很容易得出结论，无论如何，x ^ 0 === 1。
如果你做一些测试用例，也很容易得出结论，最后一位数字的幂"循环"：
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,
...
因此，如果我们知道特定基数循环中的数字计数(上面以 2 为底数的示例为 4)，我们可以使用该计数的模数来计算出最后一个数字。
例如，LD(2 ^ 55) === LD(2 ^ (55 % 4)) === LD(2 ^ 3)
因此，通过一些数学运算，我们可以为每个最后的数字得到一个漂亮的数组数组，其中数组数组的索引是基数，每个数组的索引是循环长度的模数：
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 开始的。
所以我们到了 JavaScript：
LD(Math.pow(a,b)) === p[a % 10][(b-1) % p[a % 10].length]
a % 10应该是显而易见的，它只取基数的最后一位数字作为我们数组数组中的索引，因为任何非单位都不会影响最后一位数字。
对于像问题开头[1,2,3]这样的列表，可以将其设为递归。在空列表的情况下，我们的初始值为 1，如x^1 === x，我们反转列表以利用.reduce()方法的累积：
[1,2,3].reduceRight( (a,v) =>
p[v % 10][(a-1) % p[v % 10].length], 1)
贯彻执行以使其有意义将如下所示：
- 首先是
a = 1 (initial value), 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 (last iteration), 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。
所以，我们得到了LD([1, 2, 3 ]) === 1，这不难验证：1 ^ (2 ^ 3) === 1 ^ 8 === 1.
问题：
只要指数不超过 10 并且之后没有另一个迭代，这就可以了。但是，如果出现问题。让我解释一下：
假设我们有数组，a = [ 2,2,2,2 ].由于1是我们的初始值，因此列表最初是a = [ 1,2,2,2,2 ]。使用上述缩减：
- 第一次迭代
a = 1, v = 2(记住我们的.reduce1因为它是初始值)：p[2 % 10][(1-1) % p[2 % 10].length]= [ 2,4,8,6 ][0 % 4]= 2- 很容易通过
2 ^ 1 = 2验证，我们的列表现在是 [ 2,2,2,2 ]
- 第二次迭代
a = 2, v = 2：p[2 % 10][(2-1) % p[2 % 10].length]= [ 2,4,8,6 ][1 % 4]= 4- 很容易通过
2 ^ 2 = 4验证，我们的列表现在是 [ 4,2,2 ]
- 第三次迭代
a = 4, v = 2：p[2 % 10][(4-1) % p[2 % 10].length]= [ 2,4,8,6 ][3 % 4]= 6- 很容易通过
2 ^ 4 = 16验证，我们的列表现在是 [ 16,2 ]
- 第四次迭代，问题变得明显。
a = 6, v = 2：p[2 % 10][(6-1) % p[2 % 10].length]= [ 2,4,8,6 ][5 % 4]= 4- 很容易被
2 ^ 16 = 65536反驳.
如果你研究一段时间，就会明白为什么。最终迭代的第三步，
= [ 2,4,8,6 ][5 % 4] = p[ 2,4,8,6 ][1]
应该是
= [ 2,4,8,6 ][15 % 4] = p[ 2,4,8,6 ][3]
因此给出不正确的结果。
问题：
有没有办法基于前一个指数来捕获仅传递上一次迭代的最后一位数字创建的"偏移量"？我是否可以以某种方式将上次迭代中的6与另一条信息传递，以使模数正确？
因此，与其只是返回
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注释中指出的对象或元组。
一个(糟糕的)解决方案是在累加器中跟踪上一次迭代(例如，对于最后一步，我可以返回16并将其用于下一次迭代，而不是返回6，这将给出正确的索引)。但是，如果数字非常大，这是非常不切实际的！假设上一步有数字4142和623，计算4142^623并将其传递是不切实际的。
请注意，我知道还有其他解决方案，但我很好奇是否可以更改此代码以在我编写的单个.reduce语句中解决此问题。那么是否有可能通过修改来解决此问题：
array.reduceRight( (a,v) =>
p[v % 10][(a-1) % p[v % 10].length], 1)
尽管讨论了累加器问题？它几乎有效，我想我离它工作只有一步之遥！
请注意括号！列表[3, 14, 16]等效于3 ^ (14 ^ 16) !== (3 ^ 14) ^ 16
要检查的一些测试，可以验证函数调用LU(array)，其中array是数字数组：
// 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
感谢您的阅读！
进一步的想法：
有一个小小的突破！因此，对于任何以指数为底的整数(即x^y中的x)，LD(x) === LD(x % 10)。这是因为超过第一个(从右到左)的数字不会影响指数结果的单位数字(例如，LD(23 ^ 7) === LD(3 ^ 7))
此外，与const p = [ ...一样，包含单位值循环的数组数组，所有数字的长度都有最小公倍数为 4 的周期，即所有循环都是 1、2 或 4 个数字(例如，p[3] === [ 3,9,7,1 ]单位数组的长度为 4)。
因此，我们可以得出结论LD((x % 10) ^ (y % 4)) === LD(x ^ y).
但请注意，如果一个数字是 4 的倍数，它就会变为零。我们大多数时候都不想要这个！您也不希望20在指数端变得0- 我们希望x的范围为 1 到 10，y 的范围为 1 到 4：
所以，LD((x % 10 || 10) ^ (y % 4 || 4)) === LD(x ^ y).我们可以通过以下方式处理特殊情况
if (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)是合理的，但我不确定如何处理这些信息。
终于！在做了一些挖掘之后，我意识到我可以修改最初的想法并得到我想要的答案：
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呢？因为模数 10 在诸如[ 2,2,2,2 ]的情况下会失去精度，当我们从问题示例中达到最后一步时：
第四次迭代，问题变得明显。
a = 6, v = 2：
p[2 % 10][(6-1) % p[2 % 10].length]
= [ 2,4,8,6 ][5 % 4]
= 4很容易被
2 ^ 16 = 65536反驳.
通过简单地允许最多 20 的倍数，我们就有了数组每个计数的 LCM(最小公共倍数)，以及p的长度，即 10。(LCM([ 1,2,4,10 ]) === 20)。
但是，由于指数现在永远不会高于40^8(大约 6 万亿)，并且在下一次迭代中将其取模 4，我们可以简单地执行指数并每次返回答案。
当然，为了在最后一种情况下得到数字，我们需要取模 10 来返回最后一个数字。
这里还有一些我不明白的东西。
我们允许模值下的任何值保留其与三元运算符的值。 例如，对于指数，prev < 4 ? prev : (prev % 4 + 4).但是我最初认为这是prev === 0 ? 0 : (prev % 4 + 4).
这是因为零的指数与模数的其他倍数没有相同的结束数字，它总是等于 1 (x ^ 0 === 1)。因此，通过添加 4，我们得到一个具有相同最后一位数字的值，并且通过单独保留零，我们仍然得到 1 作为零指数。
为什么需要prev < 4 ? prev : (prev % 4 + 4)才能使这个答案正确？为什么例如，prev = 3，需要3而不是像其他一样添加 4？
我相信你自上而下的方法有些缺陷，因为LD(b)不是LD(a^b)的唯一决定因素，不像a- 即b的所有数字都会影响LD(a^b)的值。因此，使用自上而下的算法，只有在最后计算LD才有意义，这有点违背了重点。
这并不是说你推导出的公式是无用的——恰恰相反。
查看内部索引，我们看到(b - 1) % p[a % 10].length可能会自下而上递归计算。那么L = p[a % 10].length的可能值是多少？1、2 和 4。I = (b - 1) % L的相应可能值为：
- 对于
L = 1来说，I = 0微不足道的。 - 对于
L = 2，I = 0b是否奇数。让我们b = c ^ d，并注意如果c是奇数或d = 0，否则为偶数，则b是奇数。因此，如果我们偷看数组中的下一个数字，这种情况也是微不足道的。 对于
L = 4，I只是b - 1以4为底的最后一位数字(称之为LD4)。我们可以计算一个类似的数字表，并像以前一样处理数组的其余部分：// base 4 table const q = [ [0], // 0^1=0 ... [1], // 1^1=1 ... [2, 0, 0, 0, ..... ], // infinitely recurring [3, 1], // 3^1=3, 3^2=1, 3^3=3, 3^4=1 ... ];
啊。好吧，由于情况很少，一些 if 子句不会有什么坏处：
LD2(a) | LD2(a^b)
----------------------------
0 | 1 if b = 0, else 0
1 | 1 always
LD4(a) | LD4(a^b)
----------------------------------------
0 | 1 if b = 0, else 0
1 | 1 always
2 | 1 if b = 0, 2 if b = 1, else 0
3 | 3 if b odd, else 1
假设0^0 = 1.另外，LD4(b - 1) = LD4(b + 3).
法典：
function isEnd(a, i)
{
return (i > a.length - 1);
}
function isZero(a, i)
{
if (!isEnd(a, i))
if (a[i] == 0)
return !isZero(a, i+1);
return false;
}
function isUnity(a, i)
{
if (isEnd(a, i) || a[i] == 1)
return true;
return isZero(a, i+1);
}
function isOdd(a, i)
{
if (isEnd(a, i) || a[i] % 2 == 1)
return true;
return isZero(a, i+1);
}
function LD2(a, i)
{
if (isEnd(a, i) || a[i] % 2 == 1)
return 1;
return isZero(a, i+1) ? 1 : 0;
}
function LD4(a, i)
{
if (isEnd(a, i)) return 1;
switch (a[i] % 4) {
case 0: return isZero(a, i+1) ? 1 : 0;
case 1: return 1;
case 2:
if (isZero(a, i+1)) return 1;
if (isUnity(a, i+1)) return 2;
return 0;
case 3: return isOdd(a, i+1) ? 3 : 1;
default: return -1; // exception?
}
}
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 ]
];
function LD10(a)
{
let LDa = a[0] % 10;
if (isZero(a, 1)) return 1; // corner case not present in tables
const row = p[LDa];
switch (row.length) {
case 1: return row[0];
case 2: return row[1 - LD2(a, 1)];
case 4: return row[(LD4(a, 1) + 3) % 4];
default: return -1; // exception?
}
}
上面的代码现在通过所有测试用例。