【資料結構與算法】數組應用4：多項式計算Java版

    這裡讨論的是多項的加法，直接看下面的程式代碼：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

<code>package</code> <code>chapter02;</code>

<code>import</code> <code>java.util.Arrays;</code>

<code>/*</code>

<code> </code><code>* 多項式加法（簡單版）</code>

<code> </code><code>* A(x) = 2x^5 + 3x^4 + 0x^3 + 5x^2 + 4x^1 +1x^0</code>

<code> </code><code>* B(x) =        3x^4 + 2x^3 + 1x^2 + 1x^1 + 2x^0</code>

<code> </code><code>* </code>

<code> </code><code>* A(x) + B(x) = </code>

<code> </code><code>* C(x) = 2x^5 + 6x^5 + 2x^3 + 6x^2 + 5x^1 + 3x^0</code>

<code> </code><code>* 采用一維數組儲存，第一個元素儲存多項式的最高次幂，後面依次儲存每項的次數</code>

<code> </code><code>* A(x) = [5, 2, 3, 0, 5, 4, 1]</code>

<code> </code><code>* B(x) = [3,    2, 1, 1, 2, 2]</code>

<code> </code><code>* A(x) + B(x) =</code>

<code> </code><code>* C(x) = [5, 2, 5, 1, 6, 6, 3]</code>

<code> </code><code>*/</code>

<code>public</code> <code>class</code> <code>CH02_08 {</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) {</code>

<code>        </code><code>//定義兩個多項式的數組</code>

<code>        </code><code>int</code><code>[] arr1 = {</code><code>5</code><code>, </code><code>2</code><code>, </code><code>3</code><code>, </code><code>0</code><code>, </code><code>5</code><code>, </code><code>4</code><code>, </code><code>1</code><code>};</code>

<code>        </code><code>int</code><code>[] arr2 = {</code><code>3</code><code>,    </code><code>2</code><code>, </code><code>1</code><code>, </code><code>1</code><code>, </code><code>2</code><code>, </code><code>2</code><code>};</code>

<code>        </code> 

<code>        </code><code>//輸出兩個多項式數組</code>

<code>        </code><code>System.out.println(Arrays.toString(arr1));</code>

<code>        </code><code>System.out.println(Arrays.toString(arr2));</code>

<code>        </code><code>//定義結果多項式的數組</code>

<code>        </code><code>int</code> <code>arrResultLen = arr1.length &gt; arr2.length ? arr1.length:arr2.length;   </code><code>//數組長度為擁有較多項的多項式的數組的長度</code>

<code>        </code><code>int</code><code>[] arrResult = </code><code>new</code> <code>int</code><code>[arrResultLen];</code>

<code>        </code><code>//初始化arrResult</code>

<code>        </code><code>Arrays.fill(arrResult, </code><code>0</code><code>);</code>

<code>        </code><code>//輸出arrResult</code>

<code>        </code><code>System.out.println();</code>

<code>        </code><code>System.out.println(Arrays.toString(arrResult));</code>

<code>        </code><code>//開始計算多項式的加法</code>

<code>        </code><code>int</code><code>[] bigArr = arr1.length == arrResultLen ? arr1:arr2;      </code><code>//找出項較多的多項式數組</code>

<code>        </code><code>int</code><code>[] smallArr = arr1.length == arrResultLen ? arr2:arr1;    </code><code>//找出項較少的多項式數組</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>bigLen = bigArr.length - </code><code>1</code><code>, smallLen = smallArr.length - </code><code>1</code><code>; bigLen &gt;= </code><code>0</code><code>; bigLen--, smallLen--){</code>

<code>            </code><code>//逆序數組進行計算，這樣就可以實作項的幂一一對應</code>

<code>            </code><code>if</code><code>(smallLen &gt; </code><code>0</code><code>){</code>

<code>                </code><code>//小的多項式數組的第0項隻是表示最高次幂，對實際計算沒有用處，這裡隻計算小的多項式數組第0項之後的值</code>

<code>                </code><code>arrResult[bigLen] = bigArr[bigLen] + smallArr[smallLen];</code>

<code>            </code><code>} </code><code>else</code> <code>{</code>

<code>                </code><code>//再往前走，如果smallArr已經到達了第0項，則隻把bigArr中相應的值直接儲存到arrResult中</code>

<code>                </code><code>arrResult[bigLen] = bigArr[bigLen];</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>//輸出結果多項式的數組</code>

<code>    </code><code>}</code>

<code>}</code>

    執行結果如下：

<code>[5, 2, 3, 0, 5, 4, 1]</code>

<code>[3, 2, 1, 1, 2, 2]</code>

<code>[0, 0, 0, 0, 0, 0, 0]</code>

<code>[5, 2, 5, 1, 6, 6, 3]</code>

<code></code>

本文轉自 xpleaf 51CTO部落格，原文連結：http://blog.51cto.com/xpleaf/1976984，如需轉載請自行聯系原作者