Write a program triples_2.py that finds all triples of consecutive positive three-digit integers each of which is the sum of two squares, that is, all triples of the form (n,n+1,n+2) such that:
n, n+1 and n+2 are integers at least equal to 100 and at most equal to 999;
each of n, n+1 and n+2 is of the form a^2 + b^2
.
Hint: As we are not constrained by memory space for this problem, we might use a list that stores an integer for all indexes n in [100,999], equal to 1 in case n is the sum of two squares, and to 0 otherwise. Then it is just a matter of finding three consecutive 1's in the list. This idea can be refined (by not storing 1s, but suitable nonzero values) to not only know that some number is of the form a^2 + b^2, but also know such a pair (a,b)...The sample output is indicative only when it comes to the decompositions into sums of squares, as such decompositions are not unique.
If you are stuck, but only when you are stuck, then use triple_2_scaffold.py.
# 我的解法
#写的有点久了，边界是考虑一下➕算一算得出的
#有一个问题是题目要求n，n+1，n+2只是一个平方数和，但一个数可能有很多平方数和组合，最终又有打印要求，只能当作锻炼找找规律写一写，不然这种打印平方和的数的规律也应该是在题目中有所讲明的，这里是更靠近的两个数的平方和，所以更新的时候想着一方从大到小，另一方从小到大，边界可算可试，让他们在刷新过程中聚拢到目的值
# Finds all triples of consecutive positive three-digit integers
# each of which is the sum of two squares.
sums_of_two_squares = [None] * 1_000
def nb_of_consecutive_squares():
L=[]
for i in range(31,7,-1):#31是双位数得三位数平方得最大值
for j in range(0,24):
x=i*i+j*j
if x<999 and j<=i:
sums_of_two_squares[x]=f'{j}^2+{i}^2'
#else:
#break
for i in range(100,998):
if sums_of_two_squares[i]!=None and sums_of_two_squares[i+1]!=None and sums_of_two_squares[i+2]!=None:
L.append((i,i+1,i+2))
L.sort()
#print(L)
for i in range(len(L)):
print(f'{L[i]} (equal to ({sums_of_two_squares[L[i][0]]}, {sums_of_two_squares[L[i][1]]}, {sums_of_two_squares[L[i][2]]})) is a solution.')
nb_of_consecutive_squares()
#马丁解法
#Finds all triples of consecutive positive three-digit integers each of which is the sum of two squares.
def nb_of_consecutive_squares(n):#None返回false，有值返回true，not取反
if not sums_of_two_squares[n]:
return 0
if not sums_of_two_squares[n + 1]:
return 1
if not sums_of_two_squares[n + 2]:
return 2
return 3
# The largest number whose square is a 3-digit number.
max = 31 #马丁的程序是规规矩矩，习惯太好，可读性代码，包括命名规范，10句缩一句～
# For all n in [100, 999], if n is found to be of the form a^2 + b^2
# then sums_of_two_squares[n] will be set to (a, b).
# Note that there might be other decompositions of n into a sum of 2 squares;
# we just recall the first decomposition we find.
# Also note that we waste the 100 first elements of the array;
# we can afford it and this choice makes the program simpler.
sums_of_two_squares = [None] * 1_000
for i in range(max + 1):#这种解法其实思路更简单，不断更新中也是聚拢到相近值了
for j in range(i, max + 1):
n = i * i + j * j
if n < 100:
continue
if n >= 1_000:
break
sums_of_two_squares[n] = i, j
for n in range(100, 1_000):
i = nb_of_consecutive_squares(n)
if i < 3:
# There is no potential triple before n + i + 1;
# the loop will increment n by 1.
n += i
continue
print(f'({n}, {n + 1}, {n + 2}) (equal to ('
f'{sums_of_two_squares[n][0]}^2+{sums_of_two_squares[n][1]}^2, '
f'{sums_of_two_squares[n + 1][0]}^2+{sums_of_two_squares[n + 1][1]}^2, '
f'{sums_of_two_squares[n + 2][0]}^2+{sums_of_two_squares[n + 2][1]}^2'
')) is a solution.'
)
# We assume we could have two solutions of the form
# (n, n + 1, n + 2) and (n + 1, n + 2, n + 3)
# (but as the solution shows, this never happens...),
# hence n is incremented by only 1 in the next iteration of the loop.
# We could avoid checking that sums_of_two_squares[n + 1] and
# sums_of_two_squares[n + 2] are not equal to 0, but why make the program
# more complicated for no significant gain?
屏幕快照 2019-04-03 上午11.37.26.png
网友评论