对于给定的数组[x1,x2,x3,…,xn],计算幂的累积:x1^(x2^(x3^(…^xn))的最后一位(十进制)数字。
例如,对于数组[3,4,2],您的代码应该返回1,因为3^(4^2)=3^16=43046721。
结果的增长得快得令人难以置信。例如,9^(9^9)有超过3.69亿个数字。你计算的lastDigit必须有效地处理这些数字。
我们假设0^0=1,并且空列表的lastDigit等于1。
算法实现:
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Numerics; 5 namespace Solution 6 { 7 public class Calculator 8 { 9 public static int LastDigit(int[] array) 10 { 11 BigInteger t = 1; 12 var arr = array.Reverse().ToList(); 13 14 foreach(var x in arr) 15 { 16 if(t < 4) 17 t = BigInteger.Pow(x,int.Parse(t.ToString())); 18 else 19 { 20 int exponent = int.Parse(BigInteger.ModPow(t,1,4).ToString()) + 4; 21 t = BigInteger.Pow(x,exponent); 22 } 23 } 24 25 return (int)BigInteger.ModPow(t,1,10); 26 } 27 } 28 }
算法详解:
1 public static int LastDigit(int[] array) 2 { 3 BigInteger t = 1; // 初始化变量t为1,用于存储计算结果 4 var arr = array.Reverse().ToList(); // 将输入数组倒序并转换为列表 5 6 foreach(var x in arr) // 对列表中的每个元素进行循环遍历 7 { 8 if(t < 4) // 如果t小于4 9 t = BigInteger.Pow(x, int.Parse(t.ToString())); // 使用x的t次方更新t 10 else // 如果t大于等于4 11 { 12 int exponent = int.Parse(BigInteger.ModPow(t, 1, 4).ToString()) + 4; // 计算指数值,将t对4取模后加上4 13 t = BigInteger.Pow(x, exponent); // 使用x的exponent次方更新t 14 } 15 } 16 17 return (int)BigInteger.ModPow(t, 1, 10); // 返回t对10取模的结果作为最后一位数字 18 }
在代码中,判断 if(t < 4)
的目的是为了处理指数较小的情况。当指数较小(小于4)时,直接使用 BigInteger.Pow(x, int.Parse(t.ToString()))
计算 x
的指数结果,并将结果赋给变量 t
。
这是因为指数较小的情况下,计算结果不会非常大,可以直接使用 BigInteger.Pow
方法进行计算。这种情况下,不需要进行额外的处理,直接将计算结果赋给 t
即可。
而当指数较大(大于等于4)时,为了避免计算结果过大导致性能问题,代码使用了一种降幂优化策略。在这种情况下,通过计算 t
的模 4 的结果(BigInteger.ModPow(t, 1, 4)
),并加上4,得到一个新的指数值 exponent
。然后使用 BigInteger.Pow(x, exponent)
计算 x
的新指数结果,并将结果赋给 t
。
因此,if(t < 4)
分支用于处理指数较小的情况,而 else
分支用于处理指数较大的情况,并进行了一种优化策略来避免计算结果过大。这样可以在不牺牲性能的情况下,处理更大的指数值。
让我们通过一个示例来解释这个降幂计算过程。
假设我们有以下输入数据:
- `x = 2`:底数为2。
- `t = 10`:指数为10。
根据代码逻辑,我们首先检查指数是否大于等于4。在这种情况下,指数为10大于4,因此我们需要执行优化策略。
1. 计算 `t` 对 4 取模的结果:
- `t_mod4 = t % 4 = 10 % 4 = 2`
这里我们使用 `%` 运算符来计算 `t` 对 4 取模的结果,得到 `2`。
2. 将 `t_mod4` 加上 4,得到新的指数值 `exponent`:
- `exponent = t_mod4 + 4 = 2 + 4 = 6`
这里我们将 `t_mod4` 的结果 `2` 加上 4,得到新的指数值 `6`。
3. 计算 `x` 的新指数结果:
- `new_t = BigInteger.Pow(x, exponent) = BigInteger.Pow(2, 6) = 64`
这里我们使用 `BigInteger.Pow` 方法计算 `x` 的新指数结果,即将底数 `2` 的指数值设为 `6`,得到 `64`。
4. 将新的指数结果赋给 `t`:
- `t = new_t = 64`
我们将计算得到的新指数结果 `64` 赋给变量 `t`。
最后,我们得到的结果是 `t = 64`。这个结果将在后续的代码中继续使用,进行其他的计算或操作。
这就是当指数较大时,代码使用的优化策略的步骤。通过对指数取模并加上一个固定值,我们得到一个较小的指数值,以避免计算结果过大导致性能问题。
测试用例:文章来源:https://www.toymoban.com/news/detail-676859.html
1 namespace Solution { 2 using NUnit.Framework; 3 using System; 4 5 public struct LDCase { 6 public int[] test; 7 public int expect; 8 public LDCase(int[] t, int e) { 9 test = t; 10 expect = e; 11 } 12 } 13 14 [TestFixture] 15 public class SolutionTest { 16 private static int CalculateLD(int[] array) { 17 int ans = 1; 18 for(int i=array.Length-1; i>=0;i--) { 19 int exp = ans; 20 if(ans >= 4) { 21 exp = ans%4+4; 22 } 23 int b = array[i]%4+4; 24 if(i == 0) { 25 b = array[i]%10; 26 } 27 else if(array[i] < 4) { 28 b = array[i]; 29 } 30 ans = (int)(Math.Pow(b, exp)); 31 } 32 return ans%10; 33 } 34 35 [Test] 36 public void SampleTest() { 37 LDCase[] allCases = new LDCase[] { 38 new LDCase(new int[0], 1), 39 new LDCase(new int[] {0,0}, 1), 40 new LDCase(new int[] {0,0,0}, 0), 41 new LDCase(new int[] {1,2}, 1), 42 new LDCase(new int[] {3,3,1}, 7), 43 new LDCase(new int[] {3,3,2}, 3), 44 new LDCase(new int[] {3,5,3}, 3), 45 new LDCase(new int[] {3,4,5}, 1), 46 new LDCase(new int[] {4,3,6}, 4), 47 new LDCase(new int[] {7,6,1}, 9), 48 new LDCase(new int[] {7,6,2}, 1), 49 new LDCase(new int[] {7,6,21}, 1), 50 new LDCase(new int[] {12,30,21}, 6), 51 new LDCase(new int[] {2,0,1}, 1), 52 new LDCase(new int[] {2,2,2,0}, 4), 53 new LDCase(new int[] {2,2,101,2},6), 54 new LDCase(new int[] {4,0}, 1), 55 new LDCase(new int[] {3,0,0}, 3), 56 new LDCase(new int[] {2,2,1}, 4), 57 new LDCase(new int[] {2,2,1,2}, 4), 58 new LDCase(new int[] {3,3,0,0}, 7), 59 new LDCase(new int[] {3,4,0}, 3), 60 new LDCase(new int[] {3,2,1,4,4},9), 61 new LDCase(new int[] {5,0}, 1), 62 new LDCase(new int[] {2,3,2}, 2), 63 new LDCase(new int[] {82242,254719,736371}, 8), 64 new LDCase(new int[] {937640,767456,981242}, 0), 65 new LDCase(new int[] {123232,694022,140249}, 6), 66 new LDCase(new int[] {499942,898102,846073}, 6), 67 new LDCase(new int[] {837142,918895,51096}, 2), 68 new LDCase(new int[] {625703,43898,614961,448629}, 1), 69 new LDCase(new int[] {2147483647,2147483647,2147483647,2147483647}, 3) 70 }; 71 for(int i=0; i<allCases.Length;i++) { 72 string msg = $"Incorrect answer for array=[{string.Join(", ", allCases[i].test)}]"; 73 Assert.AreEqual(allCases[i].expect, Calculator.LastDigit(allCases[i].test), msg); 74 } 75 } 76 77 [Test] 78 public void RandomTest() { 79 Random rnd = new Random(); 80 81 for(int i=0; i<100;i++) { 82 int size = rnd.Next(1,20); 83 int[] array1 = new int[size]; 84 int[] array2 = new int[size]; 85 int[] array3 = new int[size]; 86 for(var j=0; j<size;j++) { 87 var rand1 = rnd.Next(0,1000000); 88 var rand2 = rnd.Next(0,3); 89 var rand3 = rnd.Next(0,2); 90 if(j == 0) { 91 rand1++; rand2++; rand3++; 92 } 93 array1[j] = rand1; 94 array2[j] = rand2; 95 array3[j] = rand3; 96 } 97 98 string msg1 = $"Incorrect answer for array=[{string.Join(", ", array1)}]"; 99 int expect1 = SolutionTest.CalculateLD(array1); 100 Assert.AreEqual(expect1, Calculator.LastDigit(array1), msg1); 101 102 string msg2 = $"Incorrect answer for array=[{string.Join(", ", array2)}]"; 103 int expect2 = SolutionTest.CalculateLD(array2); 104 Assert.AreEqual(expect2, Calculator.LastDigit(array2), msg2); 105 106 string msg3 = $"Incorrect answer for array=[{string.Join(", ", array3)}]"; 107 int expect3 = SolutionTest.CalculateLD(array3); 108 Assert.AreEqual(expect3, Calculator.LastDigit(array3), msg3); 109 } 110 } 111 } 112 }
文章来源地址https://www.toymoban.com/news/detail-676859.html
到了这里,关于【算法】用c#实现计算方法中的经典降幂优化策略,减少计算复杂度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!