###### tags: `程式設計`
# 第八週
## 秘密暨南文章共享
<iframe src="https://www.facebook.com/plugins/post.php?href=https%3A%2F%2Fwww.facebook.com%2FNCNUSecrets2.0%2Fposts%2F1135119166854159&width=500" width="500" height="223" style="border:none;overflow:hidden" scrolling="yes" frameborder="0" allowTransparency="true" allow="encrypted-media"></iframe>

## 遞迴


### 遞迴的三大要件(步驟)
1. 函式的規格(參數)
2. 完成條件(終止條件)
3. 化簡(呼叫自己)的方法

### 費氏數列
1. 參數 `n` 代表費氏數列的第幾項
2. 完成條件，當 `n` <= 1 時，其值為n
3. 化簡方法，F(n - 1) + F(n - 2)

`n` 代表要找費氏數列的第 `n` 個序列

def F(n) :
    if n <= 1 :
        return n
    return F(n - 1) + F(n - 2)
    

### 河內塔問題

#定義 Hanoi 函數的規格
#n: 有幾個 disc(碟片) 要移動
#src: 來源柱子 (source)
#dest: 目的柱 (destination)
#third: 另一根柱子
#result: 每根柱子的 disc 號碼

def Hanoi(n, src, dest, third, result) :
    if n == 0 :
        print(*result[0], end=' ')
        print(*result[1], end=' ')
        print(*result[2])
        print('-----------------')
        return
    # 假設一共有 3 個盤子要移
    # 從第 0 根柱子移到第 1 根柱子
    # 要先做的事情是
    # 把 n - 1 個盤子移動到第 2 根柱子
    # (最大盤子上面被兩個盤子壓住，要移動前要先把他們移走)
    # 把最大的盤子從 0 移到 1
    # 把剛剛移走的兩個盤子從 2 移到 1
    # 上面是第一層步驟
    # 因為一次不能移動多個盤子
    # 所以要移動 2 個盤子的情況，又會再分步驟出去

    # 步驟 1 : move n-1 discs, from src to third
    Hanoi(n-1, src, third, dest, result)
    # 步驟 2 : move one disc, from src to dest
    result[dest].append(result[src].pop())
    # 步驟 3 : move n-1 disc, from third to dest
    Hanoi(n-1, third, dest, src, result)
    
def main() :
    n = int(input())
    Hanoi(n, 0, 1, 2, [[n-i for i in range(n)],[],[]])
if __name__ == '__main__' :
    main()

## 組合

# 給個 list,請取出所有 m 個的組合
# eg ABCDE,取出所有三 3 個的組合
# 有 5 種選擇,
# 選A, 然後給下一位同學(BCDE, 2, A)
# 選B, -->(CDE, 2, B)
# 選C, -->(DE, 2, C)
# data : 可選清單
# m : 要選幾個
# result : 前面同學已經選好的東西

def comb(data, n, result) :
    if m == 0 :
        print(*result)
        return
    for i in range(len(data)) : # 每個位置都有機會被選一次
        comb(data[i + 1:], m - 1, result+[data[i]])

def main() :
    # 讀入要組合的字串
    data = input().split()
    # 輸入要取幾個字母
    n = int(input())
    comb(data, n, [])

if __name__ == '__main__' :
    main()

## 忍術算術填入術

def findNum(data, m, result)) ;
    if m == 0 :
        first_line = result[0]*10+result[1]
        second_line = result[2]
        third_line = result[3]*10+result[4]
        forth_line = result[5]*10+result[6]
        fifth_line = result[7]*10+result[8]
        if first_list * second_line == third_line and third_line + forth_line == fifth_line :
            print(*result)
        return
    for i in range(len(data)) :
        findNum(data[:i]+data[i+1:], m-1, result+[data[i]])
def main() :
    findNum([i+1 for i in range(9)], 9, [])
     
if __name__ == '__main__' :
    main()