【算法】用c#实现计算方法中的经典降幂优化策略,减少计算复杂度

  • 【算法】用c#实现计算方法中的经典降幂优化策略,减少计算复杂度已关闭评论
  • 80 次浏览
  • A+
所属分类:.NET技术
摘要

对于给定的数组[x1,x2,x3,…,xn],计算幂的累积:x1^(x2^(x3^(…^xn))的最后一位(十进制)数字。

对于给定的数组[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`。这个结果将在后续的代码中继续使用,进行其他的计算或操作。

这就是当指数较大时,代码使用的优化策略的步骤。通过对指数取模并加上一个固定值,我们得到一个较小的指数值,以避免计算结果过大导致性能问题。


 

测试用例:

  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 }