# Algorithms X DP X Python 視覺化工具
## Algorithms
### Sort Algorithms
#### Bubble sort
way to sort:

def bubble_sort(data):
    for j in range(0, len(data) - 1):
        swapped = False
        for i in range(0, len(data) - 1 - j):
            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]
                swapped = True
        if not swapped:
            break
    return data

# 測試
a=list(map(int,input()))
sorted_list=bubble_sort(a)
print("sorted:",sorted_list)

time complexity:O(n^2)

當你使用氣泡排序時，你的目標是將一個列表中的數字從小到大排列。這就像在一個數字序列中，讓最小的數字「冒泡」到最前面。

這是如何實現的：

外部迴圈： 想像你有一堆數字要排列，你會進行多次迭代。每次迭代，你都會確保至少有一個數字排在了它應該在的位置。這就像你每次都讓最大的數字「浮」到了列表的最後面。

內部迴圈： 每次迭代時，你會一一比較相鄰的兩個數字。如果它們的順序錯了（例如，前面的數字比後面的大），你會把它們交換位置，讓更大的數字「浮」到後面。這樣，每次迭代後，最大的數字就會像氣泡一樣移動到了正確的位置。

簡單來說，外部迴圈確保每次迭代都讓至少一個數字排在正確的位置，而內部迴圈實際上進行了數字的比較和可能的交換，使最大的數字逐漸移到了它應該在的位置。當沒有需要交換的數字時，表示所有的數字都已經排好序，排序過程結束。

那麼我要怎麼知道迴圈的次數呢

在氣泡排序中，外部迴圈的次數可以幫助你確保所有的元素都能夠適當地冒泡到它們應該在的位置。每次外部迴圈的迭代都會將最大的未排序元素移動到正確的位置，所以你需要執行足夠的迭代次數，以確保所有的元素都被處理。

迴圈的次數是根據列表的大小和內部迴圈的邏輯來計算的。在氣泡排序中，通常會使用兩個嵌套的迴圈，如你之前提供的程式碼所示。外部迴圈的次數取決於列表的大小。如果列表中有n個元素，那麼外部迴圈需要執行n-1次迭代，因為在每次迭代後，至少有一個元素會移動到正確的位置，最後一個元素自然會在適當的位置上。

總的來說，迴圈的次數是根據排序演算法的邏輯和迭代的需求來計算的。在氣泡排序中，外部迴圈的次數確保了所有元素都能夠被處理，內部迴圈的邏輯確保了每次迭代能夠移動最大的元素到正確的位置。這樣，通過足夠的迭代次數，你就能夠確保列表中的所有元素都按照正確的順序排列。

那內層迴圈的次數要怎麼知道?

內部迴圈的次數是根據外部迴圈的當前迭代次數和列表的大小來計算的。內部迴圈的目的是進行實際的比較和可能的交換操作，以便將最大的未排序元素推到正確的位置。這裡是如何計算內部迴圈的次數：

假設你有一個列表，總共有n個元素。外部迴圈的迭代次數是n-1，因為在每次迭代後，至少有一個元素會移動到正確的位置。對於外部迴圈的第一次迭代，你需要比較和可能的交換n-1次，因為你需要將最大的元素移動到列表的最後一個位置。

對於外部迴圈的第二次迭代，你只需要比較和可能的交換前n-1-1次，因為最大的兩個元素已經在前一次迭代中被推到了列表的最後兩個位置。

依此類推，對於外部迴圈的第i次迭代，你只需要比較和可能的交換前n-1-i次。

總之，內部迴圈的次數是根據外部迴圈的當前迭代次數來計算的，公式為 len(data) - 1 - j，其中 j 是外部迴圈的迭代次數。這確保了每次迭代只需要處理未排序部分的元素，將最大的元素移動到正確的位置。

最終，通過適當計算內部迴圈的次數，你就能夠確保每次迭代都能將最大的未排序元素移動到正確的位置，從而實現氣泡排序。

#### Selction sort
way to sort:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序部分的最小元素的索引
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 將最小元素與當前位置元素交換
        arr[i], arr[min_index] = arr[min_index], arr[i]

# 測試
a=list(map(int,input()))
ans_sorted=selection_sort(a)
print("sorted:",a)

time complexity:O(n^2)

當你用選擇排序法排序一個數字列表時，就像是整理一堆數字卡片，迴圈和min_index有特定的工作：

迴圈：就像你在整理數字卡片時一張一張地看，外部迴圈是你的大動作，它讓你將已經排好序的卡片放在一邊，然後慢慢尋找未排序卡片中的最小數字。

min_index 變數：這就像是你用手指指著最小的數字卡片。當你翻看還沒排好序的卡片時，你的手指會指向當前最小的那張卡片。這樣，你就能確保你找到了最小的卡片。

總之，選擇排序法就像在整理數字卡片，你用迴圈一張一張看卡片，並用手指找到最小的卡片。這麼做幫助你把數字按照大小排好序。重複這個過程，直到所有卡片都排好序為止。

#### Insertion sort
way to sort:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 當前要插入的元素
        j = i - 1      # 已排序部分的最後一個元素的索引

        # 將比 key 大的元素向右移動，為 key 腾出插入位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        # 在適當的位置插入當前元素 key
        arr[j + 1] = key

# 測試
a=list(map(int,input()))
ans_sorted=insertion_sort(a)
print("sorted:",a)

time complexity:O(n^2)

當我們使用插入排序演算法時，我們要把一個未排序的數列按照順序排好。這就像是整理撲克牌，一張一張地將未排序的牌插入已排序的牌中。

假設你手上有一堆牌，一開始是亂的，你想要把它們從小到大排列。現在，你要使用兩個迴圈和一個叫作「關鍵牌（key）」的元素來完成這個工作。

外部迴圈： 你會從第一張牌開始，一直處理到最後一張牌。每次外部迴圈執行，都會選出一張未排序的牌，並將它插入到已排序的牌中。

內部迴圈： 當你拿起一張未排序的牌（我們稱之為「關鍵牌」），你會開始比較它與已排序的牌。如果關鍵牌比已排序的牌小，你會將這些已排序的牌往右移，騰出空間來插入關鍵牌。

關鍵牌（key）： 關鍵牌就是你目前正在處理的那張未排序的牌。你會將這張牌插入到已排序的位置，以確保整體牌組仍然保持有序。

換句話說，這個過程就像是在整理一堆牌。外部迴圈是你的手，一張一張地拿著牌，而內部迴圈則是你在已經排序好的牌中，尋找一個合適的位置將這張牌插入。而關鍵牌則是你手中目前正在處理的那張牌。

透過這種方式，你可以一步步地將未排序的元素插入到已排序的位置，最終達到整個數列的排序目標。雖然插入排序不像其他排序演算法那麼快，但在小型數列上是個實用的方法。

### Searching Algortihms
#### Linear Search
way to search:

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index  # 返回目標元素的索引位置
    return -1  # 如果找不到目標元素，返回 -1

# 測試
my_list = [3, 9, 2, 7, 1, 5]
target_element = 7

result = linear_search(my_list, target_element)

if result != -1:
    print(f"目標元素 {target_element} 在索引位置 {result}。")
else:
    print(f"目標元素 {target_element} 不存在於列表中。")

def linear_search(arr, target):：這是一個函數定義，我們定義了一個叫做 linear_search 的函數，它接受兩個參數：arr 是要搜尋的列表，target 是我們要尋找的目標元素。

for index, value in enumerate(arr):：這是一個迴圈，它用來遍歷列表 arr 中的每一個元素。enumerate 函數同時返回索引位置（index）和元素的值（value）。

if value == target:：這是一個條件語句，用來檢查目前迴圈所處的元素 value 是否等於我們要尋找的目標元素 target。

return index：如果找到了目標元素，我們使用 return 關鍵字來立即結束函數並返回目標元素的索引 index。

return -1：如果迴圈遍歷完整個列表仍然沒有找到目標元素，我們使用 return 來返回 -1，表示找不到目標元素。

線性搜尋演算法（Linear Search），也被稱為順序搜尋，是一種簡單的搜尋方法，用於在一個列表或陣列中尋找特定的元素。它的工作方式是從列表的開始元素開始，一個一個地比對目標元素，直到找到目標或者整個列表都被搜尋完畢。
想像你有一堆書，你想找到一本特定的書。你從第一本書開始，逐一翻閱，直到找到你要的那本書為止。這就是線性搜尋的概念。你從頭開始，一步一步地檢查每本書，直到找到目標書或者你已經翻遍了所有書。
在這個例子中，我們定義了一個 linear_search 函數，它接受一個列表和一個目標元素作為參數。該函數使用迴圈進行線性搜尋，對於列表中的每個元素，如果找到與目標元素相等的值，就返回該元素的索引位置。如果整個列表都被搜尋完畢後仍然找不到目標元素，則返回 -1。

請注意，線性搜尋在列表很大時可能效率較低，因為需要逐一比對每個元素。對於大型數據集，其他更快速的搜尋演算法如二元搜尋（Binary Search）可能更適合。

#### Binary Search
way to search:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2  # 找到中間位置的索引
        mid_value = arr[mid]  # 中間位置的值
        
        if mid_value == target:
            return mid  # 找到目標值，返回索引
        elif mid_value < target:
            left = mid + 1  # 目標值在右半部分，調整搜尋範圍
        else:
            right = mid - 1  # 目標值在左半部分，調整搜尋範圍
    
    return -1  # 沒有找到目標值，返回-1

# 測試
sorted_array = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target_value = 12
result = binary_search(sorted_array, target_value)

if result != -1:
    print(f"目標值 {target_value} 找到在索引 {result}")
else:
    print(f"目標值 {target_value} 未找到")

函數定義：我們首先定義了一個名為binary_search的函數，它接受兩個參數：arr（已排序的數據集）和target（我們要尋找的目標值）。

設置左右邊界：我們初始化兩個變數left和right，它們分別表示搜尋範圍的左邊界和右邊界。left初始化為0（數組的開始），right初始化為arr的長度減1（數組的結束）。

進入迴圈：我們使用一個while迴圈來執行二元搜尋。只要left小於等於right，我們就會在搜尋範圍內繼續搜索。

計算中間位置：我們計算中間位置的索引，使用整數除法運算符//來確保獲得整數結果。這個中間位置索引是mid，並且我們從arr中獲取對應的值mid_value。

比較中間值與目標值：我們將中間值mid_value與目標值target進行比較。

如果mid_value等於target，表示我們已經找到目標值，返回mid作為結果。
如果mid_value小於target，表示目標值位於右半部分，因此我們將left移到mid + 1的位置，縮小搜尋範圍。
如果mid_value大於target，表示目標值位於左半部分，因此我們將right移到mid - 1的位置，縮小搜尋範圍。
迴圈結束：一旦left大於right，表示搜尋範圍為空，我們退出迴圈。

返回結果：如果找到目標值，我們返回目標值在數組中的索引。如果未找到，則返回-1表示未找到。

測試：我們創建了一個已排序的數組sorted_array和一個目標值target_value，然後調用binary_search函數來尋找目標值。如果找到，我們印出它的索引；否則，我們印出未找到的訊息。

### Other Algorithms
#### Shuffling / Random Permutation

import random

def fisher_yates_shuffle(arr):
    n = len(arr)
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)  # Generate a random index between 0 and i
        arr[i], arr[j] = arr[j], arr[i]  # Swap elements at indices i and j

# Example list
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
fisher_yates_shuffle(my_list)
print("Shuffled list:", my_list)

import random
cards = ["A", "B", "C", "D", "E"]
random.shuffle(cards)
print(cards)

洗牌演算法的步驟：

1.從最後一個元素開始，遍歷到第一個元素，這裡的i表示當前元素的索引。
2.在每個迭代步驟中，生成一個隨機整數j，範圍從0到i之間（包括0和i）。
3.將索引為i的元素與索引為j的元素進行交換，從而實現元素的重新排列。

當我們想要把一些東西隨機打亂，就像玩撲克牌時洗牌一樣，我們可以使用洗牌演算法。在這個例子中，我們可以想像有一個裝有數字的紙條袋子，我們希望把這些數字隨機排列。這就是洗牌演算法的目的。

我們從袋子裡最後一張紙條開始，一張一張往前看，每張紙條都有一個編號，我們稱之為索引。比如最後一張的索引是最大的。
每次我們選一張紙條，然後從所有的紙條中隨機挑一張，讓這兩張紙條交換位置。
我們繼續往前，每次都隨機挑一張紙條來和目前這張交換，直到我們處理完所有的紙條。
通過這樣做，我們確保每張紙條都有平等的機會處於任何一個位置，這樣我們就達到了隨機打亂的效果。

在Python程式中，我們把紙條代表的數字放在一個列表中。然後我們用程式模仿了上面的步驟，最後印出了排列後的列表。這樣，我們就達到了隨機排列數字的目的。

#### Monte Carlo Simulation

import random

def monte_carlo_pi(num_samples):
    inside_circle = 0
    
    for _ in range(num_samples):
        x = random.random()  # 在 0 到 1 之間生成一個隨機 x 座標
        y = random.random()  # 在 0 到 1 之間生成一個隨機 y 座標
        distance = x**2 + y**2  # 計算點到原點的距離的平方
        
        if distance <= 1:  # 檢查點是否在半徑為 1 的圓內
            inside_circle += 1
    
    pi_estimate = (inside_circle / num_samples) * 4
    return pi_estimate

num_samples = 1000000  # 隨機點的數量
estimated_pi = monte_carlo_pi(num_samples)
print(f"使用蒙地卡羅模擬估計的 pi 值: {estimated_pi}")

蒙地卡羅模擬的簡單解釋：

蒙地卡羅模擬是一種通過隨機試驗來近似解決問題的方法。這種方法通常用於處理那些難以用傳統數學方法解決的複雜問題。我們通過隨機生成數據，然後對這些數據進行統計分析，從而得到我們感興趣的結果。

用蒙地卡羅模擬估計圓周率 π 的例子：

假設我們要用蒙地卡羅模擬來估計圓周率 π 的值。我們可以想像一個正方形，四個角上都有一個圓心，以及一個半徑等於正方形邊長一半的圓。現在，我們在這個正方形裡隨機扔一些點，然後計算有多少點落在圓內。如果我們用足夠多的點來模擬，那麼「圓內的點數」和「總點數」的比例就會接近「圓的面積」和「正方形的面積」的比例，而這個比例正好是 π / 4。

## Dynamic Programming(DP)

動態規劃（Dynamic Programming，簡稱 DP）是一種解決問題的方法，特別適用於需要儲存並重複使用子問題解的情況。它的核心思想是將一個大問題分解為一系列重疊且相互關聯的小問題，然後使用一個表格（或記憶化技巧）來儲存這些小問題的解，從而避免不必要的重複計算。

簡單來說，動態規劃的思想就是：「將問題分解成小問題，並記住這些小問題的答案，以優化整個問題的求解過程。」

這個概念可以用一個簡單的例子來解釋。假設你在計算費波那契數列的第 n 個數字。而你知道，費波那契數列的第 n 個數字等於第 n-1 個和第 n-2 個數字的和。在傳統的遞迴方法中，你會計算兩次第 n-1 個數字，但在動態規劃中，你只需要計算一次，並將答案儲存在表格中。這樣，當你需要再次計算第 n-1 個數字時，你只需要查表，而不需要重新計算。

總之，動態規劃通常用於優化具有重疊子問題性質的問題，通過記憶化或表格來儲存子問題的解，從而提高求解效率。

### Fibonacci

費波那契數列是一個序列，第一個和第二個數字都是1，從第三個數字開始，每個數字都是前兩個數字之和。例如：1, 1, 2, 3, 5, 8, 13, 21, ...

使用動態規劃求解費波那契數列：

我們可以使用動態規劃的方法來有效地計算費波那契數列的第 n 個數字。

def fibonacci_dp(n):
    if n <= 1:
        return n
    
    fib = [0] * (n + 1)
    fib[1] = 1
    
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

n = 10  # 要求解的費波那契數列的第 n 個數字
result = fibonacci_dp(n)
print(f"The {n}-th Fibonacci number is: {result}")

在這個範例中：

fibonacci_dp 函式用於計算第 n 個費波那契數字。
我們使用一個陣列 fib 來儲存計算過的費波那契數字，以避免重複計算。
我們從 2 開始迭代計算，每次計算 fib[i] 都等於前兩個數字的和。
最後，函式返回 fib[n]，即我們所求的第 n 個費波那契數字。

### Tower of Hanoi

def tower_of_hanoi_dp(n):
    # 建立一個陣列用於儲存移動步數
    steps = [0] * (n + 1)
    
    # 從 1 開始遞迴計算每一步的移動次數
    for i in range(1, n + 1):
        # 將圓盤 i 從柱子 A 移動到柱子 C 需要的步數是 2^i - 1
        steps[i] = 2 * steps[i - 1] + 1
    
    return steps[n]

# 讓使用者輸入圓盤的數量
n = int(input("請輸入圓盤的數量："))
result = tower_of_hanoi_dp(n)
print(f"移動 {n} 個圓盤所需的步數：{result}")

tower_of_hanoi_dp 函式使用動態規劃的思想來計算移動 n 個圓盤所需的最小步數。
我們使用一個陣列 steps 來儲存計算過的步數，steps[i] 代表移動 i 個圓盤所需的步數。
從 1 開始遞迴計算每一步的移動次數，我們可以觀察到移動 i 個圓盤需要移動兩倍圓盤數目減 1 步。
最後，函式返回 steps[n]，即移動 n 個圓盤所需的最小步數。

## Python視覺化工具
Matplotlib: Matplotlib 是 Python 中最常用的 2D 繪圖庫，用於繪製折線圖、散點圖、柱狀圖等。它具有廣泛的自定義選項和配置，可以生成高質量的圖表。

Seaborn: Seaborn 是基於 Matplotlib 的統計數據可視化庫，提供了一些更高級的圖表類型和配色方案，讓統計數據的視覺化變得更簡單。

Plotly: Plotly 是一個互動性非常強大的繪圖庫，支持繪製互動式的折線圖、散點圖、地圖、3D 圖等。它可以生成網頁上的互動圖表。

Bokeh: Bokeh 是另一個用於創建互動式網頁圖表的庫，它提供了各種圖表類型，並支持 JavaScript 回調，讓用戶可以與圖表進行互動。

Pandas: Pandas 是用於數據處理和分析的庫，它也提供了簡單的繪圖功能，可以直接對 DataFrame 數據進行繪圖。

ggplot: ggplot 是基於 R 中的 ggplot2 庫的 Python 版本，它提供了一種基於「圖形語法」的方式來創建各種圖表。

Altair: Altair 是一個宣告式的數據視覺化庫，它使用 JSON 規範來描述圖表，具有簡潔的語法和易於使用的界面。