电源列表的最后一位
Last digit of power list
问题概要：
请注意我会滥用 ^ 的生命并将其用作电源符号，尽管插入符号是 JS 中的按位异或运算符。
取一个正整数列表，
[ 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，不管怎样
如果你做一些测试用例，也很容易得出结论，最后的幂数 "loop":
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），我们可以使用该计数的 modulus 来计算最后一位。
例如，LD(2 ^ 55) === LD(2 ^ (55 % 4)) === LD(2 ^ 3)
因此，通过一些数学运算，我们可以为每个最后一位得到一个很好的数组数组，其中数组数组的索引是基数，每个数组的索引是mod循环长度的单位：
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（记住我们的 .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 ]
- 第二次迭代
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]
因此给出了错误的结果。
问题：
有没有一种方法，基于之前的指数，通过仅传递之前迭代的最后一位数字来捕获 "offset"？我能否以某种方式在最后一次迭代中传递 6 和另一条信息，以便 modulus 是正确的？
所以不只是 returning
p[v % 10][(a-1) % p[v % 10].length)
也许可以 return
[
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 在评论中指出的对象或元组。
一个（糟糕的）解决方案是跟踪累加器中的前一次迭代（例如，对于最后一步，而不是 returning 6，我可以 return 16 并将其用于下一次迭代，这将给出正确的索引）。但是，如果数字非常大，这是非常不切实际的！假设上一步有数字 4142 和 623，计算 4142^623 并传递它是不切实际的。
请注意，我知道还有其他解决方案，但我很好奇是否可以更改此代码以在我编写的单个 .reduce 语句中解决此问题。那么是否可以通过modifying来解决这个问题：
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 ] 单位数组的长度为四）。
所以，我们可以得出结论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) 是合理的，但我不确定如何处理这些信息。
我认为您的自上而下方法有些缺陷，因为 LD(b) 不是 LD(a^b) 的唯一决定因素，与 a 不同 - 即 all 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，如果b是奇数，I = 0。设 b = c ^ d，并注意如果 c 为奇数或 d = 0 为奇数，则 b 为奇数，否则为偶数。因此，如果我们查看数组中的下一个数字，这种情况也是微不足道的。
对于 L = 4，I 只是 base 4 中 b - 1 的最后一位（称之为 LD4).我们可以计算一个类似的数字 table，并像以前一样处理数组的其余部分：
// 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?
}
}
以上代码现在通过了所有测试用例。
终于！ 在做了一些挖掘之后我意识到我可以修改最初的想法并得到我想要的答案:
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 ] 等情况下会失去精度，当我们从问题示例中点击最后一步时：
Fourth iteration, where the issue becomes apparent. a = 6, v = 2:
p[2 % 10][(6-1) % p[2 % 10].length]
= [ 2,4,8,6 ][5 % 4]
= 4
Easily disproved by 2 ^ 16 = 65536.
通过简单地允许最大为 20 的倍数，我们得到数组的每个计数的 LCM（最小公倍数），以及 p 的长度，即 10。（LCM（ [ 1,2,4,10 ]) === 20).
然而，由于指数现在永远不会高于 40^8（大约 6 万亿），并且在下一次迭代中对 4 取模，我们可以简单地做指数和 return每次都回答。
当然要得到最后一个数字，我们需要对 10 取模 return 最后一个数字。
这里还有一些我不明白的地方。
我们允许模值下的任何值通过三元运算符保留其值。例如，对于指数，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？
问题概要：
请注意我会滥用 ^ 的生命并将其用作电源符号，尽管插入符号是 JS 中的按位异或运算符。
取一个正整数列表，
[ 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，不管怎样
如果你做一些测试用例，也很容易得出结论，最后的幂数 "loop":
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），我们可以使用该计数的 modulus 来计算最后一位。
例如，LD(2 ^ 55) === LD(2 ^ (55 % 4)) === LD(2 ^ 3)
因此，通过一些数学运算，我们可以为每个最后一位得到一个很好的数组数组，其中数组数组的索引是基数，每个数组的索引是mod循环长度的单位：
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（记住我们的.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 ]
- 第二次迭代
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]
因此给出了错误的结果。
问题：
有没有一种方法，基于之前的指数，通过仅传递之前迭代的最后一位数字来捕获 "offset"？我能否以某种方式在最后一次迭代中传递 6 和另一条信息，以便 modulus 是正确的？
所以不只是 returning
p[v % 10][(a-1) % p[v % 10].length)
也许可以 return
[
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 在评论中指出的对象或元组。
一个（糟糕的）解决方案是跟踪累加器中的前一次迭代（例如，对于最后一步，而不是 returning 6，我可以 return 16 并将其用于下一次迭代，这将给出正确的索引）。但是，如果数字非常大，这是非常不切实际的！假设上一步有数字 4142 和 623，计算 4142^623 并传递它是不切实际的。
请注意，我知道还有其他解决方案，但我很好奇是否可以更改此代码以在我编写的单个 .reduce 语句中解决此问题。那么是否可以通过modifying来解决这个问题：
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 ] 单位数组的长度为四）。
所以，我们可以得出结论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) 是合理的，但我不确定如何处理这些信息。
我认为您的自上而下方法有些缺陷，因为 LD(b) 不是 LD(a^b) 的唯一决定因素，与 a 不同 - 即 all 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，如果b是奇数，I = 0。设b = c ^ d，并注意如果c为奇数或d = 0为奇数，则b为奇数，否则为偶数。因此，如果我们查看数组中的下一个数字，这种情况也是微不足道的。 对于
L = 4，I只是 base 4 中b - 1的最后一位（称之为LD4).我们可以计算一个类似的数字 table，并像以前一样处理数组的其余部分：// 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?
}
}
以上代码现在通过了所有测试用例。
终于！ 在做了一些挖掘之后我意识到我可以修改最初的想法并得到我想要的答案:
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 ] 等情况下会失去精度，当我们从问题示例中点击最后一步时：
Fourth iteration, where the issue becomes apparent.
a = 6, v = 2:
p[2 % 10][(6-1) % p[2 % 10].length]
= [ 2,4,8,6 ][5 % 4]
= 4Easily disproved by
2 ^ 16 = 65536.
通过简单地允许最大为 20 的倍数，我们得到数组的每个计数的 LCM（最小公倍数），以及 p 的长度，即 10。（LCM（ [ 1,2,4,10 ]) === 20).
然而，由于指数现在永远不会高于 40^8（大约 6 万亿），并且在下一次迭代中对 4 取模，我们可以简单地做指数和 return每次都回答。
当然要得到最后一个数字，我们需要对 10 取模 return 最后一个数字。
这里还有一些我不明白的地方。
我们允许模值下的任何值通过三元运算符保留其值。例如，对于指数，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？