代码之家  ›  专栏  ›  技术社区  ›  Nick Bull

功率表的最后一位

exponent math arrays javascript
  •  9
  • Nick Bull  · 技术社区  · 8 年前

    问题概述:

    请注意我会滥用生命 ^ 并将其用作幂符号,尽管插入符号是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,
...

    因此,如果我们知道某个特定基数循环中的数字的计数(4代表上一个基数2的例子),我们可以使用该计数的模来计算最后一个数字。

    例如。, 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 (记住 .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在注释中指出的对象或元组。

    一个(糟糕的)解决方案是跟踪累加器中的前一个迭代(例如,对于最后一个步骤,而不是返回 6个 ,我可以回去 16 并在下一次迭代中使用它,这将给出正确的索引)。但是,如果数字很大,那就太不切实际了!说上一步有数字 4142 和 623 ,计算起来不实用 4142^623 把它传下去。

    请注意,我知道有其他的解决方案,但我很好奇是否可以更改此代码来解决这个问题 .减少 我写的声明。因此,是否可以通过修改以下内容来解决此问题: 

    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 在里面 x^y )我是说, 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 在指数方面-我们希望 十 从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) ,但我不知道如何处理这些信息。

    3 回复  |  直到 8 年前
        1
  •  2
  •   Nick Bull    8 年前

    终于! 在做了一些调查之后,我意识到我可以修改最初的想法并得到我想要的答案: 

    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的倍数,我们为数组的每个计数以及 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,我们得到一个与最后一个数字相同的值,如果不加0,我们仍然得到0指数的1。

    为什么是这样 上一个4?上一页:(上一页%4+4) 是为了让这个答案正确吗?为什么是, prev = 3 ,必须是 3 而不是像其他人一样加4?

        2
  •  1
  •   meowgoesthedog    8 年前

    我相信你自上而下的方法有些缺陷,因为 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=0 如果 乙 很奇怪。让 b = c ^ d ,请注意 乙 如果其中一个 c 是奇怪的还是 d = 0 ,否则就算了。因此,如果我们查看数组中的下一个数字,这个例子也很简单。

    • 为了 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?
   }
}

    上面的代码现在通过了所有的测试用例。

        3
  •  -1
  •   aec    8 年前

    让我们记住 (a^b)%c = (a%c)^b % c 是的。

    我想知道 lastDigit 是的。
    lastDigit = x^y^z % 10 = (x%10 ^ y ^ z) % 10 是的。

    p[x % 10] 有重复力量的模式 x 是的。图案的长度可以是1、2或4。

    如果图案的长度是4,那么 lastDigit = p[x][(y^z % 4)] = p[x][(y%4)^z %4]

    如果我们的问题不是因为 x,y,z 但是为了 x0,x1,x2...xn 以下内容: 

    lastDigit
 = p[x0][(x1 ^ x2 ... ^ xn-1 ^ xn) %4]
 = p[x0][((x1 ^ x2 ... ^ xn-1)%4 ^ xn) %4]

    我认为递归性现在很明显了:

    我用这个号码 4 对于余数,因为它是可以除1、2和4的最小数,对于余数,模式也相对容易找到。 

    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 ]	 
];

//returns x^y % 4
function powMod4(x, y) {
	switch (x % 4) {
		case 0:
			return 0;
		case 1:
			return 1;
		case 2:
			return y == 1 ? 2 : 0;
		case 3:
			return (y % 2) == 0 ? 1 : 3;
	}
}

function foo(arr) {
	arr = arr.map((it, i, list) => {
		if (i + 1 < list.length && list[i + 1] === 0) {
			return 1;
		} else {
			return it;
		}
	}).filter(x => x !== 0);

	let firstElem = arr[0] % 10;
	let l = p[firstElem].length

	let resp = arr.slice(1).reduce((acc, v) => {
		if (acc === undefined) {
			return v
		}
		let rem = powMod4(acc, v);
		//console.log(v, acc, " => ", rem);
		return rem;

	}, undefined);


	return p[firstElem][(resp + l - 1) % l];
}

function test(arr, expected) {
  let resp = foo(arr);
	console.log(arr.join("^"), resp, resp == expected ? "ok" : "FAIL")
}

test([3, 4, 5], 1)
test([2, 2, 2, 2], 6)
test([4, 13, 16], 4)
test([3,5,7,10], 3)
test([41,42,43], 1)
test([7,6,21], 1)
test([2,2,2,0], 4)

    所以我所做的就是,我放弃了ld函数。相反,我试图找到 x1^x2...^xn % p[x0].length 是的。相反,你想找到 x1^x2...^xn % 10

    推荐文章
    code-geek  ·  Jquery根据单选按钮选择隐藏或显示文本字段
    1 年前
    Niobos  ·  如何/是否有方法使通用算法函数同时与同步和异步函数一起工作?
    1 年前
    Alex  ·  在轻量级中同时解构和不解构变量
    1 年前
    Ângelo Rigo  ·  ReactJS映射:如何迭代[关闭]
    1 年前
    bairog  ·  从按属性筛选的对象数组字典中创建值数组
    1 年前
    KaiMcKiernan  ·  基于Math.random()的函数在另一个函数内不起作用[关闭]
    1 年前
    David Jeong  ·  浏览器不会为浏览器自动添加的某些标头发送CORS预检请求吗?
    1 年前
    user29519291  ·  为不同的变量创建一个带有可重用Click函数的简单菜单
    1 年前
    user3472810  ·  Angular@Output/EventEmitter返回undefined
    1 年前
    lokiuucx  ·  JS对象属性返回未定义,尽管对象属性应该有值
    1 年前
    关于   移动版
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号