【算法】湖心岛上的数学梦--用c#实现一元多次方程的展开式

渐行渐远的童贞

每天清晨，当第一缕阳光洒在湖面上，一个身影便会出现在湖心小岛上。她坐在一块大石头上，周围被茂盛的植物环绕，安静地沉浸在数学的世界中。
这个姑娘叫小悦，她的故事在这个美丽的湖心小岛上展开。每天早晨，她都会提前来到湖边，仔细观察水下的植物，然后抽出时间来钻研一元x次方程。她身上的气息混合着湖水的清新和植物的芬芳，形成一种独特的味道，让人感到宁静与祥和。
然而，一元x次方程的展开对于小悦来说，并不是一件容易的事。这个看似简单的数学问题，却困扰了她许久。然而，小悦并没有向困难低头，她坚信，只要努力，就一定能够找到解决的方法。
在这座小岛上，小悦度过了无数个早晨。她反复琢磨着方程的特点，尝试寻找解法。有时候，她会陷入深深的思考，甚至忘记时间；有时候，她会突然灵光一闪，兴奋地写下展开式的公式。每一个早晨，小悦都在进步，她的眼中闪耀着对知识的渴望和对梦想的坚定。
终于有一天，通过前面的积累，小悦灵光一闪，意识到她可以通过将一元x次方程的每一项分别展开，然后再将这些展开式合并起来，得到一元x次方程的展开式。于是她拿起笔和纸，开始耐心地展开每一项。首先，她展开了一元x次方程中的常数项，接着展开了一次项、二次项、三次项……，最后将所有展开式合并起来，得到了一元x次方程的展开式。小悦看着自己长期努力得来的成果，激动得热泪盈眶。
她无法掩饰内心的喜悦，兴奋地在湖边跳跃着。湖面上的波纹在阳光的照射下闪着金光，似乎在为她的成功欢呼。那一刻，小悦觉得自己仿佛成为了湖水的一部分，与周围的环境融为一体。
随着时间的推移，小悦在岛上的生活也变得更加丰富多彩。她开始尝试将数学知识应用到日常生活中，在烹饪时运用几何学来切蛋糕，或者在散步时用代数知识来计算最短路径问题。这些小小的尝试让小悦意识到，知识不仅仅是为了考试和学术，它更是一种工具，可以帮助她更好地生活。
这个美丽的湖心小岛成为了小悦成长的见证。她在知识的海洋中探索，用数学来解读自然界的奥秘。清晨的阳光照耀在她的书桌上，给她带来温暖和勇气。傍晚时分，当夕阳洒在湖面上，小悦坐在窗前，静静地看着湖面的金辉渐渐消失在暮色中。
小悦面临的一元多次方程的展开式问题如下，她是如何处理呢：
输入一个带有一个单字符变量的表达式，并将其展开。表达式的形式为（ax+b）^n，其中a和b是整数，可以是正的，也可以是负的，x是任何单字符变量，n是自然数。如果a=1，则变量前面不会放置任何系数。如果a=-1，则变量前面将放一个“-”。
展开后的表达式应以字符串形式返回，格式为ax^b+cx^d+ex^f。。。其中a、c和e是项的系数，x是原始表达式中传递的原始一个字符变量，b、d和f是每个项中x的幂，并且是递减的。
如果项的系数为零，则不应包括该项。如果一个项的系数为1，则不应包括该系数。如果项的系数为-1，则只应包含“-”。如果项的幂为0，则只应包括系数。如果项的幂为1，则应排除插入符号和幂。
示例：
EdmSolution.Expand("(x+1)^2"); // returns "x^2+2x+1"
EdmSolution.Expand("(p-1)^3");      // returns "p^3-3p^2+3p-1"
EdmSolution.Expand("(2f+4)^6");     // returns "64f^6+768f^5+3840f^4+10240f^3+15360f^2+12288f+4096"
EdmSolution.Expand("(-2a-4)^0");    // returns "1"
EdmSolution.Expand("(-12t+43)^2");  // returns "144t^2-1032t+1849"
EdmSolution.Expand("(r+0)^203");    // returns "r^203"
EdmSolution.Expand("(-x-1)^2");     // returns "x^2+2x+1"
算法实现：

1. 1 public class EdmSolution
2. 2 {
3. 3     // 定义一个只读的静态正则表达式对象，用于匹配表达式的模式
4. 4     private readonly static Regex pattern = new Regex(@"^\((-?\d*)(.)([-+]\d+)\)\^(\d+)$", RegexOptions.Compiled);
5. 5   
6. 6     // 定义一个静态方法，用于展开给定的表达式
7. 7     public static string Expand(string expr)  
8. 8     {
9. 9         // 使用正则表达式匹配给定的表达式，并将匹配结果转换为字符串数组
10. 10         var matches = pattern.Matches(expr).Cast<Match>().First().Groups.Cast<Group>().Skip(1).Select(g => g.Value).ToArray();
11. 11         
12. 12         // 解析匹配结果中的各个分组，并赋值给对应的变量
13. 13         var a = matches[0].Length == 0 ? 1 : matches[0] == "-" ? -1 : int.Parse(matches[0]);
14. 14         var x = matches[1];
15. 15         var b = int.Parse(matches[2]);
16. 16         var n = int.Parse(matches[3]);
17. 17         
18. 18         // 计算系数f的初始值，使用BigInteger类处理大整数
19. 19         var f = new BigInteger(Math.Pow(a, n));
20. 20         
21. 21         // 根据系数f的值确定常数c的值
22. 22         var c = f == -1 ? "-" : f == 1 ? "" : f.ToString();
23. 23      
24. 24         // 处理特殊情况：指数为0或常数为0的情况
25. 25         if (n == 0) return "1";
26. 26         if (b == 0) return $"{c}{x}{(n > 1) ? "^" : ""}{n}";
27. 27         
28. 28         // 创建一个StringBuilder对象，用于存储展开后的表达式
29. 29         var res = new StringBuilder();
30. 30      
31. 31         // 循环展开表达式的每一项
32. 32         for (var i = 0; i <= n; i++)
33. 33         {
34. 34             // 根据系数f的符号和当前项的位置，添加"+"或"-"符号
35. 35             if (f > 0 && i > 0) res.Append("+");
36. 36             if (f < 0) res.Append("-");
37. 37            
38. 38             // 添加系数的绝对值，如果系数大于1或当前项不是第一项
39. 39             if (i > 0 || f * f > 1) res.Append($"{BigInteger.Abs(f)}");
40. 40            
41. 41             // 添加变量x，如果当前项不是最后一项
42. 42             if (i < n) res.Append(x);
43. 43            
44. 44             // 添加指数符号和指数值，如果当前项不是倒数第二项
45. 45             if (i < n - 1) res.Append($"^{n - i}");
46. 46            
47. 47             // 更新系数f的值
48. 48             f = f * (n - i) * b / a / (i + 1);
49. 49         }
50. 50      
51. 51         // 将StringBuilder对象转换为字符串，并返回展开后的表达式
52. 52         return res.ToString();
53. 53     }
54. 54 }

复制代码

算法运行步骤：EdmSolution.Expand("(-5m+3)^4")
1. 匹配表达式：(-5m+3)^4
2. 使用正则表达式匹配给定的表达式，得到匹配结果：
   - matches[0] = "-5"
   - matches[1] = "m"
   - matches[2] = "+3"
   - matches[3] = "4"
3. 解析匹配结果中的各个分组：
   - a = -5
   - x = "m"
   - b = 3
   - n = 4
4. 计算系数f的初始值：f = (-5)^4 = 625
5. 根据系数f的值确定常数c的值：c = ""
6. 检查特殊情况：n = 4，不为0；b = 3，不为0
7. 创建StringBuilder对象res，用于存储展开后的表达式
8. 开始循环展开表达式的每一项：
   - 第一项：i = 0
     - f > 0，不添加"+"符号
     - f * f > 1，添加系数的绝对值：625
     - i < n，添加变量x："m"
     - i < n - 1，添加指数符号和指数值："^4"
     - 更新系数f的值：f = 625 * (4 - 0) * 3 / -5 / (0 + 1) = -1500
   - 第二项：i = 1
     - f < 0，添加"-"符号
     - f * f > 1，添加系数的绝对值：1500
     - i < n，添加变量x："m"
     - i < n - 1，添加指数符号和指数值："^3"
     - 更新系数f的值：f = -1500 * (4 - 1) * 3 / -5 / (1 + 1) = 1350
   - 第三项：i = 2
     - f < 0，添加"-"符号
     - f * f > 1，添加系数的绝对值：1350
     - i < n，添加变量x："m"
     - i < n - 1，添加指数符号和指数值："^2"
     - 更新系数f的值：f = 1350 * (4 - 2) * 3 / -5 / (2 + 1) = -540
   - 第四项：i = 3
     - f < 0，添加"-"符号
     - f * f > 1，添加系数的绝对值：540
     - i < n，添加变量x："m"
     - i < n - 1，不添加指数符号和指数值
     - 更新系数f的值：f = 540 * (4 - 3) * 3 / -5 / (3 + 1) = 81
   - 第五项：i = 4
     - f < 0，添加"-"符号
     - f * f > 1，添加系数的绝对值：81
     - i < n，不添加变量x
     - i < n - 1，不添加指数符号和指数值
     - 更新系数f的值：f = 81 * (4 - 4) * 3 / -5 / (4 + 1) = 0
9. 循环结束，返回StringBuilder对象res转换后的字符串："625m^4-1500m^3+1350m^2-540m+81"
10. 断言结果与期望值相等，测试通过
测试用例：
[code]  1 namespace Solution  2 {  3     using NUnit.Framework;  4     using System;  5     using System.Collections.Generic;  6     using System.Text;  7     using System.Text.RegularExpressions;  8   9     [TestFixture] 10     public class SolutionTest 11     { 12         [Test] 13         public void testBPositive() 14         { 15             Assert.AreEqual("1", EdmSolution.Expand("(x+1)^0")); 16             Assert.AreEqual("x+1", EdmSolution.Expand("(x+1)^1")); 17             Assert.AreEqual("x^2+2x+1", EdmSolution.Expand("(x+1)^2")); 18             Assert.AreEqual("x^3+3x^2+3x+1", EdmSolution.Expand("(x+1)^3")); 19             Assert.AreEqual("x^4+4x^3+6x^2+4x+1", EdmSolution.Expand("(x+1)^4")); 20             Assert.AreEqual("x^5+5x^4+10x^3+10x^2+5x+1", EdmSolution.Expand("(x+1)^5")); 21             Assert.AreEqual("1", EdmSolution.Expand("(x+2)^0")); 22             Assert.AreEqual("x+2", EdmSolution.Expand("(x+2)^1")); 23             Assert.AreEqual("x^2+4x+4", EdmSolution.Expand("(x+2)^2")); 24             Assert.AreEqual("x^3+6x^2+12x+8", EdmSolution.Expand("(x+2)^3")); 25             Assert.AreEqual("x^4+8x^3+24x^2+32x+16", EdmSolution.Expand("(x+2)^4")); 26             Assert.AreEqual("x^5+10x^4+40x^3+80x^2+80x+32", EdmSolution.Expand("(x+2)^5")); 27             Assert.AreEqual("t^5+10t^4+40t^3+80t^2+80t+32", EdmSolution.Expand("(t+2)^5")); 28             Assert.AreEqual("y^15+75y^14+2625y^13+56875y^12+853125y^11+9384375y^10+78203125y^9+502734375y^8+2513671875y^7+9775390625y^6+29326171875y^5+66650390625y^4+111083984375y^3+128173828125y^2+91552734375y+30517578125", EdmSolution.Expand("(y+5)^15")); 29         } 30  31         [Test] 32         public void testBNegative() 33         { 34             Assert.AreEqual("1", EdmSolution.Expand("(x-1)^0")); 35             Assert.AreEqual("x-1", EdmSolution.Expand("(x-1)^1")); 36             Assert.AreEqual("x^2-2x+1", EdmSolution.Expand("(x-1)^2")); 37             Assert.AreEqual("x^3-3x^2+3x-1", EdmSolution.Expand("(x-1)^3")); 38             Assert.AreEqual("x^4-4x^3+6x^2-4x+1", EdmSolution.Expand("(x-1)^4")); 39             Assert.AreEqual("x^5-5x^4+10x^3-10x^2+5x-1", EdmSolution.Expand("(x-1)^5")); 40             Assert.AreEqual("1", EdmSolution.Expand("(x-2)^0")); 41             Assert.AreEqual("x-2", EdmSolution.Expand("(x-2)^1")); 42             Assert.AreEqual("x^2-4x+4", EdmSolution.Expand("(x-2)^2")); 43             Assert.AreEqual("x^3-6x^2+12x-8", EdmSolution.Expand("(x-2)^3")); 44             Assert.AreEqual("x^4-8x^3+24x^2-32x+16", EdmSolution.Expand("(x-2)^4")); 45             Assert.AreEqual("x^5-10x^4+40x^3-80x^2+80x-32", EdmSolution.Expand("(x-2)^5")); 46             Assert.AreEqual("t^5-10t^4+40t^3-80t^2+80t-32", EdmSolution.Expand("(t-2)^5")); 47             Assert.AreEqual("y^15-75y^14+2625y^13-56875y^12+853125y^11-9384375y^10+78203125y^9-502734375y^8+2513671875y^7-9775390625y^6+29326171875y^5-66650390625y^4+111083984375y^3-128173828125y^2+91552734375y-30517578125", EdmSolution.Expand("(y-5)^15")); 48         } 49  50         [Test] 51         public void testAPositive() 52         { 53             Assert.AreEqual("625m^4+1500m^3+1350m^2+540m+81", EdmSolution.Expand("(5m+3)^4")); 54             Assert.AreEqual("8x^3-36x^2+54x-27", EdmSolution.Expand("(2x-3)^3")); 55             Assert.AreEqual("1", EdmSolution.Expand("(7x-7)^0")); 56             Assert.AreEqual("35831808a^7+20901888a^6+5225472a^5+725760a^4+60480a^3+3024a^2+84a+1", EdmSolution.Expand("(12a+1)^7")); 57             Assert.AreEqual("184528125x^5-123018750x^4+32805000x^3-4374000x^2+291600x-7776", EdmSolution.Expand("(45x-6)^5")); 58             Assert.AreEqual("12c+1", EdmSolution.Expand("(12c+1)^1")); 59             Assert.AreEqual("100000000x^4-4000000x^3+60000x^2-400x+1", EdmSolution.Expand("(100x-1)^4")); 60             Assert.AreEqual("1000x^3+2400x^2+1920x+512", EdmSolution.Expand("(10x+8)^3")); 61             Assert.AreEqual("128x^7-448x^6+672x^5-560x^4+280x^3-84x^2+14x-1", EdmSolution.Expand("(2x-1)^7")); 62             Assert.AreEqual("81t^2", EdmSolution.Expand("(9t-0)^2")); 63         } 64  65         [Test] 66         public void testANegative() 67         { 68             Assert.AreEqual("625m^4-1500m^3+1350m^2-540m+81", EdmSolution.Expand("(-5m+3)^4")); 69             Assert.AreEqual("-8k^3-36k^2-54k-27", EdmSolution.Expand("(-2k-3)^3")); 70             Assert.AreEqual("1", EdmSolution.Expand("(-7x-7)^0")); 71             Assert.AreEqual("-35831808a^7+20901888a^6-5225472a^5+725760a^4-60480a^3+3024a^2-84a+1", EdmSolution.Expand("(-12a+1)^7")); 72             Assert.AreEqual("-184528125k^5-123018750k^4-32805000k^3-4374000k^2-291600k-7776", EdmSolution.Expand("(-45k-6)^5")); 73             Assert.AreEqual("-12c+1", EdmSolution.Expand("(-12c+1)^1")); 74             Assert.AreEqual("100000000x^4+4000000x^3+60000x^2+400x+1", EdmSolution.Expand("(-100x-1)^4")); 75             Assert.AreEqual("-1000x^3+2400x^2-1920x+512", EdmSolution.Expand("(-10x+8)^3")); 76             Assert.AreEqual("-128w^7-448w^6-672w^5-560w^4-280w^3-84w^2-14w-1", EdmSolution.Expand("(-2w-1)^7")); 77             Assert.AreEqual("-n^5-60n^4-1440n^3-17280n^2-103680n-248832", EdmSolution.Expand("(-n-12)^5"));//extra static test added by docgunthrop 78             Assert.AreEqual("-k^7+28k^6-336k^5+2240k^4-8960k^3+21504k^2-28672k+16384", EdmSolution.Expand("(-k+4)^7"));//extra static test added by docgunthrop 79             Assert.AreEqual("81t^2", EdmSolution.Expand("(-9t-0)^2")); 80         } 81  82         private static readonly Random rand = new Random(); 83         private static int rands(int limit) 84         { 85             return rand.Next(2 * limit + 2) - limit; 86         } 87  88         private static string makeTestCase(int c, int n, int p) 89         { 90             int coeff = 0; 91             while (coeff == 0) 92                 coeff = rands(c); 93             return string.Format("({0}{1}{2:+0;-#})^{3}", coeff == 1 ? "" : (coeff == -1 ? "-" : "" + coeff), (char)('a' + rand.Next(26)), rands(n), rand.Next(p) + 2); 94         } 95  96         [Test] 97         public void testRandom() 98         { 99 100             for (int i = 0; i < 50; ++i)101             {102                 string eq = makeTestCase(16, 32, 4);103                 Assert.AreEqual(ReferenceSolution.Expand(eq), EdmSolution.Expand(eq), "Input: " + eq);104             }105 106             for (int i = 0; i < 100; ++i)107             {108                 string eq = makeTestCase(9, 16, 9);109                 Assert.AreEqual(ReferenceSolution.Expand(eq), EdmSolution.Expand(eq), "Input: " + eq);110             }111         }112 113         #region Reference solution114         private class ReferenceSolution115         {116 117             private static readonly Regex re = new Regex(@"\((-?\d*)([a-z])([\+\-]\d+)\)\^(\d+)");118 119             public static string Expand(string expr)120             {121 122                 Match m = re.Match(expr);123 124                 string sa = m.Groups[1].Value;125                 int a = ("".Equals(sa) ? 1 : ("-".Equals(sa) ? -1 : int.Parse(sa)));126 127                 string x = m.Groups[2].Value;128 129                 string sb = m.Groups[3].Value;130                 int b = "".Equals(sb) ? 0 : int.Parse(sb);131 132                 string se = m.Groups[4].Value;133                 int exp = "".Equals(se) ? 1 : int.Parse(se);134                 if (exp == 0)135                     return "1";136 137                 if (exp == 1)138                     return sa + x + sb;139 140                 if (b == 0)141                 {142                     long coeff = (long)Math.Pow(a, exp);143                     return (coeff == 1 ? "" : (coeff == -1 ? "-" : coeff.ToString())) + x + "^" + exp;144                 }145 146                 List binoms = new List();147                 for (int i = 0; i = 0; --i)153                 {154 155                     long coeff = coeff1 * binoms;156 157                     if (i != exp && coeff > 0)158                         terms.Append('+');159 160                     if (coeff < 0)161                         terms.Append('-');162 163                     if ((coeff != 1 && coeff != -1) || i == 0)164                         terms.Append(coeff > 0 ? coeff : -coeff);165 166                     if (i > 0)167                         terms.Append(x);168 169                     if (i > 1)170                         terms.Append("^" + i);171 172                     coeff1 = coeff1 / a * b;173                 }174 175                 return terms.ToString();176             }177 178             private static readonly List nka = new List();179 180             private static long nk(int n, int k)181             {182 183                 if (n == 0 || k == 0)184                     return 1;185 186                 if (k == 1)187                     return n;188 189                 if (n - k < k)190                     return nk(n, n - k);191 192                 for (int i = nka.Count; i