logo标签列表

幂列表的最后一位数字

javascriptarraysmathexponent
13

问题概述：

请注意，我会滥用^，并将其用作幂符号，尽管在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)，但我不确定如何利用这个信息。

5
这得算是我在 Stack Overflow 上看过的最详细的问题之一了，为此点赞。但唯一缺少的是 -> 我写过的单个 .reduce 语句。我似乎在这里没看到它... - Keith
@Keith 请查看编辑内容！希望它和详细说明一样清晰 :) - Nick Bull
2
提示：使用 reduceRight :-) - Bergi
2
关于您对插入符号的滥用 - 您可以使用 **，它是 JavaScript 中的指数运算符 ;) - AKX
啊不，不是那样。我已经在我的答案中实现了它。我的意思是3^2^0^5 -> 3^1^5。 - user1589069
显示剩余9条评论
2个回答
4

终于了！经过一番调查，我意识到可以修改最初的想法，得到我想要的答案：

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)

因为在某些情况下，例如 [2,2,2,2] ，取模为 10 会丢失精度，所以为什么要取模 20 呢？这是因为多个数组的计数器每个都需要有一个最小公倍数（LCM），而这个 LCM 的值为数组长度的 LCM 的倍数。同时，由于底数不会超过 40^8，并且在下一次迭代中它被取模为 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 呢？
@meowgoesthedog 抱歉，我之前在测试中尝试了一次，另外还有一个答案在上面。请重新尝试测试 :p - Nick Bull
@meowgoesthedog 我不会骗你，我仍然不太明白为什么会这样。一开始我写它只是作为另一种等价的写法 acc === 0 ? 0 : ...，就像底部所述一样，但似乎对于模数以下的所有值都这样做才最终起作用。如果有任何见解，将不胜感激！ - Nick Bull
1
我认为你的自上而下的方法有些缺陷，因为与a不同，LD(b)不是LD(a^b)中唯一的决定因素 - 也就是说，所有b的数字都会影响LD(a^b)的值。因此，使用自上而下的算法只有在最后计算LD才有意义，这有点违背了初衷。

这并不意味着你推导出来的公式没有用 - 恰恰相反。

从内部指数看，我们可以看到(b - 1) % p[a % 10].length可能会被自下而上地递归计算。那么L = p[a % 10].length的可能值是什么？是1、2和4。相应的I = (b - 1) % L的可能值为：

  • For L = 1, I = 0 trivially.
  • For L = 2, I = 0 if b is odd. Let b = c ^ d, and note that b is odd if either c is odd or d = 0, otherwise even. Thus this case is also trivial if we peek at the next number in the array.

  • For L = 4, I is simply the last digit of b - 1 in base 4 (call it LD4). We can compute an analogous digit table, and process the rest of the array as before:

    // 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?
   }
}

上述代码现在通过了所有的测试用例。
这看起来就是答案！午餐时会仔细检查一下。太棒了！ - Nick Bull
@NickBull 谢谢。我会尝试像你那样提出自顶向下的解决方案，但从目前的推理来看，我觉得这可能不太可能 :/ - meowgoesthedog
请不要讨厌我。但是...我认为它无法处理 275232^(84547^729410)。http://www.wolframalpha.com/widgets/view.jsp?id=56c82ccd658e09e829f16bb99457bcbc - Nick Bull
这是一个非常令人印象深刻的答案，顺便说一句。阅读并学习真是太棒了 :) - Nick Bull
@NickBull 哈哈，我找到了错误的源头 - isOdd 函数中有一个错误的 NOT 运算符。移除它后问题得到解决（得到了预期的 2），并且也不影响之前的测试用例（这可能就是为什么我没有发现它的原因）。 - meowgoesthedog
显示剩余8条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接