---
# System prepended metadata

title: 112上學期資訊課實作
tags: [已完成]

---

# 112上學期資訊課實作

## 一、基礎程式

### 1. 輸出「南光高中」

```python
# 使用內建函式print
print("南光高中")
```

```python
# 使用標準函式庫中的 sys.stdout
# print底層就是用sys.stdout實作的
# sys.stdout大量輸出時會比print快很多 但這個例子裡差不了多少
from sys import stdout
stdout.write("南光高中\n")
```

### 2. 輸入、輸出2個整數

```python
# 雖然輸入數字 但最後print的時候還是會轉成文字 乾脆不轉了直接輸出
print("第一個數字: " + input())
print("第二個數字: " + input())
```

### 3. 五則運算

```python
# 使用eval函式 簡潔又漂亮
# 輸入使用標準函式庫中的 sys.stdin 比input快太多 當然在這個例子裡也是差不了多少
from sys import stdin
# 將運算子存成一個串列 python中 /是一般除法 //是整數除法(無條件捨去)
ope = ["+", "-", "*", "//", "%"]
# 兩行各一個數字 因為等等要用eval所以不用轉成數字
a, b = stdin.read().split("\n")
for o in ope:
    # print等號前的算式時 //要輸出成/ 所以就用o[0]
    print(a + o[0] + b + "=" + str(eval(a + o + b)))
```

```python
# 一行解 用列表推導式遍歷ope
(lambda a, b: [print(a + o[0] + b + "=" + str(eval(a + o + b))) for o in ["+", "-", "*", "//", "%"]])(*[input() for _ in range(2)])
```

### 4. 分數及格判斷

```python
# 一般寫法 冗
score = input()
if int(score) >= 60:
    print("您的成績為" + score + "分,成績及格")
else:
    print("您的成績為" + score + "分,成績不及格")
```

```python
# 一行解 這邊用True = 1, False = 0 將判斷式當作list的index輸出
print((lambda score: "您的成績為" + score + "分," + 
       ["成績不及格", "成績及格"][int(score) >= 60])(input()))
```

```python
# 也可以用三元運算子 可讀性較高
print((lambda score: "您的成績為" + score + "分," + 
       ("成績及格" if int(score) >= 60 else "成績不及格"))(input()))
```

### 5. 重複結構for 2+4+6+...+N

```python
# 老師想要我們這麼寫
n = int(input())
ans = 0
for i in range(2, n+1, 2):  # n+1如果寫成n的話 i=n的回合不會執行
    ans += i
print(ans)
```

```python
# 也可以用sum代替for 雖然時間複雜度還是O(n)
# 但因為python的內建函數是用cpython實作的 所以會比較快
n = int(input())
print(sum(range(2, n+1, 2)))
```

```python
# 當然 代公式還是最快 時間O(1)
print((lambda x: (x + 1) * x)(int(input()) // 2))
```

### 6. 重複結構while 輸出n n-1 n-2...1

```python
# 老師想要我們這麼寫
n = int(input())
while n:  # n==0 時 n作為bool是False 該回合不執行
    print(n, end=" ")
    n -= 1
```

```python
# 當然 內建函式還是比較快 用列表推導式把range的int轉成str 再join起來輸出
print(" ".join([str(i) for i in range(int(input()), 0, -1)]))
```

### 7. 重複結構while 將n n-2 n-4... 等正整數寫進串列a再輸出 (把空間O(1)的題目硬是改成O(n))

```python
# 老師想要我們這麼寫
n = int(input())
a = []  # python dynamic array 不用分配空間:)
while n >= 0:
    a.append(n)
    n -= 2
print(" ".join([str(i) for i in a]))
```

```python
# 當然 a完全是多餘的
print(" ".join([str(i) for i in range(int(input()), 0, -2)]))
```

## 二、進階程式

### 1. 將串列進行氣泡排序 - 加碼幾個其他的排序法

```python
# 氣泡排序 Time: O(n²), Space: O(1)
# 每一輪把最大的交換到最後面
lst = [int(i) for i in input().split()]
for i in range(len(lst), 1, -1):  # 處理前i個
    flag = True  # 用flag紀錄 如果整輪都沒有交換就是已經排序好了 可以直接跳出
    for j in range(i-1):
        if lst[j] > lst[j+1]:  # 前面比後面大就交換
            lst[j], lst[j+1] = lst[j+1], lst[j]  # python交換是交換位址 所以可以這樣寫
            flag = False
    if flag: break  # 已經排序完成 提前跳出
print(*lst)  # 把lst unpack 再print
```

```python
# 插入排序法 Time: O(n²), Space: O(1)
# 每一輪循序找出lst[i-1] > lst[i]的地方 把lst[i] 那項往前移 直到前一個比他小
lst = [int(i) for i in input().split()]
i = 1
while True:
    while i < len(lst) and lst[i-1] <= lst[i]:  # 往後找到開始降冪的地方
        i += 1
    if i == len(lst): break
    while i >= 0 and lst[i-1] > lst[i]:  # 往前交換 直到排序正確
        lst[i-1], lst[i] = lst[i], lst[i-1]
        i -= 1
    i += 1
print(*lst)
```

```python
# 堆疊排序法 Time: O(nlogn), Space: O(1)
# 使用標準函式庫中的heapq模組 (感覺好敷衍)
from heapq import heapify, heappop
lst = [int(i) for i in input().split()]
# Linear Heapify Time: O(n), Space: O(1)
heapify(lst)
# Multiple Heappop Time: O(logn) for each, Space: O(1)
print(*[heappop(lst) for i in range(len(lst))])
```

```python
# 合併排序法 Time: O(nlogn), Space: O(n)
def merge(i, j):  # 合併排序 [i, j)
    if i == j-1: return [lst[i]]  # 只有一個元素不用排序

    # 分治 切一半
    mid = (i + j) // 2  # 取中點
    le = merge(i, mid)  # 排序左邊
    ri = merge(mid, j)  # 排序右邊

    # 合併
    idx = i  # 寫入lst起始位置
    x = y = 0  # 左右串列的位置
    while x < len(le) and y < len(ri):
        # 左右取比較小的
        if le[x] <= ri[y]:
            lst[idx] = le[x]
            x += 1
        else:
            lst[idx] = ri[y]
            y += 1
        idx += 1
    # 把剩下的寫入
    while x < len(le):
        lst[idx] = le[x]
        x += 1
        idx += 1
    while y < len(ri):
        lst[idx] = ri[y]
        y += 1
        idx += 1
    # 回傳排序後的區間
    return lst[i:j]

lst = [int(i) for i in input().split()]
lst = merge(0, len(lst))  # 起始區間 [0, n)
print(*lst)
```

### 2. 循序搜尋

```python
# 自己手刻函式
def find(arr, target):
    for idx, item in enumerate(arr):
        if item == target: return idx  # 找到第一個符合的
    return -1  # 找不到return -1
target = int(input())
arr = [int(i) for i in input().split()]
if (idx := find(arr, target)) == -1:  # 海象運算子:= 很可愛
    print("無法找到搜尋目標數字")
    print("搜尋次數:", len(arr), sep="")
else:
    print("發現搜尋目標數字，索引值為", idx, sep="")
    print("搜尋次數:", idx + 1, sep="")
```

```python
# 使用生成器推導式 以next(generator, default)函式找出第一個符合的
target = int(input())
arr = [int(i) for i in input().split()]
# 整個next()的功能和上面的find一模一樣 (用海象的話就太長了 分兩行寫)
idx = next((idx for idx, item in enumerate(arr) if item == target), -1)
if idx == -1:
    print("無法找到搜尋目標數字")
    print("搜尋次數:", len(arr), sep="")
else:
    print("發現搜尋目標數字，索引值為", idx, sep="")
    print("搜尋次數:", idx + 1, sep="")
```

## 三、語法整理
1. **進階語法:**
    - `[expr for var in iterable if condition]`: 各種推導式
    - `if-else`: 三元運算子
    - `lambda`: 匿名函式
    - `:=`: 海象運算子 回傳並賦值

2. **內建函式:**
    - `eval`: 動態運算函式
    - `split`: 字串切割函式，以分割字元將字串切割成列表
    - `join`: 字串連接函式
    - `range`: 區間生成函式
    - `enumerate`: 列舉函式，同時獲取索引和元素值
    - `next`: 迭代器取值函式

3. **函式庫:**
    - `sys .stdout .stdin`: 標準輸出和標準輸入
    - `heapq .heapify .heappop`: 堆排序相關函式庫