小菜一碟

  前言 耶呼~~~ 終於 30 天了！喔耶！因為參加鐵人賽瘦了 2 公斤，因為寫文章實在太燒腦啦XDDD，一起來看看我的心得感想吧 心得 首先，非常謝謝 iT 邦幫忙鐵人賽，透過這 30 天，讓我好好的嗑了我念書時期的書跟筆記本(差點消化不良)，從過程中了解到自己其實還有許多不懂的地方，需要好好認真面對，學會專業的內容之後，再進一步的內化並用自己的話說出來，透過舉例子(想謎題跟例子真的是想破頭XD)，分享的動作加深自己的印象，透過 30 天的學習，真的明顯感受到自己的進步，非常開心，也謝謝大家的陪伴，如果有任何理解錯誤或不適合的內容請告訴我，讓我有機會改善 XD 再來想跟大家分享資料結構與演算法對我工作上的影響，原本的我早已把大學學過的東西通通還給老師了，等到真的發現自己在撰寫程式遇到瓶頸時，大概是畢業後的第 6 年，因為過程中其實大多是接觸前端畫面的處理，或是後端的資料庫存取，就是資料的呈現與儲存而已，等到開始接觸一些推薦系統或是 LeetCode 才發現我不會寫程式了耶！ 發現自己對於如何將輸入的資料儲存成適合的資料結構會有障礙，因為資料結構會影響到後續程式排序資料或尋找資料的方便性，再來如何讀取特定的資料結構並將資料轉成自己想要呈現的結果，也卡關 XD，就像是二元樹如何使用陣列表示早知忘光，整個不知所以然，只能用慘字形容，只能好好 K 書，發現當年理解的並非真的理解 而演算法的部份更是悲慘到極點，基本排序通通不懂，剛好因為工作內容需要換成其他語言，發現比較底層的語言排序要自己寫耶，如何在一串數字中快速完成排序，又再次卡關，實在是很掉漆，頓時覺得資料結構真的很重要，這個觀念沒有架構好，演算法更是舉步維艱，覺得再這樣下去我可能工作不保，於是有開始念書，但過程中因為自己的拖延症又停擺了，剛好遇到鐵人賽，所以握緊機會參賽，果然滿載而歸 現在面對工作上的需求或是寫 LeetCode 都會先分析需求，再去了解題目的架構，需要搭配哪些資料結構來儲存相關的資料，最後再實作演算法的部分(甚至會有一些混和式的作法)，讓結果符合需求，發現念書之後整個思考方式都改變了，感覺基礎觀念真的非常重要，像是求兩數的最大公因數，可以使用暴力法，也可以使用輾轉相除法，去分析兩者之間的優缺點，雖然說自己還有很多不太了解的部分，但會想繼續努力，去加強這些觀念，對於自己工作上或思考事情上面都...

  前言 對圖形的搜尋有了基本觀念之後，接下來要在圖形的 邊 加入 權重 的部分，這樣就能找到最短路徑 生活常識 你有自己規劃行程的經驗嗎？如果朋友住在 台中 住在想去 花蓮 旅遊，那麼你會怎麼建議行程呢？是建議從南投走橫貫公路，還是從繞到台北宜蘭，還是打開 googe map 直接看哪個路徑比較短，或是花費的時間比較少，由下圖可以看到 google map 推薦 路程時間 最少的(走往台北的路徑)，而不是 距離 最短的路徑(走往南投的路徑) 專業知識 - 戴克斯特拉演算法 Dijkstra's algorithm 戴克斯特拉演算法因為音譯的關係有蠻多種說法的，每一種名字都蠻常的XD，我自己是比較習慣用英文記憶XD，回歸正題，如果僅以 邊 作為挑選路徑的考量，也就是圖形中 A 點到 B 點經過 幾個邊 ，可以使用昨天介紹的廣度或深度演算法，但如果加上 時間 的考量，則廣度搜尋演算法的結果並不一定會等於戴克斯特拉演算法的結果 如下圖，起點為 A 點，目的地為 E 點： 左圖 沒有時間的權重，所以最短路徑會選  ACE ，此路段最少，因為只需要經過2個邊 右圖 加上 時間 的權重，單位為分鐘，ACE 花費時間為 13(9+4) 分鐘，雖然 ABDE 要走 3 個邊但只需要花 10 分鐘，所以走  ABDE  最快 最短路徑 Single-Pair Shortest Path 有一個有向加權圖形 G = ( V, E )， 最短路徑 為圖中兩頂點間的最短路徑，也就是權重加總數值最小者，其中加權的部分，就看個人的考量，也許是時間，或是開車油錢等等 例子 以下圖為例，權重為公里，想要找到  A  到 任一點 最短的路徑，透過戴克斯特拉演算法要如何取得結果，這邊要特別注意，使用戴克斯特拉演算法時，圖形中的權重不能有負數(正負數)，否則演算法的結果可能會有錯誤，須改用其他演算法，像是貝爾曼福特演算法(Bellman-Ford algorithm) 先來看搜尋結果，稍後會有詳細的步驟說明 可由步驟 5 觀察到，A 到任一點的最短距離 A 到 A 的最短距離為 0 A 到 B 的最短距離為 1 A 到 C 的最短距離為 4 A 到 D 的最短距離為 6 A 到 E 的最短距離為 6 步驟說明 ： 尋找與  A ...

  前言 圖形也有搜尋演算法可以使用，例如 深度優先搜尋法 與 廣度深度優先搜尋法 ，一起來看看吧 生活常識 你在超市購物時，都是怎麼選購貨架上的物品？是使用 左右掃射 ，還是 上下掃瞄 呢？哪一種方式可以最快找到你想買的東西呢？ 圖片來源: https://www.pexels.com/zh-tw/photo/1005638/ 你玩過迷宮嗎？這是個很考驗運氣、耐性、智慧與勇氣的遊戲，從 起點 走到 終點 ，會出現很多 路徑 ，面臨多條路徑的 選擇 時，常常會出現選擇障礙，因為如果選錯可能就會 走回頭路 ，你會怎麼決定你的策略呢？ 隨機選一條路之後就勇往直前等遇到死路在做打算， 每個路徑會先去探一小段路之後再做打算 不管是哪一種，都很有可能走得頭昏眼花、四肢不聽使喚，最後還不見得能順利過關XD，不知道你有沒有聽過一種可以快速破解迷宮的方法，叫做 沿牆走 ，不過只適用於某些類型的迷宮，最土法煉鋼的方式就是勇敢嘗試，試到最後面一定會找到出口，只怕時間不夠或是你已經感到心疲力竭先放棄了，那要怎麼 預防迷路 呢？可以學習童話故事中丟 麵包屑 的方式，讓自己清楚知道要注意哪些路徑 圖片來源: https://www.pexels.com/zh-tw/photo/1904204/ 專業知識 圖形說明 如果對於 樹 或 圖形 結構不熟悉的話，可以參考前幾天的文章，圖形是由許多頂點與邊組成的，而 樹也是圖的一種 ，當今天我們在某著頂點，想要到達某個頂點時，會經過某些路徑，而要如何快速找到這兩個頂點之間的相連路徑，就是演算法要做的事情 判斷是否走過 由於目標頂點位於圖形的哪個位置我們並不知道，檢查該頂點是不是我們要尋找的頂點，在搜尋過程中為了清楚知道哪些頂點是已經搜尋過的(就像走迷宮可以丟麵包屑或做記號)，我們必須透過其他的資料結構 堆疊 、 佇列 或是使用 遞迴 演算法來輔助我們記憶已訪問過的頂點或路徑，才不會做重覆性的搜尋 深度優先搜尋法 Depth-first Search 選擇路徑 如果要找 A 走到 G 的路徑，請找一個與 A  相鄰 的點且 沒有走過 的點，重覆以下兩個動作直到找到目標點或所有點都被走過為止 有找到：判斷是否為目標點，如果不是則將此點紀錄為已走過，並以此點為新的點，再繼續往下找與新點相鄰且沒有走過的點，例如， B 與 A 相鄰，B 不是 ...

  前言 今天要來介紹 費式搜尋法 ，老實說我完全沒印象以前老師有教過這個，自己看了兩天才終於看懂，看起來很複雜，事實上真的很複雜XD 生活常識 你有欣賞過花朵嗎？有沒有注意到，有些花的花瓣大多是 3 瓣或 5 瓣，也有 8 瓣或 13 瓣，為什麼會這些數字這麼常出現呢？似乎是大自然的一種法則 圖片來源: https://www.pexels.com/zh-tw/photo/4621593/ 或是某些建築例會呈現 黃金比例 ，其實都是 費氏級數 的呈現 圖片來源: https://unsplash.com/photos/zHDiLstmQwo 專業知識 - 費氏級數 在介紹費式搜尋法之前，先來了解一下 費氏級數 或稱 斐波那契數列 公式 根據公式只會用到加減運算，不需要進行乘法與除法，所以效率會比較好 數列 數列有 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...，除了最前面的兩個數值 0 與 1 之外，其他數值皆為前兩個的相加，例如 8 = 5 + 3 專業知識 - 費式搜尋法 Fibonacci Search 費式搜尋法 又稱 費伯那搜尋法 ，跟內插搜尋法一樣會透過 某個公式 來限縮搜尋範圍，內插搜尋法是透過斜率公式，而費式搜尋法是使用 費式級數 來分割，可參考 維基百科 的說明 費式樹 特性 費氏樹的左右子樹皆為費氏樹 父節點與子節點的 相差值 會等於某一個費氏數值 左節點 的數值會 小於 父節點 右節點 的數值會 大於等於 父節點 二元樹轉費氏樹 先將費氏級數畫成二元樹 會發現左圖的二元樹節點到F(1)就會停止，因為沒有符合 1 小於 2 了，就沒有符合 n 大於等於 2 的公式了，再將數列中的數值逐一帶入二元樹中，觀察右圖即可發現 樹根的數值 = 左右節點相加的數值 資料置放的順序 存入資料數據之前，要先取得資料置放的順序，使用 中序 走訪費氏樹，可觀察到 父節點 與 左右節點 之間有一個固定的 相差值 相差值 公式如下，其相差值為某一個費氏級數 例子 將要搜尋的資料 由小至大 放到 費式樹 中，例如，有一由小到大排列好的數列：2, 5, 17, 26, 38, 42, 59, 60, 65 ,72 ,87, 93，共 12 筆資料 節點數量 我們要如何知道這些數值要 使用多少節點 來儲存呢？可透過以下公式求得...