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内置的字符串操作，不过运行时间是三个程序中最短的。