def tên_hàm(tham_số1, tham_số2, ...):
    """
    Chuỗi mô tả hàm (docstring)
    """
    # Thân hàm
    # Các câu lệnh
    return giá_trị_trả_về  # Không bắt buộc

def chao_hoi():
    """Hàm in ra lời chào"""
    print("Xin chào! Chào mừng bạn đến với Python")
    print("Hôm nay là một ngày đẹp trời!")

# Gọi hàm
chao_hoi()

def tinh_dien_tich_hinh_chu_nhat(chieu_dai, chieu_rong):
    """Tính diện tích hình chữ nhật"""
    dien_tich = chieu_dai * chieu_rong
    return dien_tich

# Sử dụng hàm
dai = 5
rong = 3
s = tinh_dien_tich_hinh_chu_nhat(dai, rong)
print(f"Diện tích hình chữ nhật {dai}x{rong} là: {s}")

def tinh_luong_thuong(luong_co_ban, he_so=1.5):
    """
    Tính lương thưởng cuối năm
    he_so mặc định là 1.5 nếu không cung cấp
    """
    return luong_co_ban * he_so

# Gọi hàm với đủ tham số
print(f"Lương thưởng: {tinh_luong_thuong(5000000, 2.0)}")

# Gọi hàm với tham số mặc định
print(f"Lương thưởng (mặc định): {tinh_luong_thuong(5000000)}")

# Tham số: a, b
def cong(a, b):
    return a + b

# Đối số: 5, 3
ket_qua = cong(5, 3)

# Biến toàn cục (global)
x = 10

def thay_doi_gia_tri():
    # Biến cục bộ (local)
    x = 5
    print(f"Giá trị trong hàm: {x}")

thay_doi_gia_tri()  # In ra: 5
print(f"Giá trị ngoài hàm: {x}")  # In ra: 10

def menu():
    """Hiển thị menu lựa chọn"""
    print("\n" + "="*30)
    print("MÁY TÍNH ĐƠN GIẢN")
    print("="*30)
    print("1. Cộng hai số")
    print("2. Trừ hai số")
    print("3. Nhân hai số")
    print("4. Chia hai số")
    print("5. Thoát")
    print("="*30)

def nhap_so():
    """Nhập hai số từ bàn phím"""
    a = float(input("Nhập số thứ nhất: "))
    b = float(input("Nhập số thứ hai: "))
    return a, b

def cong(a, b):
    return a + b

def tru(a, b):
    return a - b

def nhan(a, b):
    return a * b

def chia(a, b):
    if b != 0:
        return a / b
    else:
        return "Lỗi: Không thể chia cho 0!"

# Chương trình chính
while True:
    menu()
    lua_chon = input("Nhập lựa chọn (1-5): ")

    if lua_chon == '5':
        print("Cảm ơn bạn đã sử dụng chương trình!")
        break

    if lua_chon in ['1', '2', '3', '4']:
        a, b = nhap_so()

        if lua_chon == '1':
            ket_qua = cong(a, b)
            phep_tinh = "+"
        elif lua_chon == '2':
            ket_qua = tru(a, b)
            phep_tinh = "-"
        elif lua_chon == '3':
            ket_qua = nhan(a, b)
            phep_tinh = "×"
        else:  # lua_chon == '4'
            ket_qua = chia(a, b)
            phep_tinh = "÷"

        print(f"{a} {phep_tinh} {b} = {ket_qua}")
    else:
        print("Lựa chọn không hợp lệ! Vui lòng chọn lại.")

def ham_de_quy(tham_so):
    # 1. Kiểm tra điều kiện dừng (base case)
    if dieu_kien_dung:
        return ket_qua_co_so

    # 2. Xử lý đệ quy (recursive case)
    else:
        # Gọi lại chính hàm này với tham số nhỏ hơn
        return tinh_toan(tham_so, ham_de_quy(tham_so_nho_hon))

def giai_thua(n):
    """
    Tính giai thừa của n bằng đệ quy
    """
    # Phần cơ sở
    if n == 0 or n == 1:
        return 1
    # Phần đệ quy
    else:
        return n * giai_thua(n - 1)

# Kiểm tra
for i in range(6):
    print(f"{i}! = {giai_thua(i)}")

giai_thua(5)
= 5 * giai_thua(4)
= 5 * (4 * giai_thua(3))
= 5 * (4 * (3 * giai_thua(2)))
= 5 * (4 * (3 * (2 * giai_thua(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

def fibonacci(n):
    """
    Tìm số Fibonacci thứ n bằng đệ quy
    """
    # Phần cơ sở
    if n <= 1:
        return n
    # Phần đệ quy
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# In 10 số Fibonacci đầu tiên
print("10 số Fibonacci đầu tiên:")
for i in range(10):
    print(f"F({i}) = {fibonacci(i)}")

               fibonacci(4)
               /          \
       fibonacci(3)      fibonacci(2)
        /       \          /       \
fibonacci(2) fibonacci(1) fibonacci(1) fibonacci(0)
   /       \       1           1           0
fibonacci(1) fibonacci(0)
    1           0

def sinh_nhi_phan(n, chuoi=""):
    """
    Sinh tất cả các dãy nhị phân độ dài n
    """
    # Nếu độ dài chuỗi đã bằng n, in kết quả
    if len(chuoi) == n:
        print(chuoi)
    else:
        # Thử thêm '0' và đệ quy
        sinh_nhi_phan(n, chuoi + "0")
        # Thử thêm '1' và đệ quy
        sinh_nhi_phan(n, chuoi + "1")

print("Tất cả dãy nhị phân độ dài 3:")
sinh_nhi_phan(3)

def hoan_vi(arr, left, right):
    """
    Sinh tất cả hoán vị của mảng arr từ vị trí left đến right
    """
    if left == right:
        # In ra hoán vị khi đã đủ độ dài
        print(''.join(arr))
    else:
        for i in range(left, right + 1):
            # Đổi chỗ phần tử tại vị trí left và i
            arr[left], arr[i] = arr[i], arr[left]
            # Đệ quy cho phần còn lại
            hoan_vi(arr, left + 1, right)
            # Quay lui (backtrack): đổi lại vị trí ban đầu
            arr[left], arr[i] = arr[i], arr[left]

print("Tất cả hoán vị của ABC:")
chuoi = list("ABC")
hoan_vi(chuoi, 0, len(chuoi) - 1)

def to_hop_chap_k(n, k, bat_dau=1, day=[], do_sau=0):
    """
    Sinh tất cả tổ hợp chập k của n số từ 1 đến n
    """
    # Nếu đã chọn đủ k phần tử
    if do_sau == k:
        print(day)
    else:
        # Duyệt các phần tử từ vị trí bắt đầu đến n
        for i in range(bat_dau, n + 1):
            # Thêm phần tử i vào dãy
            day.append(i)
            # Đệ quy chọn phần tử tiếp theo
            to_hop_chap_k(n, k, i + 1, day, do_sau + 1)
            # Quay lui: bỏ phần tử i ra khỏi dãy
            day.pop()

print("Tất cả tổ hợp chập 2 của 4:")
to_hop_chap_k(4, 2)

def thap_ha_noi(n, coc_nguon, coc_dich, coc_trung_gian):
    """
    Giải bài toán Tháp Hà Nội
    n: số đĩa
    coc_nguon: cọc nguồn
    coc_dich: cọc đích
    coc_trung_gian: cọc trung gian
    """
    if n == 1:
        print(f"Di chuyển đĩa 1 từ {coc_nguon} sang {coc_dich}")
    else:
        # 1. Di chuyển n-1 đĩa từ nguồn sang trung gian
        thap_ha_noi(n-1, coc_nguon, coc_trung_gian, coc_dich)

        # 2. Di chuyển đĩa lớn nhất từ nguồn sang đích
        print(f"Di chuyển đĩa {n} từ {coc_nguon} sang {coc_dich}")

        # 3. Di chuyển n-1 đĩa từ trung gian sang đích
        thap_ha_noi(n-1, coc_trung_gian, coc_dich, coc_nguon)

print("Giải bài toán Tháp Hà Nội với 3 đĩa:")
thap_ha_noi(3, 'A', 'C', 'B')

Mảng đã sắp xếp: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Tìm x = 23

Bước 1: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
        ↑               ↑                    ↑
       left            mid                  right
        mid = (0+9)//2 = 4, arr[4] = 16
        23 > 16 → tìm ở nửa bên phải

Bước 2: [23, 38, 56, 72, 91]
        ↑       ↑       ↑
       left    mid    right
        mid = (5+9)//2 = 7, arr[7] = 56
        23 < 56 → tìm ở nửa bên trái

Bước 3: [23, 38]
        ↑  ↑  ↑
        l mid r
        mid = (5+6)//2 = 5, arr[5] = 23
        Tìm thấy tại vị trí 5!

def binary_search_recursive(arr, target, left=0, right=None):
    """
    Tìm kiếm nhị phân bằng phương pháp chia để trị (đệ quy)
    """
    if right is None:
        right = len(arr) - 1

    # Bước cơ sở: không tìm thấy
    if left > right:
        return -1

    # Bước CHIA: tìm phần tử giữa
    mid = (left + right) // 2

    # Bước TRỊ: so sánh với target
    if arr[mid] == target:
        return mid  # Tìm thấy
    elif arr[mid] > target:
        # Tìm trong nửa trái: CHIA nhỏ hơn nữa
        return binary_search_recursive(arr, target, left, mid - 1)
    else:
        # Tìm trong nửa phải: CHIA nhỏ hơn nữa
        return binary_search_recursive(arr, target, mid + 1, right)

# Ví dụ
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search_recursive(arr, target)
print(f"Tìm kiếm nhị phân đệ quy: {target} ở vị trí {result}")

def binary_search_iterative(arr, target):
    """
    Tìm kiếm nhị phân bằng phương pháp chia để trị (vòng lặp)
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        # CHIA: Tìm phần tử giữa
        mid = (left + right) // 2

        # TRỊ: So sánh và quyết định
        if arr[mid] == target:
            return mid  # Tìm thấy
        elif arr[mid] < target:
            # Tìm nửa bên phải
            left = mid + 1
        else:
            # Tìm nửa bên trái
            right = mid - 1

    return -1  # Không tìm thấy

# Ví dụ
target = 38
result = binary_search_iterative(arr, target)
print(f"Tìm kiếm nhị phân vòng lặp: {target} ở vị trí {result}")

Bài toán ban đầu: Tìm x trong mảng n phần tử
         │
         ▼
    CHIA: Tìm phần tử giữa
         │
    ┌────┴────┐
    ▼         ▼
x < arr[mid] x > arr[mid]
    │           │
    ▼           ▼
Tìm nửa trái  Tìm nửa phải
(n/2 phần tử) (n/2 phần tử)
    │           │
    ▼           ▼
  TRỊ: đệ quy TRỊ: đệ quy
    │           │
    └─────┬─────┘
          ▼
   KẾT HỢP: trả về kết quả

def merge_sort(arr):
    """
    Sắp xếp mảng bằng thuật toán MergeSort
    """
    # Trường hợp cơ sở
    if len(arr) <= 1:
        return arr

    # CHIA: Chia đôi mảng
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # TRỊ: Sắp xếp đệ quy
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)

    # KẾT HỢP: Trộn hai mảng đã sắp xếp
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """
    Trộn hai mảng đã sắp xếp
    """
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Thêm phần còn lại
    result.extend(left[i:])
    result.extend(right[j:])

    return result

# Ví dụ
arr = [38, 27, 43, 3, 9, 82, 10]
print(f"\nMergeSort - Mảng ban đầu: {arr}")
sorted_arr = merge_sort(arr.copy())
print(f"Mảng sau sắp xếp: {sorted_arr}")

def quick_sort(arr):
    """
    Sắp xếp mảng bằng QuickSort
    """
    if len(arr) <= 1:
        return arr

    # CHIA: Chọn pivot và phân hoạch
    pivot = arr[len(arr) // 2]

    # Phân hoạch thành 3 phần
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    # TRỊ: Sắp xếp đệ quy
    # KẾT HỢP: Ghép các phần
    return quick_sort(left) + middle + quick_sort(right)

# Ví dụ
arr = [38, 27, 43, 3, 9, 82, 10]
print(f"\nQuickSort - Mảng ban đầu: {arr}")
sorted_arr = quick_sort(arr.copy())
print(f"Mảng sau sắp xếp: {sorted_arr}")

Bài toán kích thước n
         │
         ▼
    CHIA thành a bài toán con
         │
    ┌────┴────┐
    ▼         ▼
Bài toán    Bài toán
 con 1      con a
(kích thước   (kích thước
   n/b)          n/b)
    │             │
    ▼             ▼
  TRỊ: giải     TRỊ: giải
   đệ quy        đệ quy
    │             │
    └──────┬──────┘
           ▼
     KẾT HỢP kết quả
           │
           ▼
   Lời giải bài toán

def fibonacci_simple(n):
    """Fibonacci đệ quy thông thường (không tối ưu)"""
    if n <= 1:
        return n
    return fibonacci_simple(n-1) + fibonacci_simple(n-2)

# Tính F(6)
print("Fibonacci thông thường F(6) =", fibonacci_simple(6))

                F(6)
               /     \
            F(5)     F(4)
           /   \     /   \
        F(4)  F(3) F(3)  F(2)
        / \   / \  / \   / \
     F(3)F(2)... (tiếp tục)

def fibonacci_memo(n, memo={}):
    """
    Fibonacci với đệ quy có nhớ
    memo: từ điển lưu trữ các giá trị đã tính
    """
    # Kiểm tra xem đã tính F(n) chưa
    if n in memo:
        return memo[n]

    # Trường hợp cơ sở
    if n <= 1:
        memo[n] = n
        return n

    # Tính toán và lưu vào memo
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# Tính F(6)
print("Fibonacci có nhớ F(6) =", fibonacci_memo(6))
print("Memo:", fibonacci_memo.__defaults__[0])

F(6) → tính F(5) và F(4)
F(5) → tính F(4) và F(3)  # nhưng F(4) đã được F(6) tính trước?

ĐỆ QUY THÔNG THƯỜNG          ĐỆ QUY CÓ NHỚ
      F(6)                         F(6)
     /    \                         |
    F(5)  F(4)                     F(5)
   /    \   |                       |
  F(4) F(3) F(3)                   F(4)
  ...    ...                       ... (mỗi F(k) chỉ tính 1 lần)

25 lần gọi hàm                7 lần gọi hàm

def memoize(func):
    """Decorator để thêm tính năng memoization cho bất kỳ hàm nào"""
    cache = {}

    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]

    return wrapper

@memoize
def fibonacci_decorated(n):
    """Fibonacci với decorator memoize"""
    if n <= 1:
        return n
    return fibonacci_decorated(n-1) + fibonacci_decorated(n-2)

# Sử dụng
print("Fibonacci với decorator F(10) =", fibonacci_decorated(10))

def fibonacci_list(n, memo=None):
    """Fibonacci với memoization dùng list"""
    if memo is None:
        # Khởi tạo memo với None cho tất cả các vị trí
        memo = [None] * (n + 1)

    # Đã tính
    if memo[n] is not None:
        return memo[n]

    # Base case
    if n <= 1:
        memo[n] = n
        return n

    # Tính toán và lưu
    memo[n] = fibonacci_list(n-1, memo) + fibonacci_list(n-2, memo)
    return memo[n]

print("Fibonacci với list F(10) =", fibonacci_list(10))

def fibonacci_bottom_up(n):
    """Fibonacci không đệ quy, tính từ dưới lên"""
    if n <= 1:
        return n

    # Tạo mảng lưu trữ
    fib = [0] * (n + 1)
    fib[0] = 0
    fib[1] = 1

    # Tính từ nhỏ đến lớn
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]

    return fib[n]

print("Fibonacci bottom-up F(10) =", fibonacci_bottom_up(10))

def combination_memo(n, k, memo={}):
    """Tính tổ hợp C(n,k) với đệ quy có nhớ"""
    # Tạo key duy nhất cho cặp (n,k)
    key = (n, k)

    # Kiểm tra đã tính chưa
    if key in memo:
        return memo[key]

    # Base cases
    if k == 0 or k == n:
        memo[key] = 1
        return 1

    # Tính toán và lưu
    memo[key] = combination_memo(n-1, k-1, memo) + combination_memo(n-1, k, memo)
    return memo[key]

# Ví dụ
print("C(10, 3) =", combination_memo(10, 3))
print("C(20, 10) =", combination_memo(20, 10))

def climb_stairs(n, memo={}):
    """Số cách leo cầu thang với đệ quy có nhớ"""
    if n in memo:
        return memo[n]

    # Base cases
    if n == 0:  # Đứng tại chỗ
        return 1
    if n == 1:  # Chỉ có 1 cách: bước 1 bậc
        return 1

    # Công thức: ways(n) = ways(n-1) + ways(n-2)
    memo[n] = climb_stairs(n-1, memo) + climb_stairs(n-2, memo)
    return memo[n]

# Ví dụ
print("Số cách leo 5 bậc thang:", climb_stairs(5))
print("Số cách leo 10 bậc thang:", climb_stairs(10))

def knapsack(values, weights, capacity, n, memo={}):
    """Bài toán cái túi với đệ quy có nhớ"""
    # Tạo key duy nhất
    key = (capacity, n)

    if key in memo:
        return memo[key]

    # Base case: không còn đồ vật hoặc không còn dung lượng
    if n == 0 or capacity == 0:
        return 0

    # Nếu đồ vật thứ n quá nặng, bỏ qua
    if weights[n-1] > capacity:
        memo[key] = knapsack(values, weights, capacity, n-1, memo)
        return memo[key]

    # Lựa chọn: lấy hoặc không lấy đồ vật thứ n
    take = values[n-1] + knapsack(values, weights, capacity - weights[n-1], n-1, memo)
    skip = knapsack(values, weights, capacity, n-1, memo)

    memo[key] = max(take, skip)
    return memo[key]

# Ví dụ
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
n = len(values)
print("Giá trị tối đa có thể lấy:", knapsack(values, weights, capacity, n))