# 2020/11/2 計算機程式設計
###### tags: `Python`
## sorted()
key=[key1,key2,key3]
if same then compared the next
Ex:
期中筆試sorted那題
## merge sort

sort a[4] b[4]
sort a[0:4] b[0:4]
for sort a[0:4]
-> sort a[0:2] a[2:4]
    for sort a[0:2]
    ->sort a[0:1] a[1:2]
        for sort a[0:1]
        ->sort a[0] a[1]
        merge[0,1]
    merge[0,1,2]
merge[0,2,4]

#### 時間複雜度:O(nlog(n))
### example:
[4,3,2,6,5,1]
>[4,3,2,6,5,1,inf,inf]#變2的次方個
>[3,4][2,6][1,5][inf,inf]
>[2,3,4,6][1,5,inf,inf]
>[1,2,3,4,5,6,inf,inf]

## Goodstein sequences
- #### 與期中go函數相關(ppt提供solution)
- #### finite for every N
### Gn(b)=
> #### n ,if b=1
> #### go(b,Gn(b-1))-1 ,if Gn(b-1)>0
#### use oridinal number to proof
### 相關:海怪(hydra)
#### Thm:
任何形狀的海怪以任何順序砍頭，在有限刀內所有頭都會被砍光
### 延伸
- 哥德不完備定理
- 希爾伯特的二十三個問題
## 停機問題
#### Q:可否用一個python程式看出另一個python程式是否會在有限次數迴圈後停止
##### 如以下函式

import inspect
def h(function,para):
    code=inspect.getsource(func)
    if(code can end):
        return True
    else:
        return False

##### <proofed>圖靈:停機問題無解
GG證明

import h from h
def g(func):
    if h(func,func):
        while True: x=3

> #### h(g,g) == True ->g(g) 會停下來 by definition of h
> #### g(g) 會停下來 -> h(g,g)==False by definition of g
> #### 矛盾(-><-)故不存在
## 河內塔(Tower of Hanoi)
> ### Rule:
> #### 大碟子不能移到小碟子上
> #### 共三根柱子
> #### 須把一個塔移到另一位子
### Q:最少要幾步?
n=1 1步
n=2 3步
n=3 f(2)+1+f(2)步
step 0~3 類似f(2) (移動1&2 to B)
step 3~4 (移動3 to C)
step 4~7 類似f(2) (移動1&2 to C)
使用遞迴會好做很多
詳見PPT
## 費波那契數列
f(n)=1 ,n=1or2
f(n)=f(n-1)+f(n-2) ,n>=3

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

### 利用Recursion
#### 優點
- 程式簡潔，方便好想
#### 缺點
- 浪費時間、記憶體，時間複雜度高(指數成長)
### 利用list
#### 優點
- 時間複雜度O(n)(相對較低)
#### 缺點
- 浪費記憶體(用陣列儲存)