大衞的筆記

你來幫幫 ICPC 的忙，ICPC 會給你一組數列，與一個數字 k，請你告訴 ICPC 要在這數列中至少要插入幾個數字才可以成為迴文數列，如果插入的次數大於 k 輸出 too difficult，如果不需要插入輸出 too easy，除此之外，輸出你插入的次數。

題目連結

此筆記用途在於台北科技大學資訊與財金管理系大二下管理作業系統作業紀錄
並非所有人都適用，此為老師所給予的題目。
這是個人心得的筆記，可能不太適用會未來的學生

（請閱讀 W16_少林旅行社—標錯價格事件）

此筆記僅記錄大衛如何使用 google docs 中的建立程式碼，來寫成一份外掛程式。
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是學習後心得的筆記，可能不太適用會未來的學生，或是版本更新就不適用

由於我並不是 google app script 大神，可能有些地方沒有寫得很棒，還請多包涵。

此筆記僅記錄大衛如何使用 google docs 中的建立程式碼，來寫成一份外掛程式。
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是學習後心得的筆記，可能不太適用會未來的學生，或是版本更新就不適用

由於我並不是 google app script 大神，可能有些地方沒有寫得很棒，還請多包涵。

Nastia 有一個數列，但我們並不知道數列裡面的數值，我們現在必須知道這些數值是甚麼，其中我們得知數列裡面的數值，是 1 ~ 數列長度。

我們可以像 Nastia 進行詢問，但 Nastia 不接受普通的詢問方式，她接受的詢問方式如下

• \(t=1 : max(min(x,p_i), min(x+1, p_j)) \)
• \(t=2 : mim(max(x,p_i), max(x+1, p_j)) \)
• 其中 \(t\) 為我們選擇哪種查詢公式，\(p_i,p_j\) 則是數列的 index 當下數值，\(x\) 則是我們任意給的值，但 \(x\) 必須是數列中的數字。
• \(t=1\) or \(t=2, 1 \leq i,j \leq n, i != j, 1 \leq x \leq n-1\)，一定要符合這些條件。

我們可以對 Nastia 最多查詢 \( \frac{3*n}{2} + 30 \)，必須在這些次數前確認出所有的數列。

如果已經確定數列，那輸出格式為 ! a b c，其中 a,b,c 為數列的數字， index 從 1 開始。

題目連結

主要是透過費氏數列所組成的費氏二元樹來對數列進行搜尋，主要的搜尋方式與二元搜尋大概相同，不同之處在於費氏二元樹與二分搜尋的二元樹構造不同。

費氏二元樹在往左右子樹時，只需要使用加減法，不使用乘或除法。
有些 CPU 在乘除法的運算來的過大。

費氏二元樹，我們透過此圖進行理解

• 有一個數列長度有 33，裡面的數字從 1~33，
• 我們必須先建立一顆費氏二元樹，我們先透過費氏數列找出 \(f(n) >= 33\)，其中 \(n = 8\)
• \(fib(8) = 35\)，其實我們可以發現 \(fib(8) = fib(7) + fib(6) \)，其實可以看的出來一些端倪，\(root = 左子樹、右子樹\)，因此 \(fib(8)\) 就是這邊的 root、\(fib(7)\) 是左子樹、\(fib(6)\) 是右子樹
• 左子樹的樹值一定比 root 小，右子樹的數值一定比 root 大
• 其實費氏樹與二元樹相同，只是二元樹是左右子樹的葉節點一樣大，而費氏樹的左子樹葉節點數量有 \(fib(n-1)\)、費氏樹的右子樹葉節點數量有 \(fib(n-2)\)。
• 再來我們就是不斷地用加減法來算出下個子樹的 index。
• 需要記住費氏數列的 index 從 0 開始。
  
  [search] fibonacci search by Chris Yang 學習筆記，如果作者不願意圖片供我引用，請告訴我，我會馬上刪除，讓你感到不舒服我很抱歉QQ

定義 value: 為我們要查詢的樹值
那我們主要就是從 root 開始找

• 如果 root == value，退出 search
• 如果 value > root 往右子樹找
• 如果 value < root 往左子樹找

此筆記用途在於台北科技大學資訊工程系大二下多媒體技術與應用作業紀錄
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是學習後心得的筆記，可能不太適用會未來的學生

由於我沒有學習過裡面的理論，因此這是資工大二學生透過網路與自身理解的筆記，學習價值並不高、且可能擁有大量錯誤。

插值搜尋主要用在於資料量大，且資料離散程度大致相同的數列。

其概念與二分搜尋 by 大衞的筆記 概念大致相同，只有對於 mid 並不同。

二分搜尋再分成左右子樹時，是切半分配。
插值搜尋則是透過斜率公式去進行優化。

其主要插值法的選擇原理如下
value 是我們要查詢的值，那 \(x_1, x_2\) 則是我們現在進行搜尋的區間，因為我們要搜尋的數列是已經排序好的數列，那我們假設區間的資料都是相同離散分布，因此理論上我們可以透過斜率來猜測我們的 value 應該位於 m 處(數列 index)。
也就是我們透過 \(m = \frac{(value - y_1)(x_2 - x_1)}{(y_2 - y_1)} + x_1\)。

此筆記用途在於台北科技大學資訊工程系大二下多媒體技術與應用作業紀錄
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是學習後心得的筆記，可能不太適用會未來的學生

由於我沒有學習過裡面的理論，因此這是資工大二學生透過網路與自身理解的筆記，學習價值並不高、且可能擁有大量錯誤。

訓練的資料是從 FinMind Api 取得，謝謝他們的無私奉獻，讓我們可以輕鬆讀取資料。

堆積排序是透過最大堆積樹來進行排序，其實作與原理如下
主要核心是要讓 root 大於左右子樹，由於我們每次都能夠找出 root，且必定大於左右子樹，因此我們只需要將 root 提出來，再讓左右子樹中的最大值替補 root，依序遞迴擊可。

• 我們用一維陣列來表達我們的二元樹
• 其中 index 0 一定是二元樹中最大的數字
• 透過遞迴，參數： i
  • 以當前 i 節點為 root，L、R 分別是左右子樹
  • 如果左子樹數值比 i 數值還要大，那就讓 i 與左子樹交換
  • 如果右子樹數值比 i 數值還要大，那就讓 i 與右子樹交換
  • 如果先前有進行交換的動作，那我們就讓與 i 交換的子樹再重新進行遞迴

我們主要是維護二元堆積樹的 root 最大，如果 root 與其他數值有做交換，那我們必須讓 root 往下至其適合的位置，適合的位置：左右子樹都沒有比他還大，root 本身比左右子樹更大

時間複查度為 \(O(n log n)\)，在某些演算法中會用到堆積排序，因此算是篇重要的排序演算法之一。