---
# System prepended metadata

title: '暑假第一周: 遞迴'

---

[c002. 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002)
```python=
def f(n):
    if n <= 100:
        return(f(f(n+11)))
    elif n >= 101:
        return n-10
while True:
    n = int(input())
    if n == 0:
        break
    print(f"f91({n}) = {f(n)}")
    
```
[d443. 10497 - Sweet Child Makes Trouble](https://zerojudge.tw/ShowProblem?problemid=d443)
```python=
def derangements(n):
    if n == 1:
        return 0
    elif n == 2 or n == 0:
        return 1
    return (n - 1) * (derangements(n - 1) + derangements(n- 2))
while True:
    n = int(input())
    if n == -1:
        break
    print(derangements(n))
```
學科筆記重點
![image](https://hackmd.io/_uploads/B1Efp91wR.png)
~按位翻轉 ~1 = -2, ~2 = -3,~-3 = 2, ,~-4 = 3
```PYTHON=
b = a
c = [1, 2, 3]

print(a is b)  # True，因為 a 和 b 指向同一個列表對象
print(b is c)  # False，雖然值相同，但 a 和 c 指向不同的列表對象
print(a is not c)  # True，a 和 c 指向不同的列表對象
```
[b573. 排列組合、最大公因數](https://zerojudge.tw/ShowProblem?problemid=b573)
```python=
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

def perm(ls, start, end):
    global z
    if(start >= end):
        z.append(ls.copy())
    else:
        for i in range(start, end + 1):
            ls[start], ls[i] = ls[i], ls[start]
            perm(ls, start + 1, end)
            ls[start], ls[i] = ls[i], ls[start]
n = int(input())
for i in range(n):
    z = []
    z1 = []
    i, j, k = map(int,input().split())
    perm(list(str(i)), 0, len(str(i))-1)
    for permuted_list in z:
        z1.append(int("".join(permuted_list)))
    z1.sort()
    print(gcd(z1[j-1],z1[k-1]))

```
[o078. 3. 缺字問題](https://zerojudge.tw/ShowProblem?problemid=o078)
```python=
z = []
def f(k,l,s):
    global z
    if l == 0:
        z.append(s)
        return
    for i in k:
        f(k,l-1,s+i)
k = list(input())
l = int(input())
s = input()
f(k,l,"")
ex = set(s[i:i+l] for i in range(len(s) - l + 1))#優化使用集合方式
for i in z:
    if i not in ex:
        print(i)
        break
```
[f607. 3. 切割費用](https://zerojudge.tw/ShowProblem?problemid=f607)
```python=
import bisect#chatgpt優化版

n, L = map(int, input().split())
li = [0, L]
z = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    z[b - 1] = a

ans = 0
for i in range(n):

    pos = bisect.bisect_left(li, z[i])
    if pos < len(li):
        ans += li[pos] - li[pos - 1]
        bisect.insort(li, z[i])

print(ans)

```
```python=
n, l = map(int,input().split())
li = [0,l]
z = [0] * n
for i in range(n):
    a, b = map(int,input().split(" "))
    z[b-1] = a
ans = 0
for i in range(n):
    for j in range(len(li)):
        if z[i] < li[j]:
            ans += li[j] - li[j-1]
            li.append(z[i])
            li.sort()
            break
print(ans)
```
[f637. DF-expression](https://zerojudge.tw/ShowProblem?problemid=f637)
```python=
def ex(n):
    global le,ans,idx
    if idx >= le:
        return
    idx += 1
    if k[idx] == "1":
        ans += n * n
    elif k[idx] == "2":
        ex(n//2)
        ex(n//2)
        ex(n//2)
        ex(n//2)
    return
k = input()
le = len(k)
idx = -1
ans = 0
n = int(input())
ex(n)
print(ans)
```
sliding window 演算法
[a320: P-4-13. 最大連續子陣列(P-5-2)](https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a320)
```python=
n= int(input())
z = [int(i) for i in input().split()]
for i in range(1,n):
    z[i] = z[i-1]+z[i] 
ma = 0 
for i in range(n):
    for j in range(i,n):
        isum = z[j]-z[i]
        if isum>ma:
            ma = isum
if ma < 0:
    print(0)
else:
    print(ma)
```
Q-1-11. 刪除矩形邊界 — 遞迴 (APCS201910, subtask)
```python=
mi = 9999
def side(x,x1,y,y1):
    global z,mi
    if x1 == x+1 or y1 == y+1:
        return 0
    li = []
    for i in range(y,y1):
        li.append(z[x][i])
    k1 = min(li.count(0),li.count(1))
    li = []
    for i in range(y,y1):
        li.append(z[x][i])
    k2 = min(li.count(0),li.count(1))
    li = []
    for i in range(x,x1):
        li.append(z[i][y])
    k3 = min(li.count(0),li.count(1))
    li = []
    for i in range(x,x1):
        li.append(z[i][y])
    k4 = min(li.count(0),li.count(1))
    kk = min(k1,k2,k3,k4)
    print(k1,k2,k3,k4)
    if kk < mi:
        mi = kk
    return side(x+1,x1-1,y+1,y1-1)
    
m, n = map(int,input().split())
z = []
for i in range(m):
    z.append([int(i) for i in input().split()])
side(0,m,0,n)
print(mi)
```
[d389. 11069 - A Graph Problem](https://zerojudge.tw/ShowProblem?problemid=d389)
```python=
def f(n):
    global z
    for i in range(4,n+1):
        z.append(z[i-2]+z[i-3])
z = [0,1,2,2]
f(76)
try:
    while True:
        n = int(input())
        print(z[n])
except EOFError:
    pass
```
111-O
```python=
ans = 0;li = []
def f(s,l,z):
    global ans,li
    if s <= 0:
        if s == 0:
            ans += 1
            li.append(z.copy())
        return
    for i in range(l,n):
        if s >= 0:
            z.append(c[i])
            f(s-c[i],i,z)
            z.pop()
n, x = map(int,input().split())
c = [int(i) for i in input().split()]
f(x,0,[])
print(li)
print(ans)
```
111-Ｍ
```python=
def f(n):
    if n == 1:
        return ["0", "1"]
    li = f(n-1)
    z = []
    for i in li:
        z.append("0" + i)
    for i in reversed(li):
        z.append("1" + i)
    return z
def print_f(n):
    codes = f(n)
    for code in codes:
        print(code)
print_f(int(input()))
'''
n = 1 回傳 0 1
然後添加正序與反序
n = 2
00 01 11 10
n = 3
000 001 011 010 110 111 101 100
'''
```