最新要闻

广告

手机

⚽日职乙战报：权田修一离奇乌龙 秋田蓝闪电全场0射正 仍1-1平清水心跳

⚽日职乙战报：权田修一离奇乌龙 秋田蓝闪电全场0射正 仍1-1平清水心跳

 《支付宝》蚂蚁庄园2023年8月26日答案介绍

《支付宝》蚂蚁庄园2023年8月26日答案介绍

家电

  1. 首页
  2. 移动通信
  3. 内容

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

来源：博客园

对于给定的数组[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         else19         {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次方更新t10     else  // 如果t大于等于411     {12       int exponent = int.Parse(BigInteger.ModPow(t, 1, 4).ToString()) + 4;  // 计算指数值，将t对4取模后加上413       t = BigInteger.Pow(x, exponent);  // 使用x的exponent次方更新t14     }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                 

关键词：