程序员的数学（三）余数：编程中的周期性与分组魔法

欢迎回到 “程序员的数学” 系列专栏。上一篇我们聊了 “逻辑”，知道了真 / 假二元世界是计算机判断的基础 —— 而今天要讲的 “余数”，可以说是连接 “逻辑” 与 “复杂问题” 的桥梁。比如逻辑中的 “奇偶判断”，本质就是 “除以 2 的余数”；再比如循环任务调度、数据分组，都离不开余数的 “简化魔法”。

你可能会说：“余数不就是除法剩下的数吗？小学就学过了，有什么好深入的？” 但在编程中，余数的价值远不止 “剩下的数”：它能把 “无限循环” 变成 “有限分组”，把 “庞大数字” 变成 “小范围判断”，甚至能帮我们快速定位 bug（比如奇偶校验）。今天我们就从 “分组” 和 “周期性” 两个核心角度，用生活和编程的例子把余数讲透，让你下次遇到循环、分组问题时，能第一时间想到 “用余数试试”。

一、为什么程序员需要余数？因为它能 “化繁为简”

先从两个编程场景说起，感受一下余数的 “简化能力”：

场景 1：计算 1 亿天后是星期几

如果让你计算 “今天是星期日，1 亿天后是星期几”，你会怎么算？难道要从 1 天、2 天… 数到 1 亿天吗？显然不可能 —— 但用余数一句话就能解决：1 亿除以 7 的余数，就是星期几的偏移量（因为一周有 7 天，周期是 7）。

计算过程：100000000 ÷ 7 = 14285714 余 2 → 星期日 + 2 天 = 星期二。就这么简单！

场景 2：数组按大小分组

有一个长度为 1000 的数组，要分成每组 5 个元素的子数组，怎么快速判断某个索引属于哪一组？比如索引 123 属于第几组？用余数：123 ÷ 5 = 24 余 3 → 余数 3≠0，所以属于第 25 组（24+1）；如果索引 120，120÷5=24 余 0，属于第 24 组。不用遍历数组，一句话就能定位分组，效率极高。

这就是余数的核心价值：把 “无限 / 庞大的问题” 压缩到 “有限的周期 / 分组” 里，用小范围的计算解决大范围的问题。计算机处理有限数据时效率最高，余数正好帮我们实现了这种 “压缩”。

二、余数的本质：分组与周期性

要理解余数，先记住一句话：余数是 “按周期分组” 的工具 —— 用 “除数” 作为周期，把所有数字分成 “余数为 0、1、2… 除数 - 1” 的若干组。比如除数是 7（星期的周期），所有天数就被分成 7 组：余数 0（星期日）、余数 1（星期一）… 余数 6（星期六）。

1. 用余数解决周期性问题：星期计算

我们从 “小数字” 到 “大数字”，逐步掌握周期问题的解法。

例子 1：100 天后是星期几？

已知今天是星期日（对应余数 0），步骤如下：

1. 确定周期：星期的周期是 7（除数 = 7）；
2. 计算余数：100 ÷ 7 = 14 余 2 → 余数 = 2；
3. 映射结果：余数 0→星期日，余数 1→星期一，余数 2→星期二。

结论：100 天后是星期二。

例子 2：1 亿天后是星期几？

步骤完全一样，只是数字变大，但余数计算不变：

1. 周期 = 7；
2. 100000000 ÷ 7 = 14285714 余 2 → 余数 = 2；
3. 余数 2→星期二。

不管数字多大，只要找到周期，用余数压缩后，问题就变成 “0~ 周期 - 1” 的小范围判断 —— 这就是余数的 “化繁为简” 魔法。

编程实现：通用星期计算函数

我们写一个函数，输入 “当前星期几” 和 “天数 n”，返回 n 天后的星期几：

def get_future_week(current_week, n):
    """
    current_week: 当前星期几（0=星期日，1=星期一，...，6=星期六）
    n: 未来的天数（正整数）
    返回：n天后的星期几（0~6）
    """
    cycle = 7  # 星期的周期是7
    remainder = n % cycle  # 计算n除以7的余数
    future_week = (current_week + remainder) % cycle  # 避免超过6
    return future_week

# 测试：今天是星期日（0），100天后→2（星期二），1亿天后→2（星期二）
print(get_future_week(0, 100))       # 输出2
print(get_future_week(0, 100000000)) # 输出2
# 边界测试：7天后→0（星期日），6天后→6（星期六）
print(get_future_week(0, 7))         # 输出0
print(get_future_week(0, 6))         # 输出6

关键细节：(current_week + remainder) % cycle 确保结果不会超过 6（比如当前是星期六（6），3 天后：6+3=9，9%7=2→星期一，正确）。

2. 用余数解决乘方周期性问题：大数字的个位计算

除了 “天数”，余数还能解决 “乘方的周期性” 问题。比如 “1234567 的 987654321 次方，个位是多少？”—— 直接计算不可能，但用余数能快速找到规律。

分析步骤：

1. 个位的周期：一个数的乘方个位，只和 “原数的个位” 有关（比如 1234567 的个位是 7，所以只需关注 7 的乘方个位）；
2. 找 7 的乘方个位周期：
   • 7¹=7 → 个位 7（余数 7%10=7）；
   • 7²=49 → 个位 9（9%10=9）；
   • 7³=343 → 个位 3（3%10=3）；
   • 7⁴=2401 → 个位 1（1%10=1）；
   • 7⁵=16807 → 个位 7（7%10=7）—— 周期出现了！周期是 4。
3. 计算指数的余数：指数是 987654321，周期是 4，所以余数 = 987654321 % 4 = 1（因为 987654320 是 4 的倍数，加 1 后余 1）；
4. 映射结果：余数 1→7¹ 的个位 7，所以最终个位是 7。

编程实现：大数字乘方的个位计算

python

def get_power_last_digit(base, exponent):
    """
    base: 底数（整数）
    exponent: 指数（正整数）
    返回：base^exponent 的个位数字
    """
    if exponent == 0:
        return 1  # 任何数的0次方个位是1（除0外，此处简化）
    # 步骤1：取底数的个位（只关注个位即可）
    last_digit = base % 10
    # 步骤2：找个位的乘方周期（预定义常见周期，或动态计算）
    # 预定义0-9的乘方周期：key=个位数字，value=周期列表
    cycles = {
        0: [0],          # 0的任何次方正数幂个位都是0，周期1
        1: [1],          # 1的任何次幂个位都是1，周期1
        2: [2,4,8,6],    # 2的周期4
        3: [3,9,7,1],    # 3的周期4
        4: [4,6],        # 4的周期2
        5: [5],          # 5的周期1
        6: [6],          # 6的周期1
        7: [7,9,3,1],    # 7的周期4（我们例子中的情况）
        8: [8,4,2,6],    # 8的周期4
        9: [9,1]         # 9的周期2
    }
    cycle = cycles[last_digit]
    cycle_len = len(cycle)
    # 步骤3：计算指数除以周期长度的余数（注意指数从1开始）
    remainder = exponent % cycle_len
    # 余数为0时，取周期最后一个元素（比如周期4，余数0→第4个元素）
    if remainder == 0:
        return cycle[-1]
    else:
        return cycle[remainder - 1]  # 余数1→第0个索引

# 测试：1234567^987654321 的个位→7
print(get_power_last_digit(1234567, 987654321))  # 输出7
# 测试：2^10 的个位→4（2^10=1024）
print(get_power_last_digit(2, 10))  # 输出4

这个函数的核心是 “用余数找到周期内的位置”—— 不管指数多大，最终都压缩到 “0~ 周期长度 - 1” 的范围，计算效率极高。

三、余数的特殊情况：奇偶性（余数为 0 或 1）

当除数是 2 时，余数只有 0 和 1 两种可能 —— 这就是我们常说的 “奇偶性”。上一篇讲逻辑时提到的 “真 / 假”，其实和 “奇 / 偶” 是对应的：奇数对应真，偶数对应假（或反之）。奇偶性是余数最常用的 “简化工具”，在数据校验、分组中高频出现。

1. 奇偶性的核心应用：数据传输中的奇偶校验

在网络传输、文件存储中，数据容易受干扰出错（比如 1 变成 0）。奇偶校验就是用 “余数” 来检测错误的简单方法：

• 发送端：在数据末尾加一个 “校验位”，让整个数据的 “1 的个数” 是奇数（奇校验）或偶数（偶校验）；
• 接收端：计算数据（包括校验位）的 “1 的个数”，看余数是否符合约定（奇校验→1 的个数余 1，偶校验→余 0），如果不符合，说明数据出错。

例子：偶校验的实现

假设要传输二进制数据10110，采用偶校验：

1. 发送端：计算数据中 1 的个数→1+0+1+1+0=3（奇数），需要加 1 个校验位（1），让总个数为 4（偶数），最终传输数据是101101；
2. 接收端：计算101101中 1 的个数→4（偶数），余数 0，符合偶校验，数据正确；
3. 如果传输中数据变成101001（中间的 1 变成 0），1 的个数→3（奇数），余数 1，不符合，判定出错。

编程实现：奇偶校验函数

python

def parity_check(data, is_even=True):
    """
    data: 二进制字符串（如"10110"）
    is_even: 是否为偶校验（True=偶校验，False=奇校验）
    返回：(带校验位的数据, 校验位)
    """
    # 步骤1：计算数据中1的个数
    one_count = data.count('1')
    # 步骤2：确定校验位（让总1的个数符合校验规则）
    if is_even:
        # 偶校验：总1的个数为偶数→余数0
        parity_bit = '1' if (one_count % 2 != 0) else '0'
    else:
        # 奇校验：总1的个数为奇数→余数1
        parity_bit = '1' if (one_count % 2 == 0) else '0'
    # 步骤3：拼接数据和校验位
    data_with_parity = data + parity_bit
    return data_with_parity, parity_bit

def is_data_correct(data, is_even=True):
    """
    验证带校验位的数据是否正确
    """
    one_count = data.count('1')
    if is_even:
        return one_count % 2 == 0
    else:
        return one_count % 2 == 1

# 测试：偶校验传输
data = "10110"
data_with_parity, parity_bit = parity_check(data, is_even=True)
print(f"原始数据：{data}，带校验位数据：{data_with_parity}，校验位：{parity_bit}")  # 输出101101，校验位1
# 验证正确数据
print(is_data_correct(data_with_parity, is_even=True))  # 输出True
# 验证错误数据（模拟传输错误）
wrong_data = "101001"
print(is_data_correct(wrong_data, is_even=True))  # 输出False

奇偶校验虽然简单，但能检测出 “1 位数据错误”，是计算机底层（如内存、网络帧）常用的错误检测方式 —— 而它的核心，就是 “除以 2 的余数”。

2. 奇偶性的其他应用：数组分组、路径判断

例子 1：数组按奇偶分组

把一个数组分成 “奇数数组” 和 “偶数数组”，用余数判断：

python

def split_odd_even(arr):
    odd_arr = []  # 奇数数组
    even_arr = [] # 偶数数组
    for num in arr:
        if num % 2 == 1:  # 余数1→奇数
            odd_arr.append(num)
        else:  # 余数0→偶数
            even_arr.append(num)
    return odd_arr, even_arr

# 测试：[1,2,3,4,5,6]→奇数[1,3,5]，偶数[2,4,6]
print(split_odd_even([1,2,3,4,5,6]))  # 输出([1,3,5], [2,4,6])

例子 2：判断路径是否存在（哥尼斯堡七桥问题）

这是数学史上的经典问题：哥尼斯堡有 7 座桥，连接 4 块陆地，能否从一块陆地出发，不重复走完所有桥回到起点？欧拉用 “奇偶性” 解决了这个问题：

• 把陆地当作 “点”，桥当作 “边”，每个点连接的边数叫 “度数”；
• 路径存在的条件：所有点的度数都是偶数（能回到起点），或只有 2 个点的度数是奇数（不能回到起点）；
• 哥尼斯堡七桥的 4 个点度数都是奇数（3、3、3、5），所以不存在这样的路径。

编程实现：判断欧拉路径是否存在

python

def has_euler_path(degrees):
    """
    degrees: 每个点的度数列表（如[3,3,3,5]）
    返回：是否存在欧拉路径（True/False）
    """
    odd_count = 0  # 度数为奇数的点的数量
    for d in degrees:
        if d % 2 == 1:
            odd_count += 1
    # 条件：奇数度数的点为0（欧拉回路）或2（欧拉路径）
    return odd_count == 0 or odd_count == 2

# 测试：哥尼斯堡七桥的度数[3,3,3,5]→odd_count=4→返回False
print(has_euler_path([3,3,3,5]))  # 输出False
# 测试：存在欧拉路径的情况（度数[2,2,3,3]→odd_count=2→返回True）
print(has_euler_path([2,2,3,3]))  # 输出True

这个例子告诉我们：复杂的几何问题，用余数（奇偶性）建模后，就能用简单的计数判断解决。

四、余数的进阶应用：铺设草席、黑白格染色

除了周期性和奇偶性，余数还能帮我们解决 “覆盖问题”—— 比如 “一个房间能否用 1×2 的草席铺满”，核心是用 “染色法” 结合余数判断。

例子：铺设草席问题

房间是 8×8 的正方形（去掉左上角和右下角两个黑格），用 1×2 的草席（每块草席覆盖 1 黑 1 白两个格子）能否铺满？

分析步骤：

1. 染色：把房间按 “黑白格” 交替染色（像国际象棋棋盘），左上角是黑格，右下角也是黑格（因为 8×8 的棋盘，(0,0) 和 (7,7) 都是黑格，去掉后剩下 62 个格子：30 黑 + 32 白）；
2. 草席特性：每块 1×2 的草席必覆盖 1 黑 1 白两个格子，n 块草席需覆盖 n 黑 + n 白个格子；
3. 余数判断：房间剩下 30 黑 + 32 白，黑格比白格少 2（余数 2），无法满足 “n 黑 = n 白”，所以不能铺满。

编程实现：判断草席能否铺满

python

def can_pave_carpet(rows, cols, missing_positions):
    """
    rows: 房间行数
    cols: 房间列数
    missing_positions: 缺失格子的坐标列表（如[(0,0), (7,7)]）
    返回：能否用1×2草席铺满（True/False）
    """
    # 步骤1：计算总格子数（减去缺失格子）
    total = rows * cols - len(missing_positions)
    if total % 2 != 0:
        return False  # 总格子数为奇数，肯定不能铺满（每块草席占2格）
    # 步骤2：计算黑格和白格的数量（染色规则：(i+j)偶数→黑格，奇数→白格）
    black = 0
    white = 0
    for i in range(rows):
        for j in range(cols):
            if (i, j) in missing_positions:
                continue  # 跳过缺失格子
            if (i + j) % 2 == 0:
                black += 1
            else:
                white += 1
    # 步骤3：草席需要黑格=白格
    return black == white

# 测试：8×8房间，缺失(0,0)和(7,7)→black=30，white=32→返回False
print(can_pave_carpet(8, 8, [(0,0), (7,7)]))  # 输出False
# 测试：8×8房间，缺失(0,0)和(0,1)→black=31，white=31→返回True
print(can_pave_carpet(8, 8, [(0,0), (0,1)]))  # 输出True

这个例子的核心是 “用染色法创造余数条件”—— 把覆盖问题转化为 “黑格和白格数量是否相等”（余数 0），从而用简单的计数判断解决。

五、编程实战：余数的高频场景总结

我们梳理一下编程中余数的常见用法，结合代码片段让你直接复用：

1. 循环任务调度（按周期执行）

比如 “每 7 天执行一次备份任务”，判断今天是否需要执行：

python

def need_execute(task_cycle, current_day):
    """
    task_cycle: 任务周期（天）
    current_day: 当前天数（从0开始）
    返回：是否需要执行任务
    """
    return current_day % task_cycle == 0

# 测试：周期7天，第7天、14天→执行
print(need_execute(7, 7))  # 输出True
print(need_execute(7, 10)) # 输出False

2. 数组分组（按余数分配）

把长度为 100 的数组分成每组 5 个元素的子数组：

python

def group_array(arr, group_size):
    groups = {}
    for idx, num in enumerate(arr):
        group_idx = idx // group_size  # 组索引（0,1,...）
        # 用余数判断是否是组内最后一个元素（可选）
        is_last_in_group = (idx + 1) % group_size == 0
        if group_idx not in groups:
            groups[group_idx] = []
        groups[group_idx].append(num)
    return list(groups.values())

# 测试：数组[0-9]，每组3个→[[0,1,2], [3,4,5], [6,7,8], [9]]
arr = list(range(10))
print(group_array(arr, 3))  # 输出[[0,1,2], [3,4,5], [6,7,8], [9]]

3. 哈希表分组（余数作为哈希键）

用余数实现简单的哈希表，把数据分到不同桶（bucket）中，提高查询效率：

python

class SimpleHashTable:
    def __init__(self, bucket_count):
        self.bucket_count = bucket_count
        self.buckets = [[] for _ in range(bucket_count)]
    
    def hash_func(self, key):
        # 用余数作为哈希键（简化版，实际会更复杂）
        return key % self.bucket_count
    
    def add(self, key, value):
        bucket_idx = self.hash_func(key)
        self.buckets[bucket_idx].append((key, value))
    
    def get(self, key):
        bucket_idx = self.hash_func(key)
        for k, v in self.buckets[bucket_idx]:
            if k == key:
                return v
        return None

# 测试：哈希表有3个桶，添加key=5（5%3=2）、key=8（8%3=2）→都在桶2
hash_table = SimpleHashTable(3)
hash_table.add(5, "apple")
hash_table.add(8, "banana")
print(hash_table.get(5))  # 输出apple
print(hash_table.get(8))  # 输出banana

六、小结：余数是编程的 “简化神器”

今天我们一起拆解了余数的核心用法：

1. 周期性问题：用余数把大数字压缩到周期范围内（如星期计算、乘方个位）；
2. 奇偶性判断：用余数 0/1 解决数据校验、路径判断（如奇偶校验、欧拉路径）；
3. 覆盖 / 分组问题：用染色法 + 余数判断是否满足覆盖条件（如铺设草席）；
4. 高效计算：用余数实现循环调度、哈希分组，提升代码效率。

余数的本质，是 “把复杂问题转化为有限条件的判断”—— 计算机最擅长处理有限范围的问题，余数正好帮我们搭建了 “复杂” 与 “有限” 之间的桥梁。

下一篇我们将学习 “数学归纳法”—— 它和余数的周期性结合，能帮我们证明 “无限循环的正确性”（比如用归纳法证明 “星期的周期永远是 7”），还能解决递归、迭代中的 “无限步骤” 问题。

如果你在编程中用余数解决过有趣的问题（比如游戏中的地图循环、数据分片），欢迎在评论区分享！