前言

自守数也是一个很容易用编程解决的数学问题，不过，教材提到的一个点，值得深入研究。

问题

计算指定范围内的所有自守数

名词解释

自守数，指一个数平方结果的后几位，等于这个数本身。如 $25\times25=625$25×25=625, $625$625的后两位等于乘数25，所以是一个自守数。

编程思路

1. 很容易发现，一个数是几位数，那么就得截取乘积的后几位数，所以，得编写确定一个数位数的子函数
2. 提取乘积的后几位，可以利用上一篇博客提取特定位数的方法
3. 直接比较验证

实现代码

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-04-06 12:40:29
# @Author  : Promise ([email protected])
# @Link    : ${link}
# @Version : $Id$

import time


# 自守数，就是一个数平方结果的后几位，等于自身
# 编程思路：1）读取数是几位数 k
#          2）然后取余 10**k
# 编写判断位数的函数
def bitJudge(num):
    temp = num
    bit = 0
    while temp > 0:  # 至少是个位数
        bit += 1
        temp //= 10  # 减少一位
    return bit


# 主函数
def findAutomorphic(maxLimit):
    count = 0
    for i in range(maxLimit):
        bit_count = bitJudge(i)
        lastBit = (i**2) % (10**bit_count)  # 有几位就取余几位，如果是两位数，就取余 10^2 = 100
        if lastBit == i:
            print('第', count+1, '个自守数是：', i)
            count += 1


# 运行
start = time.process_time()
findAutomorphic(200000)
end = time.process_time()
print('运行时间t=', end - start)

运行结果

代码分析

1. 理解子函数 bitJudge(num):，能进入while循环，说明数字至少是个位的
2. 一个数是几位数，那么就要从乘积提取后几位数，理解lastBit = (i**2) % (10**bit_count) # 有几位就取余几位，如果是两位数，就取余 10^2 = 100，如 $625 \% 10^2 = 25$625%102=25。
3. 这里只有唯一一个for循环，同时要处理的操作很少，所以即使是20万，运行依然很快。

拓展

在教材里提到一种情况，假如我们要求的数，位数非常非常大，比如要占用64bit来存储，那么这时候，直接求这个数的平方，对于计算机来说，是完全不可能的。于是，教材提出了类比于手写运算的方法来求解, 如下图。图片里的文字，也做了详细的介绍。通过这种方法，就极大的减小了数字的规模。本来我是不想写这些的，但是考虑到，我写博客的目的是为了学习算法啊，这么好的锻炼机会怎么可以偷懒……

相应的编程思路

1. 判断输入的数$num$num是几位数
2. 根据位数，建立一个对应长度的数组num_list，分别存储各个位（个十百），从索引0开始，这样的好处是，每个位的索引就是它权重，num_list[j] $\times 10^j$×10j，就取出了第$j+1$j+1位的数， 如数组$[5,2,6]$[5,2,6]（对应数字 $625$625），$6\times10^2=600$6×102=600
3. 根据上图最下面总结经验，依次相乘即可

实现代码

# 编写判断位数的函数
def bitJudge(num):
    temp = num
    bit = 0
    while temp > 0:  # 至少是个位数
        bit += 1
        temp //= 10  # 减少一位
    return bit

# 计算乘积的主函数，重点理解！！！
def GetTimesValue(num, bit_count):
    num_list = [0]*bit_count
    # 提取各个位，依次存取
    temp = num
    i = 0
    while temp > 0:
        num_list[i] = temp % 10
        i += 1  # 索引加1
        temp //= 10
    # 出来后，就把数字拆分在数组了,然后按规律求和
    result = 0
    for j in range(bit_count):
        a = num % (10**(bit_count-j))  # 取出被乘数
        b = num_list[j]*(10**j)  # 取出乘数，依次是个位，十位等
        result = (result + a * b) % (10**bit_count)
    return result

def findAutomorphicInbit(maxLimit):
    count = 0
    for i in range(maxLimit):  # 有必要把求解的过程包装成子函数
        bit_count = bitJudge(i)  # 判断几位数是要的，取乘积的后几位，就是 %10^(bit_count)
        timeValue = GetTimesValue(i, bit_count)
        if timeValue == i:
            print('第', count+1, '个自守数是：', i)
            count += 1

运行效果

代码分析

1. 重点理解a = num % (10**(bit_count-j)) # 取出被乘数，以625为例，一开始我们要计算 $625\times5$625×5，用$625 \% 10^3=625$625%103=625，这里巧妙的利用了取余的特点；下一次迭代，j 变成1，就变成$625 \% 10^2=25$625%102=25,这样就符合图片中要求的取数字了
2. b = num_list[j]*(10**j) # 取出乘数，这一步中规中矩，就是根据权重把数取出来，以$625$625为例，就是按$600,20,5$600,20,5依次把数取出来
3. result = (result + a * b) % (10**bit_count), 最后取余$10^{bit-count}$10bit−count次方，跟第一个程序是同一个道理
4. 增加了太多中间步骤，程序严重变慢；不过，这种方法可以在第一种方法失效的时候，发挥作用；有所得，必有所失吧。（好像很有道理……）

教材的方法

非常的不直观，差评！于是才有了上面我自己写的程序，我还没验证它是否效率高点，但非常不推荐程序像它那样，因为需要费很大功夫才能看懂……

总结

对于编写数量级不大的数字，自守数问题是很简单的。很感谢教材给了一个重要的提示，让我去考虑数字规模很大的情况，虽然，通过运行，我感觉变慢了……但说不定这种处理思想将来某一天会运用到呢……哈哈，人不能太短视啊、
另外，我差点走了误区……我写博客，初衷是为了督促自己持续写代码……然而，一开始，我看到教材的拓展写法，觉得麻烦，竟然想跳过……
再次强调，不能为了写博客而写博客，写代码，掌握编程思想才是核心！