问题概述:
请注意,我会滥用^
,并将其用作幂符号,尽管在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
。
如果进行几个测试案例,也很容易得出幂的最后一位数字会“循环”:
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(初始值),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
。
因此,我们得到 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]
因此会产生不正确的结果。
问题:
基于先前的指数,是否有一种方式可以捕获仅传递上一次迭代的最后一个数字所创建的“偏移量”?我是否可以以某种方式传递上一个迭代中的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 ]
单位数组的长度为四。
因此,我们可以得出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)
,但我不确定如何利用这个信息。
reduceRight
:-) - Bergi**
,它是 JavaScript 中的指数运算符 ;) - AKX