小练习： 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 形式的数。

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

jerryxjr1220 · 发表于 2017-8-20 23:09:29

这题好像以前在我的小练习中有出过，思路主要是分析这个数字的特点：某个数的平方以0结尾，这个数只可能也是0，而且这个平方数的末尾2位都是0，那么平方数倒数第3位是9的数，只可能是3或者7.
这个平方数最大可能是1929394959697989990，最小是1020304050607080900，开根以后得1389026623和1010101010，这样就很简单了。

#print(1929394959697989990**0.5, 1020304050607080900**0.5)
for i in range(3890266,101010,-1):
t1 = str((1000000000+i*100+30)**2)
t2 = str((1000000000+i*100+70)**2)
if t1[0::2] == '1234567890':
print(1000000000+i*100+30, t1)
break
if t2[0::2] == '1234567890':
print(1000000000+i*100+70, t2)
break

复制代码

1389019170 1929374254627488900

zmx296689210 · 发表于 2017-8-21 02:44:07

from math import sqrt
MAX = int(sqrt(1929394959697989990)) # 最大可能值
MIN = int(sqrt(1020304050607080900)) # 最小可能值
# 最大可能值和最小可能值比较，从最大可能值开始会快很多！因为结果接近
for num in range(MAX, MIN-1, -1):
tmp = str(num*num)
# 判断是否是1_2_3_4_5_6_7_8_9_0
cnt = 2
for each in tmp[2::2]:
if each != str(cnt):
break
cnt = (cnt+1) % 10
# 是的话就是结果了
if cnt == 1:
print(num, tmp)
break

复制代码

Xlyxcar · 发表于 2017-8-21 19:50:19

笨办法哈哈哈哈,下次试试递归~

test1 = int(1020304050607080900 ** 0.5)
test2 = int(1929394959697989990 ** 0.5)
def no1():
num=0
for i in range(test1, test2, 10):
if str(i**2)[num]=='1':
num +=2
if str(i**2)[num]=='2':
num +=2
if str(i**2)[num]=='3':
num +=2
if str(i**2)[num]=='4':
num +=2
if str(i**2)[num]=='5':
num +=2
if str(i**2)[num]=='6':
num +=2
if str(i**2)[num]=='7':
num +=2
if str(i**2)[num]=='8':
num +=2
if str(i**2)[num]=='9':
num +=2
if str(i**2)[num]=='0':
print(i, i**2)
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue
else:
num=0
continue

复制代码

suloman · 发表于 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

gunjang · 发表于 2017-8-22 08:06:13

本帖最后由 gunjang 于 2017-8-24 21:12 编辑

正好是euler206

from math import sqrt
import time
amax = 1929394959697989990
amin = 1020304050607080900
#print(int(sqrt(amin)), int(sqrt(amax))) #1010101010 1389026623 10^9
st = time.time()
waitinglist=[]
for a in range(10):
if a*a % 10 == 0:
waitinglist.append(a)
maxDigit = len(str(int(sqrt(amin))))-1
if maxDigit%2 == 0: #9
maxDigit -= 1
#n=a+b ==>n^2 = a^2+2ba+b^2
#low 3 digit
#let b = n%1000, a=(n//1000)*1000
#so a^2 's lower 3 digit is n^3 's lower 3 digit
for digit in range(3, maxDigit+1, 2):
wl = []
for x in waitinglist:
for b1 in range(0, 100):
b = b1*(10**(digit-2))+x
if (b*b % 10**digit)//10**(digit-1) == (10 - digit//2):
wl.append(b)
waitinglist = wl
#print(digit,len(waitinglist)) #24000
def check(n):
n = str(n)
if (len(n)==19):
for i in range(5+1): #67890 have checked
if n[i*2]!=str(i+1):
return False
else:
return False
return True
r = 0
for h in range(int(sqrt(amin))//10**maxDigit, int(sqrt(amax))// 10**maxDigit +1):
for x in waitinglist:
b = h* 10**9 + x
if check(b*b):
print(b, b*b)
r = b
break
if r != 0:
break
#1389019170 1929374254627488900
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

小Q学Python · 发表于 2017-8-22 09:56:55

笨方法，速度7秒多。。。

#最后一位是0，只有0的平方是0，可以确定后三位是900
#只有30和70的平方才是900，所以只要验证这2个数字结尾的数就可以了
ss = '1_2_3_4_5_6_7_8_9_0'
temp = str(int(int(ss.replace('_','0'))**0.5))
x1 = int(temp[:-2]+'30')
x2 = int(temp[:-2]+'70')
y = int(int(ss.replace('_','9'))**0.5+1)
for i in range(x1,y,100):
if str(i**2)[::2]=='1234567890':
print(i)
break
for i in range(x2,y,100):
if str(i**2)[::2]=='1234567890':
print(i)
break

复制代码

%time %run olxxx.py
1389019170
Wall time: 7.26 s

夏天和大熊 · 发表于 2017-8-22 22:48:16

本帖最后由夏天和大熊于 2017-8-22 23:19 编辑

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

import re
import time
def find():
for i in range(10101010, 13890265, 1):
nums = re.findall(r'1\d2\d3\d4\d5\d6\d7\d8\d9', str((i*10+3)**2)) + \
re.findall(r'1\d2\d3\d4\d5\d6\d7\d8\d9', str((i*10+7)**2))
if nums:
break
return nums[0] + '00'
if __name__ == '__main__':
t1 = time.time()
print(find())
t2 = time.time()
print(t2 - t1)

复制代码

WelanceLee · 发表于 2017-8-23 14:24:03

本帖最后由 WelanceLee 于 2017-8-23 14:29 编辑

def match(a):
s = str(a)
for i in range(0, 17, 2):
if s[i] != str(i//2 + 1):
return False
return True
for i in range(1*10**8 + 7, 15*10**7, 10):
if match(i**2):
print(i*10)
break
if i == 15*10**7-1:
for i in range(1*10**8 + 3, 15*10**7, 10):
if match(i**2):
print(i*10)
break
else:
pass

复制代码

答案是1389019170

chunchun2017 · 发表于 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),
===================================================================

list0 = range(101010107,138902657,10)
list1 = range(101010103,138902653,10)
list2 = []
for i in list0:
temp = i*i
if ((temp//100)%10==8 and (temp//10000)%10==7 \
and (temp//1000000)%10==6 and (temp//100000000)%10==5 \
and (temp//10000000000)%10==4 and (temp//1000000000000)%10==3\
and (temp//100000000000000)%10==2):
list2.append(i)
break
if(len(list2)==0):
for i in list1:
temp = i**i
if ((temp//100)%10==8 and (temp//10000)%10==7 \
and (temp//1000000)%10==6 and (temp//100000000)%10==5 \
and (temp//10000000000)%10==4 and (temp//1000000000000)%10==3\
and (temp//100000000000000)%10==2):
list2.append(i)
break
print(list2[0]*10)

复制代码

达锅 · 发表于 2017-8-24 00:14:20

本帖最后由达锅于 2017-8-24 23:58 编辑

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

import time as t
tt=t.time()
#暴力破解
maxx=int(19293949596979899**0.5)
minn=int(10203040506070809**0.5)
xl='123456789'
for i in range(maxx,minn,-1):#倒序秒出
if str(i*i)[::2]==xl:
print(i*10)
break
print(t.time()-tt)

复制代码

另外一种思路：由平方数性质可知，最后两位肯定为00，倒数第三位为3或者7
无标题.png

因为低位数的平方数不受高位数的变动影响，即个位数确定后，十位数及以上的怎么变动都不会影响个位数
所以先第一步先确定个位数为3或者7，然后找出003-993、007-997的平方数中百位数为8的，记录下来，
然后再找出万位数为7的，以此类推
最后再找出符合123456789的
速度也不错，0.4秒左右

import time as t
tt=t.time()
xl0=['3','7']
def midd(n,t):
return ('0'*(2-len(str(j)))+str(j)+i \
for i in xl0 \
for j in range(1,100) \
if str(int(str(j)+i)**2)[n]==t)
xl0=midd(-3,'8')
xl0=midd(-5,'7')
xl0=midd(-7,'6')
def fin():
xl='123456789'
for i in xl0:
for j in range(1,100):
if str(int(str(j)+i)**2)[::2]==xl:#匹配全部比匹配部分快，而且匹配部分结果不对……
return str(j)+i+'0'
print((fin()))
print(t.time()-tt)

复制代码

运维小书童 · 发表于 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]

小剑剑 · 发表于 2017-8-26 15:20:27

import time
f=int(19293949596979899**0.5)
print(f)
j=f%10
if 7<=j:
f=f-j+7
sort=True
elif 3<=j:
f=f-j+3
sort=False
else:
f=f-j-3
sort=True
an=False
if not sort:
temp=str(i**2)
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'):
an=True
else:
f=f-6
if not an:
while True:
temp=str(f**2)
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'):
break
f-=4
temp=str(f**2)
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'):
break
f-=6
print(f*10)
print(time.process_time())

复制代码

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

1389019170

账号		自动登录	找回密码
密码			立即注册

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

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分