# 2020/11/9 計算機程式設計
###### tags: `Python`
## 零錢問題:
Ex $$n=8, S=\{1,4,6\}$$
輸出:$$f(n,S)=用最少個S中面值的郵票總數湊出n元當方法需要幾枚$$
### Solution 1: Recursion
$$
f(n,S)=\left\{\begin{array}{l}1\;,if\;n\in S\\\infty\;,if\;n<min(S)\\1+min_{x\in S}\;f(n-x,S)\;,otherwise\end{array}\right.
$$

### Solutino 2: Dynamic Programming
- 用 a[i] 記住算好的 f(i, S)
- 直接 for i in range(n) 去算每個值，每個值都可以從算好的 a[i] 推得

n=8
s={}

a=[n+1*(n+1)
for x in range(min(S),n+1):
    if x in S: a[x]=1;continue
    I={x-s for s in S if x>s}
    a[x] = 1 + min({a[i] for i in I})

## 八皇后問題
如何能夠在8×8的西洋棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變為n×n，而皇后個數也變成n。若且唯若n = 1或n ≥ 4時問題有解。

### Solution
冪集合用遞迴去爆搜
一個row一個row遞迴
s = [0] * n: 用一維記錄 Q 放的位置就好ㄌ
由於知道同一行同一列的地方都不能放
因此在第7行時可以從7-C開始

def explore(r):
    def mark(d,j=0):
        for i in range(r+1,n):
            b[i][c]+=d
            if c+j < n:b[i][c+j]+=d
            if c-j >= 0:b[i][c-j]+=d
            i+=1
    for c in range(n):
        if b[r][c]>0:continue
        s[r]=c
        if r == n-1:printsolution();continue
        mark(1)
        explore(r+1)
        mark(-1)
explore(0)

c=0
p=[]
while(True):
    x=input(f'')
    if x=='':break;

if y not in p: 
    p.append(y)
    n = len(p)
    s = 0

def move(d,g):
    global s
    if p[d]==g: return
    for l in range(d-1,-1,-1):
        move(l,({1,2,3}-{p[d],g}).pop())
    print(f'Step {(s:=s+1)}: move disk {d+1} from {p[d]} to {g}')
    p[d] = g

for d in range(n-1, -1, -1):
    move(d, 3)

print('搬好了')

## decorator
語法如下:

@hijack #hijack 先寫好
def add(x,y):return x+y
@hijack
def mul(x,y):return x*y

好處:不像原本hijack要自己呼叫，
只需要前面加一個@hijack
Note:適合debug

python語法原本就支援 如下

def deco(f,......):#這一塊會因為@deco而跑一次
    return g
@deco
def func(,......):
    ...

def deco(f):#這一塊會因為@deco而跑一次
    print('hello')
@deco
def func():
    .....
func()#出錯 (func=deco(func) --> func=None deco()沒回傳)

常用方法

def deco(f,.....):
    def func(*a,**b):#把純資料讀入a 把??=????? 讀入b變成字典
        ...
    return func

@deco
function(1,2,3,4,x,end=' ')