Python实现枚举算法——一波三折的优化

#头条创作挑战赛#昨天看到这样一个例子，一辆车肇事逃逸，现场有三个目击证人，第一个说我看到车牌的前两位数字一样，第二个说我看到车牌的后两位数字一样，但和前面的数字不同，第三个说车牌的四位数刚好等于一个数的平方。根据以上信息找出符合条件的四位数车牌号。

书上给出的算法是，首先列举前两位所有可能的数字（从0到9），然后在此基础上列举后两位所有的可能（从0到9），得到所有可能的四位数，再逐一判定这些四位数是否符合条件，条件当然就是该四位数等于某个数的平方。代码如下。

import time     #导入time库，测试一下该程序的效率
flog = 0        #设置一个标志，用来判断是否找到目标值
start1 = time.perf_counter()    #记录程序开始运行时间
for i in range(10):        #从0到9枚举所有可能的值，这里是前两位
    if flog:               #判断是否找到目标值，如果找到结束循环
        break
    for j in range(10):    #从0到9枚举后两位所有可能的值
        if flog:           #判断是否找到目标值，如果找到结束循环
            break
        if i != j:         #判断是否满足前两位数不等于后两位，
            k = 1000 * i + 100 * i + 10 * j + j #如果符合，给出所有可能的四位数
            for temp in range(32, 100): #列举完全平方数是四位数的所有数
                if temp * temp == k:    #判断该四位数是否等于完全平方数
                    print(k)            #输出符合条件的四位数
                    flog = 1            #把标志设置为已找到
                    break               #结束当前循环
end1 = time.perf_counter()    #记录程序运行结束的时间
print(end1 - start1)          #输出程序执行时间

找到的四位数：7744

程序运行时间：0.0008686760011187289

如果没有break，最外层循环将执行10次，每一次外层循环第二层循环都将执行10次，第二层循环执行一次最内层循环将执行68次（100-32=68，循环只在满足外层i不等于第二层j的条件下执行），所以该程序并没有执行10*10*68=6800次，而是10*9*68=6120次。每一层循环都要判断是否找到目标值，找到的话用break终止循环（break只能终止当前层的循环）

程序运行过程如下：

i: 0 j: 1 k: 11

i: 0 j: 2 k: 22

i: 0 j: 3 k: 33

……

i: 0 j: 9 k: 99

i: 1 j: 0 k: 1100

i: 1 j: 2 k: 1122 这里跳过了1111，因为前后不能相等

……

i: 7 j: 4 k: 7744

7744 如果使用break的话，那么程序运行到此为止。

i: 7 j: 5 k: 7755

i: 7 j: 6 k: 7766

……

i: 8 j: 6 k: 8866

i: 8 j: 7 k: 8877

i: 8 j: 9 k: 8899

……

i: 9 j: 8 k: 9988

本题是不是一定要使用三层嵌套循环？能否对程序改进优化呢？下面尝试从找出的完全平方数中寻找符合条件的答案，也就是从第三个条件出发去找符合第一、二个条件的值，程序如下所示。

import time   #导入时间库
p=[i for i in range(4)]   #初始化列表p，p中用来存放可能的四位数中每一位的数值
start=time.perf_counter() #记录程序开始运行时间
for i in range(32,100):   #枚举所有完全平方后是四位数的
    t=i*i                 #计算出所有可能的四位数
    for j in range(4):    #依次取出组成四位数的每一位数
        p[j]=t%(10**(j+1))//(10**j)  #通过求余加整除的方式得出每一位
    if p[0]==p[1] and p[2]==p[3] and p[0]!=p[2]: #判断前两位相同，并且后两位相同，并且前后不同的四位数
        print(t)          #输出符合条件的四位数
        break             #结束循环
end=time.perf_counter()   #记录程序结束时间
print(end-start)          #输出所用时间

找到的四位数：7744

程序运行时间：0.0002392329988651909

如果没有break语句，该程序应该执行272次，外层循环执行68次，每执行一次内层循环执行4次，68*4=272。

程序还能不能进一步优化改进呢？还是可以的，借助字符串实现快速查找和比对，而不用执行内循环，代码如下所示。

import time   #导入时间库
start=time.perf_counter()  #记录程序开始运行时间
for i in range(32,100):    #依次读取每一个经过完全平方可以得到四位数的值
    t=i*i                  #计算得到每一个四位的完全平方数
    t1=str(t)              #把四位数值转化为字符串
    if t1[0]==t1[1] and t1[2]==t1[3] and t1[0]!=t1[2]: #通过字符切片判断前两位相同，
    #后两位相同，但前后不同的数
        print(t)           #输出符合结果的四位数
        break              #结束循环
end=time.perf_counter()    #记录程序结束时间
print(end-start)           #输出程序运行时间

找到的四位数：7744

程序运行时间：4.287200135877356e-05

这个程序只有一层循环68次，每执行一次都需要使用Python内置的字符串操作，不过运行时间是三个程序中最短的。