笔记11-《程序员的数学》余数的力量

目录

1. 余数的力量
2. 思考题（100 天以后是星期几）
3. 余数的力量——将较大的数字除一次就能分组
4. 思考题（10^100 天以后是星期几）
5. 乘方的思考题
6. 回顾：规律和余数的关系

余数的力量

• 奇数与偶数

  • 奇数 = 被 2 除余 1 的整数（1、3、5、7、9、11……）
  • 偶数 = 被 2 整除的整数
  • 除法就像分组，根据余数来确定属于哪个组

思考题（100 天以后是星期几）

• 题目

  • 今天是星期日，那么 100 天以后是星期几？

• 思考题答案

  • 一周有 7 天，每过 7 天循环到相同的星期数

  • 98 是 7 的倍数，因此 98 天后也是星期日

    98 天后 …… 星期日
    99 天后 …… 星期一
    100 天后 … 星期二

  • 答案：星期二

• 运用余数思考

  • 数字 0、1、2……6 分别代表星期日、星期一、星期二……星期六
  • 100 天后的星期数 = 「100 除以 7 的余数」
  • 100 ÷ 7 = 14 余 2，所以 100 天后是星期二

余数的力量——将较大的数字除一次就能分组

• 为什么数不动的时候要用余数

  • 「今天是星期日、1 天后是星期一、2 天后是星期二……」这样数到第 100 天也能答出

  • 但 100 不算大，1 亿天就数不动了 —— 即使 1 秒数 1 下，也要 3 年以上

  • 用余数则很快就能算出：100000000 ÷ 7 = 14285714 余 2

  • 余数为 2，所以 1 亿天后是星期二

  • 面对难以直接计算的庞大数字，只要发现它如何循环，就能通过余数将其降服

  • 验证一下

    #ruby
    # 用余数直接求 N 天后是星期几（0=周日, 1=周一, ... 6=周六）
    def weekday(n)
      ["星期日", "星期一", "星期二", "星期三", "星期四", "星期五", "星期六"][n % 7]
    end
    
    puts weekday(100)           # 星期二
    puts weekday(100_000_000)   # 星期二
    
    # 数到 1 亿需要多久
    seconds = 100_000_000
    puts "#{seconds / 86400.0} 天"   # 1157.4074074074074 天

思考题（10^100 天以后是星期几）

• 题目

  • 今天是星期日，那么 10^100 天以后是星期几？

• 提示：可以直接计算吗

  • 如果能像求 100 天以后那样，用 10^100 除以 7 的余数来算就好了
  • 但数字太大，计算起来相当费力，即使借助计算器也很难完成
  • 星期数思考题（1）用了星期的周期性，那么这个问题有周期性吗？找出它循环的规律

• 思考题答案

  • 不急于求 10^100，而是像 1、10、100、1000 这样依次增加 0 的个数，观察规律

    0 的个数	除法	余数
    0	1 ÷ 7 = 0 余 1	1
    1	10 ÷ 7 = 1 余 3	3
    2	100 ÷ 7 = 14 余 2	2
    3	1000 ÷ 7 = 142 余 6	6
    4	10000 ÷ 7 = 1428 余 4	4
    5	100000 ÷ 7 = 14285 余 5	5
    6	1000000 ÷ 7 = 142857 余 1	1
    7	10000000 ÷ 7 = 1428571 余 3	3
    8	100000000 ÷ 7 = 14285714 余 2	2
    9	1000000000 ÷ 7 = 142857142 余 6	6
    10	10000000000 ÷ 7 = 1428571428 余 4	4

  • 余数以 1、3、2、6、4、5 的顺序循环，星期数以一、三、二、六、四、五……的顺序循环

  • 每增加 6 个 0，星期数就相同，因此周期为 6

  • 把 0 的个数除以 6，得到的余数为 0、1、2、3、4、5 之一

  • 它们分别对应星期一、星期三、星期二、星期六、星期四、星期五（没有星期日）

  • 100 个 0：100 ÷ 6 = 16 余 4，对应星期四

  • 用代码验证这个周期

    #ruby
    # 10^k 除以 7 的余数，观察周期
    r = 1
    (0..12).each do |k|
      puts "10^#{k} 除以 7 余 #{r}" if k <= 10
      r = (r * 10) % 7
    end
    
    # 10^100 天以后：100 个 0，100 mod 6 = 4 -> 余数 4 -> 星期四
    days = 10**100
    puts "10^100 除以 7 余 #{days % 7}"
    names = ["星期日","星期一","星期二","星期三","星期四","星期五","星期六"]
    puts "10^100 天以后是 #{names[days % 7]}"

输出：

10^0 除以 7 余 1
10^1 除以 7 余 3
10^2 除以 7 余 2
10^3 除以 7 余 6
10^4 除以 7 余 4
10^5 除以 7 余 5
10^6 除以 7 余 1
10^7 除以 7 余 3
10^8 除以 7 余 2
10^9 除以 7 余 6
10^10 除以 7 余 4
10^100 除以 7 余 4
10^100 天以后是 星期四

乘方的思考题

• 思考题（1 234 567 的 987 654 321 次方）

  • 求 1234567 的 987654321 次方的个位数是多少？

• 提示：通过试算找出规律

• 思考题答案

  • 只关心个位数，也就是除以 10 的余数

  • 依次试算 7 的各次幂的个位数

    n	7^n 的个位数
    1	7
    2	9
    3	3
    4	1
    5	7

  • 周期为 4：7、9、3、1 循环

  • 987654321 ÷ 4 = 246913580 余 1

  • 余数 1 对应周期里的第 1 个，即 7

  • 答案：个位数是 7

  • 代码验证

    #ruby
    # 7 的幂的个位数周期
    (1..8).each { |n| puts "7^#{n} 个位数 = #{7**n % 10}" }   # 7^1 个位数 = 7
    
    # 大指数直接用 ** 会溢出（Ruby 会给 NaN），改用模幂
    def last_digit(base, exp)
      result = 1
      b = base % 10
      e = exp
      while e > 0
        result = (result * b) % 10 if e.odd?
        b = (b * b) % 10
        e >>= 1
      end
      result
    end
    
    base, exp = 1234567, 987654321
    puts "#{base}^#{exp} 个位数 = #{last_digit(base, exp)}"   # 1234567^987654321 个位数 = 7

回顾：规律和余数的关系

• 三个思考题的共同结构

  • 100 天 → 周期 7
  • 10^100 天 → 周期 6（0 的个数）
  • 7^n 的个位数 → 周期 4
  • 都有一个循环的周期，答案 = 大数 ÷ 周期 的余数

• 余数的力量：把庞大的数字除一次就能分组

• 找规律（周期）是前提，余数是降服大数的工具