经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C# » 查看文章
【算法】湖心岛上的数学梦--用c#实现一元多次方程的展开式
来源:cnblogs  作者:lanedm  时间:2023/9/11 8:51:35  对本文有异议

每天清晨,当第一缕阳光洒在湖面上,一个身影便会出现在湖心小岛上。她坐在一块大石头上,周围被茂盛的植物环绕,安静地沉浸在数学的世界中。

这个姑娘叫小悦,她的故事在这个美丽的湖心小岛上展开。每天早晨,她都会提前来到湖边,仔细观察水下的植物,然后抽出时间来钻研一元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. 断言结果与期望值相等,测试通过


测试用例:

  1. 1 namespace Solution
  2. 2 {
  3. 3 using NUnit.Framework;
  4. 4 using System;
  5. 5 using System.Collections.Generic;
  6. 6 using System.Text;
  7. 7 using System.Text.RegularExpressions;
  8. 8
  9. 9 [TestFixture]
  10. 10 public class SolutionTest
  11. 11 {
  12. 12 [Test]
  13. 13 public void testBPositive()
  14. 14 {
  15. 15 Assert.AreEqual("1", EdmSolution.Expand("(x+1)^0"));
  16. 16 Assert.AreEqual("x+1", EdmSolution.Expand("(x+1)^1"));
  17. 17 Assert.AreEqual("x^2+2x+1", EdmSolution.Expand("(x+1)^2"));
  18. 18 Assert.AreEqual("x^3+3x^2+3x+1", EdmSolution.Expand("(x+1)^3"));
  19. 19 Assert.AreEqual("x^4+4x^3+6x^2+4x+1", EdmSolution.Expand("(x+1)^4"));
  20. 20 Assert.AreEqual("x^5+5x^4+10x^3+10x^2+5x+1", EdmSolution.Expand("(x+1)^5"));
  21. 21 Assert.AreEqual("1", EdmSolution.Expand("(x+2)^0"));
  22. 22 Assert.AreEqual("x+2", EdmSolution.Expand("(x+2)^1"));
  23. 23 Assert.AreEqual("x^2+4x+4", EdmSolution.Expand("(x+2)^2"));
  24. 24 Assert.AreEqual("x^3+6x^2+12x+8", EdmSolution.Expand("(x+2)^3"));
  25. 25 Assert.AreEqual("x^4+8x^3+24x^2+32x+16", EdmSolution.Expand("(x+2)^4"));
  26. 26 Assert.AreEqual("x^5+10x^4+40x^3+80x^2+80x+32", EdmSolution.Expand("(x+2)^5"));
  27. 27 Assert.AreEqual("t^5+10t^4+40t^3+80t^2+80t+32", EdmSolution.Expand("(t+2)^5"));
  28. 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. 29 }
  30. 30
  31. 31 [Test]
  32. 32 public void testBNegative()
  33. 33 {
  34. 34 Assert.AreEqual("1", EdmSolution.Expand("(x-1)^0"));
  35. 35 Assert.AreEqual("x-1", EdmSolution.Expand("(x-1)^1"));
  36. 36 Assert.AreEqual("x^2-2x+1", EdmSolution.Expand("(x-1)^2"));
  37. 37 Assert.AreEqual("x^3-3x^2+3x-1", EdmSolution.Expand("(x-1)^3"));
  38. 38 Assert.AreEqual("x^4-4x^3+6x^2-4x+1", EdmSolution.Expand("(x-1)^4"));
  39. 39 Assert.AreEqual("x^5-5x^4+10x^3-10x^2+5x-1", EdmSolution.Expand("(x-1)^5"));
  40. 40 Assert.AreEqual("1", EdmSolution.Expand("(x-2)^0"));
  41. 41 Assert.AreEqual("x-2", EdmSolution.Expand("(x-2)^1"));
  42. 42 Assert.AreEqual("x^2-4x+4", EdmSolution.Expand("(x-2)^2"));
  43. 43 Assert.AreEqual("x^3-6x^2+12x-8", EdmSolution.Expand("(x-2)^3"));
  44. 44 Assert.AreEqual("x^4-8x^3+24x^2-32x+16", EdmSolution.Expand("(x-2)^4"));
  45. 45 Assert.AreEqual("x^5-10x^4+40x^3-80x^2+80x-32", EdmSolution.Expand("(x-2)^5"));
  46. 46 Assert.AreEqual("t^5-10t^4+40t^3-80t^2+80t-32", EdmSolution.Expand("(t-2)^5"));
  47. 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. 48 }
  49. 49
  50. 50 [Test]
  51. 51 public void testAPositive()
  52. 52 {
  53. 53 Assert.AreEqual("625m^4+1500m^3+1350m^2+540m+81", EdmSolution.Expand("(5m+3)^4"));
  54. 54 Assert.AreEqual("8x^3-36x^2+54x-27", EdmSolution.Expand("(2x-3)^3"));
  55. 55 Assert.AreEqual("1", EdmSolution.Expand("(7x-7)^0"));
  56. 56 Assert.AreEqual("35831808a^7+20901888a^6+5225472a^5+725760a^4+60480a^3+3024a^2+84a+1", EdmSolution.Expand("(12a+1)^7"));
  57. 57 Assert.AreEqual("184528125x^5-123018750x^4+32805000x^3-4374000x^2+291600x-7776", EdmSolution.Expand("(45x-6)^5"));
  58. 58 Assert.AreEqual("12c+1", EdmSolution.Expand("(12c+1)^1"));
  59. 59 Assert.AreEqual("100000000x^4-4000000x^3+60000x^2-400x+1", EdmSolution.Expand("(100x-1)^4"));
  60. 60 Assert.AreEqual("1000x^3+2400x^2+1920x+512", EdmSolution.Expand("(10x+8)^3"));
  61. 61 Assert.AreEqual("128x^7-448x^6+672x^5-560x^4+280x^3-84x^2+14x-1", EdmSolution.Expand("(2x-1)^7"));
  62. 62 Assert.AreEqual("81t^2", EdmSolution.Expand("(9t-0)^2"));
  63. 63 }
  64. 64
  65. 65 [Test]
  66. 66 public void testANegative()
  67. 67 {
  68. 68 Assert.AreEqual("625m^4-1500m^3+1350m^2-540m+81", EdmSolution.Expand("(-5m+3)^4"));
  69. 69 Assert.AreEqual("-8k^3-36k^2-54k-27", EdmSolution.Expand("(-2k-3)^3"));
  70. 70 Assert.AreEqual("1", EdmSolution.Expand("(-7x-7)^0"));
  71. 71 Assert.AreEqual("-35831808a^7+20901888a^6-5225472a^5+725760a^4-60480a^3+3024a^2-84a+1", EdmSolution.Expand("(-12a+1)^7"));
  72. 72 Assert.AreEqual("-184528125k^5-123018750k^4-32805000k^3-4374000k^2-291600k-7776", EdmSolution.Expand("(-45k-6)^5"));
  73. 73 Assert.AreEqual("-12c+1", EdmSolution.Expand("(-12c+1)^1"));
  74. 74 Assert.AreEqual("100000000x^4+4000000x^3+60000x^2+400x+1", EdmSolution.Expand("(-100x-1)^4"));
  75. 75 Assert.AreEqual("-1000x^3+2400x^2-1920x+512", EdmSolution.Expand("(-10x+8)^3"));
  76. 76 Assert.AreEqual("-128w^7-448w^6-672w^5-560w^4-280w^3-84w^2-14w-1", EdmSolution.Expand("(-2w-1)^7"));
  77. 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. 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. 79 Assert.AreEqual("81t^2", EdmSolution.Expand("(-9t-0)^2"));
  80. 80 }
  81. 81
  82. 82 private static readonly Random rand = new Random();
  83. 83 private static int rands(int limit)
  84. 84 {
  85. 85 return rand.Next(2 * limit + 2) - limit;
  86. 86 }
  87. 87
  88. 88 private static string makeTestCase(int c, int n, int p)
  89. 89 {
  90. 90 int coeff = 0;
  91. 91 while (coeff == 0)
  92. 92 coeff = rands(c);
  93. 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. 94 }
  95. 95
  96. 96 [Test]
  97. 97 public void testRandom()
  98. 98 {
  99. 99
  100. 100 for (int i = 0; i < 50; ++i)
  101. 101 {
  102. 102 string eq = makeTestCase(16, 32, 4);
  103. 103 Assert.AreEqual(ReferenceSolution.Expand(eq), EdmSolution.Expand(eq), "Input: " + eq);
  104. 104 }
  105. 105
  106. 106 for (int i = 0; i < 100; ++i)
  107. 107 {
  108. 108 string eq = makeTestCase(9, 16, 9);
  109. 109 Assert.AreEqual(ReferenceSolution.Expand(eq), EdmSolution.Expand(eq), "Input: " + eq);
  110. 110 }
  111. 111 }
  112. 112
  113. 113 #region Reference solution
  114. 114 private class ReferenceSolution
  115. 115 {
  116. 116
  117. 117 private static readonly Regex re = new Regex(@"\((-?\d*)([a-z])([\+\-]\d+)\)\^(\d+)");
  118. 118
  119. 119 public static string Expand(string expr)
  120. 120 {
  121. 121
  122. 122 Match m = re.Match(expr);
  123. 123
  124. 124 string sa = m.Groups[1].Value;
  125. 125 int a = ("".Equals(sa) ? 1 : ("-".Equals(sa) ? -1 : int.Parse(sa)));
  126. 126
  127. 127 string x = m.Groups[2].Value;
  128. 128
  129. 129 string sb = m.Groups[3].Value;
  130. 130 int b = "".Equals(sb) ? 0 : int.Parse(sb);
  131. 131
  132. 132 string se = m.Groups[4].Value;
  133. 133 int exp = "".Equals(se) ? 1 : int.Parse(se);
  134. 134 if (exp == 0)
  135. 135 return "1";
  136. 136
  137. 137 if (exp == 1)
  138. 138 return sa + x + sb;
  139. 139
  140. 140 if (b == 0)
  141. 141 {
  142. 142 long coeff = (long)Math.Pow(a, exp);
  143. 143 return (coeff == 1 ? "" : (coeff == -1 ? "-" : coeff.ToString())) + x + "^" + exp;
  144. 144 }
  145. 145
  146. 146 List<long> binoms = new List<long>();
  147. 147 for (int i = 0; i <= exp; ++i)
  148. 148 binoms.Add(nk(exp, i));
  149. 149
  150. 150 long coeff1 = (long)Math.Pow(a, exp);
  151. 151 StringBuilder terms = new StringBuilder();
  152. 152 for (int i = exp; i >= 0; --i)
  153. 153 {
  154. 154
  155. 155 long coeff = coeff1 * binoms[i];
  156. 156
  157. 157 if (i != exp && coeff > 0)
  158. 158 terms.Append('+');
  159. 159
  160. 160 if (coeff < 0)
  161. 161 terms.Append('-');
  162. 162
  163. 163 if ((coeff != 1 && coeff != -1) || i == 0)
  164. 164 terms.Append(coeff > 0 ? coeff : -coeff);
  165. 165
  166. 166 if (i > 0)
  167. 167 terms.Append(x);
  168. 168
  169. 169 if (i > 1)
  170. 170 terms.Append("^" + i);
  171. 171
  172. 172 coeff1 = coeff1 / a * b;
  173. 173 }
  174. 174
  175. 175 return terms.ToString();
  176. 176 }
  177. 177
  178. 178 private static readonly List<List<long>> nka = new List<List<long>>();
  179. 179
  180. 180 private static long nk(int n, int k)
  181. 181 {
  182. 182
  183. 183 if (n == 0 || k == 0)
  184. 184 return 1;
  185. 185
  186. 186 if (k == 1)
  187. 187 return n;
  188. 188
  189. 189 if (n - k < k)
  190. 190 return nk(n, n - k);
  191. 191
  192. 192 for (int i = nka.Count; i <= n; ++i)
  193. 193 nka.Add(new List<long>());
  194. 194
  195. 195 List<long> ns = nka[n];
  196. 196 for (int i = ns.Count; i <= k; ++i)
  197. 197 ns.Add(0L);
  198. 198
  199. 199 if (ns[k] != 0)
  200. 200 return ns[k];
  201. 201 else
  202. 202 {
  203. 203 long b = nk(n - 1, k - 1) + nk(n - 1, k);
  204. 204 ns[k] = b;
  205. 205 return b;
  206. 206 }
  207. 207 }
  208. 208 }
  209. 209 #endregion
  210. 210 }
  211. 211 }

 

原文链接:https://www.cnblogs.com/lan80/p/17691306.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号