鱼C论坛

 找回密码
 立即注册
查看: 3282|回复: 12

[技术交流] 小练习: 20170821 隐藏的平方数

[复制链接]
发表于 2017-8-20 19:41:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-8-29 08:08 编辑

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。

什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives

这里已经有了500余题。


                               
登录/注册后可看大图


要求:

以python语言完成,如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成,即8.28 10:00之前,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。题目不难,大家看看谁的效率高。

-- 回帖需写明解题思路,鼓励在程序中加上注释 --

-- 一些鱼油反映题目有些过难,为此略过一部分偏难的题目 --


                               
登录/注册后可看大图


题目:

找出唯一一个符合如下条件的数字:它的平方是具有 1_2_3_4_5_6_7_8_9_0 形式的数。

每个 _ 都代表了单个数字。


本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-8-20 23:09:29 | 显示全部楼层
这题好像以前在我的小练习中有出过,思路主要是分析这个数字的特点:某个数的平方以0结尾,这个数只可能也是0,而且这个平方数的末尾2位都是0,那么平方数倒数第3位是9的数,只可能是3或者7.
这个平方数最大可能是1929394959697989990,最小是1020304050607080900,开根以后得1389026623和1010101010,这样就很简单了。
  1. #print(1929394959697989990**0.5, 1020304050607080900**0.5)
  2. for i in range(3890266,101010,-1):
  3.         t1 = str((1000000000+i*100+30)**2)
  4.         t2 = str((1000000000+i*100+70)**2)
  5.         if t1[0::2] == '1234567890':
  6.                 print(1000000000+i*100+30, t1)
  7.                 break
  8.         if t2[0::2] == '1234567890':
  9.                 print(1000000000+i*100+70, t2)
  10.                 break
复制代码

1389019170 1929374254627488900

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-21 02:44:07 | 显示全部楼层
  1. from math import sqrt

  2. MAX = int(sqrt(1929394959697989990))  # 最大可能值
  3. MIN = int(sqrt(1020304050607080900))  # 最小可能值

  4. # 最大可能值和最小可能值比较, 从最大可能值开始会快很多! 因为结果接近
  5. for num in range(MAX, MIN-1, -1):
  6.     tmp = str(num*num)

  7.     # 判断是否是1_2_3_4_5_6_7_8_9_0
  8.     cnt = 2
  9.     for each in tmp[2::2]:
  10.         if each != str(cnt):
  11.             break
  12.         cnt = (cnt+1) % 10

  13.     # 是的话就是结果了
  14.     if cnt == 1:
  15.         print(num, tmp)
  16.         break

  17.    

复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-21 19:50:19 | 显示全部楼层
笨办法哈哈哈哈,下次试试递归~

  1. test1 = int(1020304050607080900 ** 0.5)
  2. test2 = int(1929394959697989990 ** 0.5)
  3. def no1():
  4.     num=0
  5.     for i in range(test1, test2, 10):
  6.         if str(i**2)[num]=='1':
  7.             num +=2
  8.             if str(i**2)[num]=='2':
  9.                 num +=2
  10.                 if str(i**2)[num]=='3':
  11.                     num +=2
  12.                     if str(i**2)[num]=='4':
  13.                         num +=2
  14.                         if str(i**2)[num]=='5':
  15.                             num +=2
  16.                             if str(i**2)[num]=='6':
  17.                                 num +=2
  18.                                 if str(i**2)[num]=='7':
  19.                                     num +=2
  20.                                     if str(i**2)[num]=='8':
  21.                                         num +=2
  22.                                         if str(i**2)[num]=='9':
  23.                                             num +=2
  24.                                             if str(i**2)[num]=='0':
  25.                                                 print(i, i**2)
  26.                                             else:
  27.                                                 num=0
  28.                                                 continue
  29.                                         else:
  30.                                             num=0
  31.                                             continue
  32.                                     else:
  33.                                         num=0
  34.                                         continue
  35.                                 else:
  36.                                     num=0
  37.                                     continue
  38.                             else:
  39.                                 num=0
  40.                                 continue
  41.                         else:
  42.                             num=0
  43.                             continue
  44.                     else:
  45.                         num=0
  46.                         continue
  47.                 else:
  48.                     num=0
  49.                     continue
  50.             else:
  51.                 num=0
  52.                 continue
  53.         else:
  54.             num=0
  55.             continue
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-22 00:02:29 | 显示全部楼层
最后一位是0那倒数第二位也是0
然后是9 那开方后  末尾为3或7
temp=1020304050607080900
#for i in range(10):
  #  temp=i*10**(20-i*2)+temp   
def panduan(shu):
    c=True
    for j in range(1,17,2):
        if str(shu)[j-1]!=str(int(j/2+1)):
            c=False
            break
    if c==False:
        return(False)
    else:
        return(True)

for i in range(10):
    for j in range(10):   
        for k in range(10):   
            x=temp+i*10**17+j*10**15+k*10**13
            y=int(x/10**12+1)*10**12
            m=int(x**(1/2)/100)*100+30
            n=int(y**(1/2)/100)*100+30            
            for kk in range(m,n,100):
                a=kk**2
                b=panduan(a)        
                if b==True:
                    print(a)
                    print(a**0.5)
                    break   
            if b==True:
                break         
        if b==True:
            break
    if b==True:
        break
            
   
for i in range(10):
    for j in range(10):      
        for k in range(10):   
            x=temp+i*10**17+j*10**15+k*10**13
     
            y=int(x/10**12+1)*10**12
            m=int(x**(1/2)/100)*100+70
            n=int(y**(1/2)/100)*100+70            
            for kk in range(m,n,100):
                a=kk**2
                b=panduan(a)        
                if b==True:
                    print(a)
                    print(a**0.5)
                    break   
            if b==True:
                break      
        if b==True:
            break
    if b==True:
        break
      
答案  1929374254627488900
           1389019170

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-22 08:06:13 | 显示全部楼层
本帖最后由 gunjang 于 2017-8-24 21:12 编辑

正好是euler206
  1. from math import sqrt
  2. import time
  3. amax = 1929394959697989990
  4. amin = 1020304050607080900
  5. #print(int(sqrt(amin)), int(sqrt(amax))) #1010101010 1389026623 10^9

  6. st = time.time()

  7. waitinglist=[]
  8. for a in range(10):
  9.         if a*a % 10 == 0:
  10.                 waitinglist.append(a)
  11. maxDigit = len(str(int(sqrt(amin))))-1
  12. if maxDigit%2 == 0: #9
  13.         maxDigit -= 1

  14. #n=a+b ==>n^2 = a^2+2ba+b^2
  15. #low 3 digit
  16. #let b = n%1000, a=(n//1000)*1000
  17. #so a^2 's lower 3 digit is n^3 's lower 3 digit
  18. for digit in range(3, maxDigit+1, 2):
  19.         wl = []
  20.         for x in waitinglist:
  21.                 for b1 in range(0, 100):
  22.                         b = b1*(10**(digit-2))+x
  23.                         if (b*b % 10**digit)//10**(digit-1) == (10 - digit//2):
  24.                                 wl.append(b)
  25.         waitinglist = wl
  26.         #print(digit,len(waitinglist)) #24000

  27. def check(n):
  28.         n = str(n)
  29.         if (len(n)==19):
  30.                 for i in range(5+1): #67890 have checked
  31.                         if n[i*2]!=str(i+1):
  32.                                 return False
  33.         else:
  34.                 return False
  35.         return True

  36. r = 0
  37. for h in range(int(sqrt(amin))//10**maxDigit, int(sqrt(amax))// 10**maxDigit +1):
  38.         for x in waitinglist:       
  39.                 b = h* 10**9 + x
  40.                 if check(b*b):
  41.                         print(b, b*b)
  42.                         r = b
  43.                         break
  44.         if r != 0:
  45.                 break
  46. #1389019170 1929374254627488900
  47. print(time.time()-st) #0.75s
复制代码

思路:直接穷举法太费时间了,可以用特性减少搜索数量
(a+b)^2=a^2+2ba+b^2
n=a+b,
假设b是n的个数部分,(n//10)
则a^2+2ba的个位数肯定是0,所以决定n^2的个位数部分的实际上就是b^2
同理,决定最后3位的b=n//1000
因为n最大为10位数,所以可以求出n^2符合9位数的b的候选列表(b<1E9)
接下来就是暴力穷举,a只有11-13三个选择(*10^9)

1389019170 1929374254627488900

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-22 09:56:55 | 显示全部楼层
笨方法,速度7秒多。。。
  1. #最后一位是0,只有0的平方是0,可以确定后三位是900
  2. #只有30和70的平方才是900,所以只要验证这2个数字结尾的数就可以了

  3. ss = '1_2_3_4_5_6_7_8_9_0'
  4. temp = str(int(int(ss.replace('_','0'))**0.5))
  5. x1 = int(temp[:-2]+'30')
  6. x2 = int(temp[:-2]+'70')
  7. y = int(int(ss.replace('_','9'))**0.5+1)


  8. for i in range(x1,y,100):
  9.     if str(i**2)[::2]=='1234567890':
  10.         print(i)
  11.         break
  12. for i in range(x2,y,100):
  13.     if str(i**2)[::2]=='1234567890':
  14.         print(i)
  15.         break
复制代码


%time %run olxxx.py
1389019170
Wall time: 7.26 s
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-22 22:48:16 | 显示全部楼层
本帖最后由 夏天和大熊 于 2017-8-22 23:19 编辑

结果是 1929374254627488900  因为结果最后1位是0,所可以肯定平方之前的数最后一位是0,那么结果的倒数第二位也为0。那么平方之前的数倒数第二位只可能为3和7,缩小了一些计算的范围,勉强算是没超过时间。暂时还没构思到这样推理下去能否把计算的时间再做精简,因为在这之后可能的结果出现了分支而且涉及到了进位。
  1. import re
  2. import time

  3. def find():
  4.     for i in range(10101010, 13890265, 1):
  5.         nums = re.findall(r'1\d2\d3\d4\d5\d6\d7\d8\d9', str((i*10+3)**2)) + \
  6.                re.findall(r'1\d2\d3\d4\d5\d6\d7\d8\d9', str((i*10+7)**2))
  7.         if nums:
  8.             break
  9.     return nums[0] + '00'


  10. if __name__ == '__main__':
  11.     t1 = time.time()
  12.     print(find())
  13.     t2 = time.time()
  14.     print(t2 - t1)
复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-23 14:24:03 | 显示全部楼层
本帖最后由 WelanceLee 于 2017-8-23 14:29 编辑
  1. def match(a):
  2.     s = str(a)
  3.     for i in range(0, 17, 2):
  4.         if s[i]  != str(i//2 + 1):
  5.             return False
  6.     return True

  7. for i in range(1*10**8 + 7, 15*10**7, 10):
  8.     if match(i**2):
  9.         print(i*10)
  10.         break

  11. if i == 15*10**7-1:
  12.     for i in range(1*10**8 + 3, 15*10**7, 10):
  13.         if match(i**2):
  14.             print(i*10)
  15.             break
  16. else:
  17.     pass
复制代码

答案是1389019170

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-23 16:39:23 | 显示全部楼层
本帖最后由 chunchun2017 于 2017-8-23 16:50 编辑

答案是:1389019170,它的平方是1929374254627488900
===============================================================
要求的数记为x,x^2后末位是0,所以一定是两个0,因此为缩小范围,可以计算1_2_3_4_5_6_7_8_9是x/10的平方,
10203040506070809<=1_2_3_4_5_6_7_8_9<=19293949596979899
求平方根后,是(101010101,138902662),这个区间,由于(x/10)^2末位是9,所以x/10末位是3或者7
因此区间可以变成(101010103,138902657),
===================================================================
  1. list0 = range(101010107,138902657,10)
  2. list1 = range(101010103,138902653,10)
  3. list2 = []
  4. for i in list0:
  5.      temp = i*i
  6.      if ((temp//100)%10==8 and (temp//10000)%10==7 \
  7.          and (temp//1000000)%10==6 and (temp//100000000)%10==5 \
  8.          and (temp//10000000000)%10==4 and (temp//1000000000000)%10==3\
  9.          and  (temp//100000000000000)%10==2):
  10.          list2.append(i)
  11.          break
  12. if(len(list2)==0):
  13.     for i in list1:
  14.          temp = i**i
  15.          if ((temp//100)%10==8 and (temp//10000)%10==7 \
  16.              and (temp//1000000)%10==6 and (temp//100000000)%10==5 \
  17.              and (temp//10000000000)%10==4 and (temp//1000000000000)%10==3\
  18.              and  (temp//100000000000000)%10==2):
  19.              list2.append(i)
  20.              break
  21. print(list2[0]*10)
复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-24 00:14:20 | 显示全部楼层
本帖最后由 达锅 于 2017-8-24 23:58 编辑

答案:1389019170
知道答案以后,直接从大到小暴力破解,秒出

  1. import time as t
  2. tt=t.time()
  3. #暴力破解
  4. maxx=int(19293949596979899**0.5)
  5. minn=int(10203040506070809**0.5)
  6. xl='123456789'
  7. for i in range(maxx,minn,-1):#倒序秒出
  8.     if str(i*i)[::2]==xl:
  9.         print(i*10)
  10.         break
  11. print(t.time()-tt)
复制代码


另外一种思路:由平方数性质可知,最后两位肯定为00,倒数第三位为3或者7
无标题.png
因为低位数的平方数不受高位数的变动影响,即个位数确定后,十位数及以上的怎么变动都不会影响个位数
所以先第一步先确定个位数为3或者7,然后找出003-993、007-997的平方数中百位数为8的,记录下来,
然后再找出万位数为7的,以此类推
最后再找出符合123456789的
速度也不错,0.4秒左右


  1. import time as t
  2. tt=t.time()

  3. xl0=['3','7']

  4. def midd(n,t):
  5.     return ('0'*(2-len(str(j)))+str(j)+i \
  6.      for i in xl0 \
  7.          for j in range(1,100) \
  8.              if str(int(str(j)+i)**2)[n]==t)
  9. xl0=midd(-3,'8')
  10. xl0=midd(-5,'7')
  11. xl0=midd(-7,'6')


  12. def fin():
  13.     xl='123456789'
  14.     for i in xl0:
  15.         for j in range(1,100):
  16.             if str(int(str(j)+i)**2)[::2]==xl:#匹配全部比匹配部分快,而且匹配部分结果不对……
  17.                 return str(j)+i+'0'
  18.         
  19. print((fin()))

  20. print(t.time()-tt)
复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-8-24 11:18:55 | 显示全部楼层
1389019170  T.T 50s  
code]import math,time
def calc():
    '''找出唯一一个符合如下条件的数字:它的平方是具有 1_2_3_4_5_6_7_8_9_0 形式的数。'''
    number = int(math.sqrt(1020304050607080900))    #初始数字 最小的平方数开方
    number //= 10
    number *= 10   #转换为10的倍数  因为平方位数是0 该数字一定是10的倍数
   
    while 1:
        result = number**2
        list1 = list(str(result))
        if list1[::2] == ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']:
            print(number)
            break
        number += 10
start = time.clock()
calc()
end = time.clock()
print('cost: %s s' %(end - start))[/code]

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-26 15:20:27 | 显示全部楼层
  1. import time
  2. f=int(19293949596979899**0.5)
  3. print(f)
  4. j=f%10
  5. if 7<=j:
  6.     f=f-j+7
  7.     sort=True
  8. elif 3<=j:
  9.     f=f-j+3
  10.     sort=False
  11. else:
  12.     f=f-j-3
  13.     sort=True
  14. an=False
  15. if not sort:
  16.     temp=str(i**2)
  17.     if (temp[2],temp[4],temp[6],temp[8],temp[10],temp[12],temp[14],temp[16])==('2','3','4','5','6','7','8','9'):
  18.         an=True
  19.     else:
  20.         f=f-6
  21. if not an:
  22.     while True:
  23.         temp=str(f**2)
  24.         if (temp[2],temp[4],temp[6],temp[8],temp[10],temp[12],temp[14],temp[16])==('2','3','4','5','6','7','8','9'):
  25.             break
  26.         f-=4
  27.         temp=str(f**2)
  28.         if (temp[2],temp[4],temp[6],temp[8],temp[10],temp[12],temp[14],temp[16])==('2','3','4','5','6','7','8','9'):
  29.             break
  30.         f-=6

  31. print(f*10)

  32. print(time.process_time())
复制代码

第一个必定是1,最后一个是0,倒数第二个是3或7

1389019170

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 12:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表