---
# System prepended metadata

title: 教學紀錄

---

# 教學紀錄

## 其他筆記本

[Genereal.io Algorithm](https://hackmd.io/@St418/r1qurZvS3/edit)

## 2023/05/21

### HackMD簡介
* MarkDown
    * **BOLD**
    * `code`
* MarkUp
    * HTML Hyper Text MarkUp Language

* Code
```python=
print('Hello World!')
```

### Memory Layout

https://blog.gtwang.org/programming/memory-layout-of-c-program/

![](https://hackmd.io/_uploads/ryIWRlvrh.png)

#### static

#### dynamic stack
10
記憶體位址由宣告順序先後遞減(從高記憶體位址往低記憶體位址成長)
a - 2 -> 10
m - 1 -> 9
n - 0 -> 8

#### dynamic heap
vector

Point start {x, y} # stack

queue - reference(q) # stack
      - allocator # heap
      
push stack -> heap
emplace heap


#### & reference operator

#### auto: known at compile time

deallocate delete

life span


### Tree

Time Complexity `O(log(n))`

Small `10 ^ 6`

![](https://hackmd.io/_uploads/rJ3bSMwB3.png)


### cin-cout vs scanf-printf

Address -> Value


```c=
#include <stdio.h>

int a, m, n;

// format string
scanf("%d%d%d", &a, &m, &n);

// 11 22 33
printf("%d %d %d\n", a, m, n);

// 249ff1c 249ff18 249ff14
printf("%x %x %x\n", &a, &m, &n);
```

Buffer 緩衝

System call - I/O

```cpp=
#include <iostream>

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

int a, m, n;

// input stream
cin >> a >> m >> n;

// output stream -> to buffer
cout << a << m << n;

// end line
cout << endl;

// clear buffer -> system call
cout << '\n' << flush;
```

## 2023/06/05

[待補]

- 關鍵字：
### introsort(C++<algorithm>sort())
    
先進行快速排序(Quicksort)

遞迴深度超過一定深度後轉堆積排序(Heapsort)（深度：排序元素數量的對數值）
    
與quicksort.heapsort同為比較排序演算法
    
時間複雜度平均與最壞均為Ｏ(n log n)
    
### timsort(python sort)
    
先把整個資料分成小區塊，分別把小區塊的資料以Insertion Sort排序，然後再把這些區塊以Merge Sort的合併階段作法(merge function)來合併起來．

### hash
    
通過雜湊函式/演算法，將要檢索的項與用來檢索的索引（稱為雜湊，或者雜湊值）關聯起來，生成一種便於搜尋的資料結構（稱為雜湊表）
    
### kraskal's (MST)
    
權重最小的生成數
    
    尋找方式：
    
    將圖中所有邊依照權重由小到大排序
        
    依序選取邊加回圖上，若形成環則不加
        
    重複步驟直到圖上所有點皆有連線
    
    所形成的圖形即稱為最小生成樹
    
### method of using Kraskal's to make a maze
It based on a namesake algorithm for finding a Minimal Spanning Tree (MST) over a graph.    
    
    Steps:
    
    1.Create a set of all walls in the grid.
    
    2.Randomly select a wall from the grid. 
    
    If that wall connects two disjoint trees, join the trees. 
    
    Otherwise, remove that wall from the set.
    
    3.Repeat step 2 until there are no more walls left in the set.
    
code:
    
```python
from random import shuffle
from argparse import ArgumentParser
import numpy as np
import matplotlib.pylab as plt

def generate(x, y):
    with plt.ion():
        grid = np.ones((y, x), dtype=np.uint8)

        forest = [(i, j) for i in range(1, y - 1, 2)
                  for j in range(1, x - 1, 2)]

        for tree in forest:
            grid[tree] = 0

        plt.imshow(grid, 'gray_r')

        edges = [(i, j) for i in range(2, y - 1, 2) for j in range(1, x - 1, 2)] + \
                [(i, j) for i in range(1, y - 1, 2)
                 for j in range(2, x - 1, 2)]

        shuffle(edges)

        parent = dict(zip(forest, forest))
        # {tree: tree for tree in forest}

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        count = len(forest)
        
        # unpack
        for u, v in edges:
            if u % 2:
                x = u, v - 1
                y = u, v + 1
            else:
                x = u - 1, v
                y = u + 1, v

            x = find(x)
            y = find(y)
            if x != y:
                parent[x] = y
                grid[u, v] = 0
                count -= 1

            plt.clf()
            plt.imshow(grid, 'gray_r')
            plt.pause(0.001)

            if count == 0:
                break

    return grid

parser = ArgumentParser()
parser.add_argument('-x', type=int, help='width', default=5)
parser.add_argument('-y', type=int, help='height', default=5)
args = parser.parse_args()

maze = generate(**vars(args))
plt.imshow(maze, 'gray_r')
plt.show()

# functional programming
# object-oriented programming
```
    
    
    


- 參考資料：
pip install mazelib
Github
https://github.com/john-science/mazelib/tree/main

## 2023/06/12

[待補]

- 關鍵字：迷宮製作
### numpy
用於科學運算，支援高階大規模的多維陣列與矩陣運算
### matplotlib
資料視覺化
### pytorch
python機器學習庫
    
## 2023/06/19
    
### python library
    
### itertools
    
 Official website
    https://docs.python.org/3/library/itertools.html
    
    
### argparse
    
Official website    
https://docs.python.org/3/library/argparse.html


## 2023/07/31


Heuristic

Hamiltonain path (NP-Hard)
    


## 2023/09/04
    
## 2023/09/11

    rens_pump_lns()
    lns: Large Neighborhood Search
    rins_pump_lns()
    
