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

这篇具有很好参考价值的文章主要介绍了【算法】用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         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 }

 文章来源地址https://www.toymoban.com/news/detail-676859.html

到了这里,关于【算法】用c#实现计算方法中的经典降幂优化策略,减少计算复杂度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 空间划分算法优化碰撞检测研究(网格划分、四叉树\八叉树、层次包围盒树BVH)Unity C#实现

    目录 前言 一、Demo说明 二、暴力法  三、网格划分 实测 分析 四、四叉树 四叉树的构建细节  实测 五、松散四叉树 实测 八叉树 六、层次包围盒树(BVH) 包围盒 AABB树 AABB树构建细节 实测 总结   碰撞检测是一个非常经典的问题。虽然现在我们都有物理引擎提供的便捷接口

    2023年04月11日
    浏览(84)
  • 机器学习笔记之优化算法(十八)经典牛顿法

    本节将介绍 优化算法——经典牛顿法 ( Newton Method ) (text{Newton Method}) ( Newton Method ) 。 下降方向 在线搜索方法——方向角度中介绍了 下降方向 ( Descent Direction ) (text{Descent Direction}) ( Descent Direction ) 的概念。首先,通过推导得到 如果 更新方向 P k mathcal P_k P k ​ 与梯度方向

    2024年02月11日
    浏览(37)
  • 快速排序算法(递归非递归,三种方法实现,优化)

    快速排序 代码实现 ⚪单趟排序 版本一 ⚪快速排序 递归 关于快排优化 ⚪单趟排序 版本二 ⚪单趟排序 版本三 ⚪快速排序 非递归 特性总结 快速排序作为效率相对较高的排序,分别有递归与非递归两种写法,但都是 进行单趟排序,随后再解决其余问题。 快速排序的平均时间

    2024年02月05日
    浏览(43)
  • 【算法】用c#实现自定义字符串编码及围栏解码方法

    编写一个函数/方法,它接受2个参数、一个字符串和轨道数,并返回ENCODED字符串。 编写第二个函数/方法,它接受2个参数、一个编码字符串和轨道数,并返回DECODED字符串。 然后使用围栏密码对其进行解码。 这种密码用于通过将每个字符沿着一组“竖状轨道”依次放在对角线

    2024年02月12日
    浏览(38)
  • 机器学习笔记之优化算法(十九)经典牛顿法的收敛性分析

    上一节整体介绍了 经典牛顿法 ,并讨论了其更新方向 P k mathcal P_k P k ​ 是否为 下降方向 。本节将对 经典牛顿法 在迭代过程中的收敛性 进行分析。 在这些迭代算法中,我们关注的重点在于 算法在迭代过程中 是否收敛 ,以及它的 收敛速度 。 Wolfe text{Wolfe} Wolfe 准则的收

    2024年02月11日
    浏览(43)
  • C#的AOP(最经典实现)

    (适用于.NET/.NET Core/.NET Framework) 【目录】 0.前言 1.第一个AOP程序 2.Aspect横切面编程 3.一个横切面程序拦截多个主程序 4.多个横切面程序拦截一个主程序 5.AOP的泛型处理 (扩充) 6.AOP的异步处理 (扩充) 7.优势总结 8.展望 0.前言 AOP(Aspect Oriented Programming)是“面向横切面编程

    2024年04月11日
    浏览(23)
  • 蚂蚁群优化算法在JavaScript环境下的实现与在负载均衡调度中的应用

    在我们的日常生活中,我们可以看到蚂蚁通过寻找食物并返回蚁巢的过程,展现出了一种非常高效的搜索策略。这种策略在计算机科学中被引入,并被称为蚁群算法。蚁群算法是一种群体智能优化算法,它模拟了蚂蚁寻找食物的行为,从而实现了全局优化的目标。在本文中,

    2024年02月15日
    浏览(64)
  • 数据结构(五)数据结构与算法中的经典题

    本文是在原本数据结构与算法闯关的基础上总结得来,加入了自己的理解和部分习题讲解。至此数据结构介绍已完结,后续会把数据结构算法题系列更完。 原活动链接 邀请码: JL57F5 根据要求完成题目 Q1. (单选)以下哪些数据结构支持随机访问? A. 数组 B. 单链表 C. 双向链表

    2024年01月20日
    浏览(44)
  • 基于粒子群优化算法的面向综合能源园区的三方市场主体非合作交易方法(Matlab代码实现)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码实现 ​ 随着

    2023年04月09日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包