CCF GESP 编程能力等级认证（Python）· 知识点手册

name = "小明"      # 变量：字符串
age = 10           # 变量：整数
score = 95.5       # 变量：小数
print(name, age, score)

a = 10          # int
b = 3.14        # float
c = "你好"      # str
d = True        # bool
print(type(a))  # <class 'int'>
print(type(c))  # <class 'str'>

name = input("请输入名字：")   # 输入（返回字符串）
print("你好，", name)            # 输出
age = int(input("年龄："))       # 要算数先 int()

# 顺序：从上到下
a = int(input()); b = int(input())
print(a + b)
# 分支
if a >= 60:
    print("及格")
else:
    print("不及格")
# 循环
s = 0
for i in range(1, 101):
    s += i
print(s)      # 5050

import turtle          # 导入 turtle 模块
t = turtle.Turtle()   # 创建小乌龟
t.forward(100)        # 前进 100 步
t.left(90)            # 左转 90 度
t.forward(100)
turtle.done()

print(ord("A"))    # 65（字符转编码）
print(chr(65))    # 'A'（编码转字符）
# 小写 = 大写 + 32：'a' = 65 + 32 = 97
print(ord("a") - ord("A"))   # 32

x = int("123")       # 字符串→整数
y = float("3.5")     # →小数
s = str(100)         # 整数→字符串
n = int(3.99)        # 3（截断，不是四舍五入）
print(round(3.6))    # 4（四舍五入）
# 隐式转换：int 和小数运算自动变成小数
print(3 + 0.5)       # 3.5

score = int(input())
if score >= 90:
    print("优秀")
elif score >= 80:
    print("良好")
elif score >= 60:
    print("及格")
else:
    print("不及格")

for i in range(1, 6):        # 外层管行
    for j in range(1, i + 1):   # 内层管列
        print("*", end="")
    print()                     # 换行
# 输出直角三角形

import math
abs(-5)          # 5    绝对值
max(3, 7, 2)     # 7    最大值
min(3, 7, 2)     # 2    最小值
round(3.6)       # 4    四舍五入
math.sqrt(25)    # 5.0  平方根
pow(2, 10)       # 1024 乘方
# 随机数
import random
random.randint(1, 6)   # 1~6 随机整数（掷骰子）

n = 13
s = ""
while n > 0:
    s = str(n % 2) + s    # 余数往前拼
    n //= 2
print(s)                  # 1101
# Python 内置
print(bin(13))    # 0b1101
print(hex(255))   # 0xff
print(int("1101", 2))   # 13

n = 7
print(n & 1)      # 1 → 奇数（判断奇偶）
print(n << 1)     # 14（×2）
print(n >> 1)     # 3（÷2）
a, b = 5, 3
a ^= b; b ^= a; a ^= b   # 交换两数（异或技巧）

lst = [3, 1, 2]
lst.append(5)          # 末尾加
lst.sort()             # 排序
lst[0]                 # 第一个元素
# 列表解析（推导式）
squares = [x * x for x in range(5)]    # [0,1,4,9,16]
even = [x for x in range(10) if x % 2 == 0]   # 偶数
d = {"name": "小明", "age": 10}
d["name"]              # "小明"
s = {1, 2, 2, 3}       # {1, 2, 3}（去重）

s = "Python Programming"
print(s.upper())         # PYTHON PROGRAMMING
print(s.split(" "))      # ['Python', 'Programming']
print(s[0:6])            # 'Python'（切片）

# 找 100~999 的水仙花数
for n in range(100, 1000):
    a = n // 100
    b = n // 10 % 10
    c = n % 10
    if a**3 + b**3 + c**3 == n:
        print(n, end=" ")    # 153 370 371 407

# 模拟：每天存钱，第 1 天 1 元、第 2 天 2 元……n 天后共多少
n = 10
total = 0
for day in range(1, n + 1):
    total += day
print(total)      # 55

def add(a, b):        # a、b 是形参
    return a + b
result = add(3, 5)    # 3、5 是实参
print(result)         # 8

x = 10                # 全局变量
def f():
    x = 20            # 局部变量（函数内新造一个）
    print(x)          # 20
f()
print(x)              # 10（外面没变）

count = 0
def add():
    global count      # 声明要用全局的 count
    count += 1
add(); add()
print(count)          # 2

def change(lst):
    lst.append(99)      # 列表可变，外面也会变
a = [1, 2]
change(a)
print(a)              # [1, 2, 99]

# 列表里套字典（学生表）
students = [
    {"name": "小明", "scores": [90, 85]},
    {"name": "小红", "scores": [88, 95]},
]
print(students[0]["name"])        # 小明
print(students[1]["scores"][0])   # 88
# 字典里套列表
scores = {"math": [80, 90], "chinese": [85, 92]}
for k, v in scores.items():
    print(k, sum(v) / len(v))

# 斐波那契：f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)
n = 10
f = [0] * (n + 1)
f[1] = f[2] = 1
for i in range(3, n + 1):
    f[i] = f[i - 1] + f[i - 2]
print(f[n])       # 55

def bubble(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

def insert_sort(a):
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]; j -= 1
        a[j + 1] = key
    return a

def select_sort(a):
    for i in range(len(a) - 1):
        mn = i
        for j in range(i + 1, len(a)):
            if a[j] < a[mn]: mn = j
        a[i], a[mn] = a[mn], a[i]
    return a

# 写文件
with open("out.txt", "w", encoding="utf-8") as f:
    f.write("第一行\n")
# 追加
with open("out.txt", "a", encoding="utf-8") as f:
    f.write("追加内容\n")
# 读文件
with open("out.txt", "r", encoding="utf-8") as f:
    for line in f:
        print(line.strip())

try:
    n = int(input("请输入整数："))
    print(100 // n)
except ValueError:
    print("输入的不是整数！")
except ZeroDivisionError:
    print("不能除以 0！")

def is_prime(n):
    if n < 2: return False
    i = 2
    while i * i <= n:
        if n % i == 0: return False
        i += 1
    return True

def gcd(a, b):          # 辗转相除法（欧几里得）
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd(a, b)

def binary_search(a, x):
    l, r = 0, len(a) - 1
    while l <= r:
        mid = (l + r) // 2
        if a[mid] == x: return mid
        elif a[mid] < x: l = mid + 1
        else: r = mid - 1
    return -1

# 例：把 n 根长度不一的绳子切成 m 段，求每段最长能多长
def ok(mid, a, m):
    return sum(x // mid for x in a) >= m

n, m = 3, 4
a = [10, 15, 7]          # 绳子长度
l, r = 1, max(a)
while l <= r:
    mid = (l + r) // 2
    if ok(mid, a, m): l = mid + 1
    else: r = mid - 1
print(r)                 # 最长能切 5

def fact(n):
    if n <= 1: return 1        # 终止条件（非常重要）
    return n * fact(n - 1)     # 递归调用

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n <= 2: return 1
    return fib(n - 1) + fib(n - 2)
print(fib(50))    # 12586269025（很快）

def merge_sort(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    L = merge_sort(a[:m]); R = merge_sort(a[m:])
    i = j = 0; res = []
    while i < len(L) and j < len(R):
        if L[i] < R[j]: res.append(L[i]); i += 1
        else: res.append(R[j]); j += 1
    return res + L[i:] + R[j:]

def quick_sort(a):
    if len(a) <= 1: return a
    p = a[0]
    less = [x for x in a[1:] if x <= p]
    more = [x for x in a[1:] if x > p]
    return quick_sort(less) + [p] + quick_sort(more)

# 例：硬币找零（面额 1/5/10/20/50，求最少硬币数）
coins = [50, 20, 10, 5, 1]
amount = 78
count = 0
for c in coins:
    count += amount // c
    amount %= c
print(count)     # 5（50+20+5+1+1+1=6? 实际 78=50+20+5+1+1+1）

class Node:
    def __init__(self, v):
        self.v = v; self.left = None; self.right = None

def preorder(r):          # 前序：根-左-右
    if not r: return
    print(r.v, end=" "); preorder(r.left); preorder(r.right)
def inorder(r):           # 中序：左-根-右
    if not r: return
    inorder(r.left); print(r.v, end=" "); inorder(r.right)
def postorder(r):         # 后序：左-右-根
    if not r: return
    postorder(r.left); postorder(r.right); print(r.v, end=" ")

def insert(root, x):
    if root is None: return Node(x)
    if x < root.v: root.left = insert(root.left, x)
    else: root.right = insert(root.right, x)
    return root
# 中序遍历 BST = 从小到大输出

def dfs(x):
    if 越界 or 访问过: return
    visited[x] = True
    print(x, end=" ")
    for nxt in 邻居[x]:
        dfs(nxt)

from collections import deque
def bfs(start):
    q = deque([start])
    visited = {start}
    while q:
        x = q.popleft()
        print(x, end=" ")
        for nxt in 邻居[x]:
            if nxt not in visited:
                visited.add(nxt); q.append(nxt)

n = 10
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
print(dp[n])   # 89

# 背包容量 W，物品重量 w、价值 v，求最大价值
W, n = 10, 3
w = [0, 3, 4, 5]; v = [0, 4, 5, 6]
dp = [0] * (W + 1)
for i in range(1, n + 1):
    for j in range(W, w[i] - 1, -1):   # 倒序！0-1 背包
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[W])   # 10

class Dog:
    def __init__(self, name, age):   # 构造方法
        self.name = name             # 属性
        self.age = age
    def bark(self):                  # 方法
        print(self.name, "汪汪！")
d = Dog("旺财", 3)
d.bark()    # 旺财 汪汪！

from collections import deque
s = deque()          # 用双端队列当栈
s.append(1); s.append(2)
print(s.pop())       # 2（后进先出）

q = deque()
q.append(1); q.append(2)
print(q.popleft())   # 1（先进先出）

import math
math.sin(math.pi / 2)    # 1.0  正弦（弧度）
math.cos(0)              # 1.0  余弦
math.log10(1000)         # 3.0  以 10 为底的对数
math.log2(8)             # 3.0  以 2 为底
math.exp(1)              # e ≈ 2.718
math.pow(2, 10)          # 1024.0

a = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(a)
dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))    # 4（1,4,5,9 或 1,4,5,6）

s1, s2 = "abcde", "ace"
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[m][n])   # 3（"ace"）

# 邻接表存图
graph = [[] for _ in range(n + 1)]
# 加一条 u→v 的边
graph[u].append(v)

def dfs(u):
    visited[u] = True
    for v in graph[u]:
        if not visited[v]:
            dfs(v)

# 数一个 0/1 地图上有几块 1 的连通块
def flood_fill(x, y):
    stack = [(x, y)]; a[x][y] = 0
    while stack:
        i, j = stack.pop()
        for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            ni, nj = i + dx, j + dy
            if 0 <= ni < n and 0 <= nj < m and a[ni][nj] == 1:
                a[ni][nj] = 0; stack.append((ni, nj))

cnt = 0
for i in range(n):
    for j in range(m):
        if a[i][j] == 1:
            cnt += 1
            flood_fill(i, j)
print(cnt)

d = {}
d["apple"] = 3          # 插入/更新
print(d.get("apple"))   # 3（O(1) 查找）
s = {1, 2, 3}
print(1 in s)           # True（O(1) 判断存在）

from math import comb, perm
print(comb(5, 2))    # 10  组合
print(perm(5, 2))    # 20  排列

n = 6
t = [[0] * (n + 1) for _ in range(n + 1)]
t[0][0] = 1
for i in range(1, n + 1):
    for j in range(i + 1):
        t[i][j] = (t[i-1][j-1] if j > 0 else 0) + (t[i-1][j] if j < i else 0)
for i in range(n + 1):
    print(t[i][:i + 1])

# 快速幂：求 a^b % m
def qpow(a, b, m):
    res = 1
    while b:
        if b & 1: res = res * a % m
        a = a * a % m
        b >>= 1
    return res
print(qpow(2, 10, 1000000007))    # 1024

# 解一元一次方程 ax + b = 0
a, b = 2, -8
print(-b / a)        # 4.0
# 解二元一次方程组（用克莱姆法则）
# a1*x + b1*y = c1 ; a2*x + b2*y = c2
a1, b1, c1 = 1, 1, 5
a2, b2, c2 = 2, -1, 1
det = a1 * b2 - a2 * b1
x = (c1 * b2 - c2 * b1) / det   # 2
y = (a1 * c2 - a2 * c1) / det   # 3

# Kruskal：按边权从小到大加边，不成环就选（并查集判环）
edges.sort()                 # [(w, u, v), ...]
fa = list(range(n + 1))
def find(x):
    while fa[x] != x:
        fa[x] = fa[fa[x]]; x = fa[x]
    return x
ans = 0
for w, u, v in edges:
    fu, fv = find(u), find(v)
    if fu != fv:
        fa[fu] = fv; ans += w

# Dijkstra：单源最短路（边权非负）
import heapq
dist = [float("inf")] * (n + 1); dist[s] = 0
pq = [(0, s)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]: continue
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))