Category Archives: Program

[DataStructure]Towers of Hanoi(河內塔)

河內塔是一個數學遊戲:有三個塔柱A、B、C,遊戲的目的就是將A塔柱的圓盤全數移到C塔柱

遊戲有幾個規則: 1. 一次只能搬移一個圓盤 2. 小圓盤可以移到大圓盤上面,大圓盤不可以移到小圓盤上面。

事實上,可以從河內塔移動次數中,發現這是有遞迴規則的。 以最小的圓盤 n 為例: 當圓盤總數為 1 時, n 移動了 1 次 當圓盤總數為 2 時, n 移動了 2 次 當圓盤總數為 3 時, n 移動了 4 次 當圓盤總數為 4 時, n 移動了 8 次

為了要讓大盤可以移出來到目的柱,當盤數越多,其他較小圓盤就必須先移到暫存柱(三柱其中一柱) 若有n個盤子,則移動完畢所需的次數為2^n – 1

Java

Continue Reading

[Java]Scanner next()與nextLine()無法同時使用問題

在Scanner中,有next()與nextLine()兩種方法 next()是以空白或換行為區格,nextLine()則是以換行為區格讀取整行

當一起使用時,會出現遇到nextLine()無法正常運作的問題 如以下程式碼

會這樣子的原因是因為next()是抓取空白或\n換行字元以前的字串,所以next()抓完字串之後\n就被nextLine()抓住了,因此nextLine()只有抓到\n而已,沒有抓到應該抓的字串。

解決方法就是不斷讓nextLine()重複抓取,直到抓到有字串為止:

Continue Reading

[DataStructure]Insertion Sort(插入排序法)

插入排序法的步驟就是把後面的牌抽到前面適當的位置插入

以{123456,123,12,33,44,55}為例

將123插入到最前面 [123 123456] 12 33 44 55 將12插入到最前面 [12 123 123456] 33 44 55 將33插入到12跟123之間 [12 33 123 123456] 44 55 將44插入到33跟123之間 [12 33 44 123 123456] 55 將55插入到44跟123之間 [12 33 44 55 123 123456]

Java

Continue Reading

[Java]LinkedList

List是以物件加入的順序來排序,如果單純用來讀取,建議使用ArrayList,如果大量做插入、刪除等動作,用LinkedList會比ArrayList好上很多

Continue Reading

[Java]HashSet

HashSet是實作Set介面的物件,Set容器中的物件都是唯一的

HashSet

這段程式會顯示出:李四 王五 張三。 其中張三輸入了兩次,所以第二次輸入張三時,會判定已有這個物件 至於順序不一樣是因為HashSet的順序是利用Hash Table排序過的,所以會與當初輸入時不一樣

如果要讓set順序與輸入時相同,可以使用LinkedHashSet

他的走訪就會跟LinkedList一樣

Continue Reading

[DataStructure]Selection Sort(選擇排序法)

選擇排序法的複雜度為O(n^2),和氣泡排序法是一樣的

他的步驟是將要排序的數字分為未排序已排序兩部份

接著在未排序找出最小值插入已排序的末端

以{123456,123,12,33,44,55}為例

未排序 123456 123 12 33 44 55 找到最小值12,並與第一筆123456交換(12是已排序的數字了) [12] 123 123456 33 44 55 找到最小值33,並與第一筆123交換 [12 33] 123456 123 44 55 找到最小值44,並與第一筆123456交換 [12 33 44] 123 123456 55 找到最小值55,並與第一筆123交換 [12 33 44 55] 123456 123 找到最小值123,並與第一筆123456交換 [12 33 44 55 123] 123456 完成 [12 33 44 55 123 123456]

Java

Continue Reading

[DataStructure]Bubble Sort(氣泡排序法)

這是資料結構第一個學到的排序法,

雖簡單但因為複雜度太高效率非常不好(Ο(n^2)),通常實作中都不採用這種排序法

不過對於初學者學習排序的概念非常有幫助

氣泡排序法的概念很容易,分為幾個步驟

1.比較相鄰的元素。如果第一個比第二個大,就交換。 2.對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對(這時候最後一個數應該會是最大) 3.重複以上動作(不包含最後一個數)

Java:

Continue Reading

[DataStructure]Quick Sort(快速排序法)

目前公認最快的排序法,雖然最壞的時候還是會衝到O(n^2),不過大部份還是很快的(Quick Sort的速度與基準點的選擇有關)

Quick Sort分為幾個步驟 以{41,24,76,11,45,64,21,69,19,36}這個陣列為例

1.先將最左邊的數41當成基準點(s) 2.索引 I 由左邊向右找,一直找到大於基準點(s)的數 3.索引 J 由右邊向左找,一直找到小於基準點(s)的數 4.如果 I >= J 就跳出迴圈。如果 I < J,array[I]和array[J]交換 6.基準點與array[J]交換,這時 J 因為第3步驟的關係,會一直找到小於基準點的數(這時 I 已 >= J,雖迴圈跳出了,但 J 的值還在) 7.對基準點左邊及右邊進行相同步驟的遞迴

I 找到比基準點大的、J 找到比基準點小的 [41],24,76(I),11,45,64,21,69,19,36(J) I、J交換,繼續往下找 [41],24,36,11,45(I),64,21,69,19(J),76 I、J交換,繼續往下找 [41],24,36,11,19,64(I),21(J),69,45,76 I、J交換且繼續往下找,但是 I >= J 所以會break,這時 J 停留在21 [41],24,36,11,19,21(J),64,69,45,76 基準點與 J 交換 21,24,36,11,19,[41],64,69,45,76 最後再以基準點左右兩邊做相同遞迴

Java

Continue Reading

[Java]BigInteger

在寫程式時,最怕碰到數字超過現有型態的大小,且又要做運算….

Java提供了一個BigInteger物件解除大數的煩腦

Continue Reading