问题 61-65 参见: https://www.jianshu.com/p/ce99a41bc728
66,丢番图方程
考虑如下形式的二次丢番图方程:
x2 - Dy2 = 1
举例而言,当 D=13 时,x 的最小值出现在 6492 - 13×1802 = 1.可以断定,当 D 是平方数时,这个方程不存在正整数解.
对于 D= {2, 3, 5, 6, 7} 分别求出 x 取最小值的解,我们得到:
32 - 2×22= 1
22 - 3×12 = 1
92 - 5×42 = 1
52 - 6×22 = 1
82 - 7×32 = 1
因此,对于所有 D ≤ 7,当 D=5 时 x 的最小值最大.
对于 D ≤ 1000,求使得 x 的最小值最大的 D 值.
Python3 解答
#Pell方程解题思路
#由X^2-D*Y^2=1.可得根号D约等于X/Y.而根号D恰好可以变为连分数的形式
def GetPell(number):
sboot=number**0.5
#判断是否为完全平方数
if int(sboot)-sboot==0:
return [number]
else:
#开始计算根号D的连分数形式
P=0
Q=1
a=int(sboot)
#第0和第1个渐进分数
p=[1,a]#分子
q=[0,1]#分母
while p[1]**2-number*(q[1]**2)!=1:
#中间变量
P=a*Q-P
Q=(number-P**2)/Q
a=int((int(sboot)+P)//Q)
#渐进分数
pp=a*p[1]+p[0]#分子
qq=a*q[1]+q[0]#分母
#存储
p=[p[1],pp]
q=[q[1],qq]
return [p[1],number,q[1]]
#开始计算
x=0
d=0
for ipell in range(1001):
result=GetPell(ipell)
if len(result)==3:#排除完全平方的数
if x<result[0]:#选择最小值
x=result[0]
d=result[1]
elif x==result[0] and d<result[1]:#一样的X值,选择D最小的值
d=result[1]
print(d)
答案:661
67,最大路径和 (进阶版)
从下面展示的三角形的顶端出发,不断移动到在下一行与其相邻的元素,能够得到的最大路径和是 23.
3
7 4
2 4 6
8 5 9 3
如上图,最大路径和为 3 + 7 + 4 + 9 = 23.
在文件 triangle.txt 中包含了一个 100 行的三角形,求从其顶端出发到达底部,计算能够得到的最大路径和.
这是 第 18 题 的强化版.由于总路径一共有 299 条,穷举每条路经来解决这个问题是不可能的!即使你每秒钟能够检查 1012 条路径,全部检查完也需要两千万年.需要利用一个非常高效的算法才能解决这个问题.
Python3 解答
#读取数据
fan=open(r'C:\Users\GWT9\Desktop\p067_triangle.txt')
an=[]
for i in range(100):
an.append([])
x=fan.readline()
for j in range(100):
try:
an[i].append(int(x[j*3:(j*3)+2]))
except ValueError:
pass
fan.close()
#路径和最小动态规划
for ii in range(len(an)-2,-1,-1):
for j in range(len(an[ii])):
an[ii][j]=max(an[ii+1][j],an[ii+1][j+1])+an[ii][j]#动态规划思想
print(an[0][0])
答案:7273
动态思想系列讲解
68,"魔力" 五边形环
考虑下图中的 "魔力" 三角形环,在其中填入 1 至 6 这 6 个数,每条线上的三个数加起来都是 9.
Magic.png
从最外侧结点所填的数中最小的数(在这个例子中是 4,3,2)开始,按顺时针方向连接数字.按照此种方式每个解都能被唯一地描述.例如,上面这个解可以记作:4,3,2; 6,2,1; 5,1,3.将环填满后,每条线上的总和一共有四种可能:9,10,11 和 12,总共有下面 8 种填法,见下图:
sum.png
把解集中的数字连接起来,可以构造一个 9 位数字串;对于三角形环来说,最大的数字串就是 432621513.
在如下的 "魔力" 五边形环中,
five.png
在其中填入 1 至 10 这 10 个数,根据不同的填写方式,可以组成 16 位或 17 位数字串.在 "魔力" 五边形环中,最大的 16 位数字串是.
Python3 解答
import itertools as it
import numpy as np
#判断共享的数字集合
def magic(n):
#数字列表
select = list(range(1, 2*n + 1))
#可能的数组列表
plist = []
#返回n个数字的组合
for ii in it.combinations(select,n):
if sum(list(ii)) % n == 0:#共同的数字之和必须能被n整除
plist.append(list(ii))
return plist
def comadd(exlist):
#原始组合
yuanshi = np.array(exlist)
after = np.array(exlist[1:]+[exlist[0]])
#关系字典
save = {}
for ii in range(len(yuanshi)):
save[yuanshi[ii] +after[ii]] = [yuanshi[ii], after[ii]]
return save
def judge(exlist):
#去差集
cha = list(set(list(range(1, 2 * len(exlist) + 1))).difference(set(exlist)))
#计算exlist的可能的组合,
problist = []
pailie = it.permutations(exlist[1:], len(exlist) - 1)
for i in pailie:
if list(i)[::-1] not in problist:#去除掉组合重复的
problist.append(list(i))
#存储的字典
savedict = {}
for hh in problist:
hh.insert(0, exlist[0])
sadict = comadd(hh)
if len(sadict.keys()) == len(cha):#如果字典长度不够,说明存在数字和相同的情况,去掉这种情形
# 计算problist中的每一个组合是否满足条件
sumlist = list(np.array(sorted(list(sadict.keys()))) + np.array(sorted(cha, reverse = True)))
if len(set(sumlist)) == 1:
savedict[tuple(cha)] = sadict
return savedict
#定义输出数字序列的函数
def Transnum(exdict, keynum, weizhi, emptylist, keylist, sumdi):
emptylist += str(sumdi - keynum) + str(exdict[keynum][weizhi]) + str( exdict[keynum][weizhi - 1]) + ','
#选取键序列中的最小值
keylist.append(keynum)
for jj in exdict:
if jj not in keylist:
if exdict[keynum][weizhi - 1] == exdict[jj][weizhi]:
keynum = jj
return Transnum(exdict, keynum, weizhi, emptylist, keylist, sumdi)
return emptylist
#输出所有的可能性
savelist = []
for idi in magic(5):
#字典
ddict = judge(idi)
if len(ddict) != 0:
#键中的最小值
keynu = min(list(list(ddict.keys())[0]))
#值中键的最大值
numley = max(list(list(ddict.values())[0].keys()))
for idd in [0, 1]:
numstr = Transnum(list(ddict.values())[0], numley, idd, '', [], keynu + numley)
savelist.append(numstr)
print('%s: %s'%(keynu + numley, numstr))
#判断16数字最大的
lastnumber = 0
for j in savelist:
#去掉逗号
dele = j.replace(',','')
if len(dele) == 16:
#获得数字
if lastnumber < int(dele):
lastnumber = int(dele)
print(lastnumber)
答案:
所有"魔力"五边形环:
14: 635,752,824,941,1013,
14: 653,1031,914,842,725,
16: 2410,5101,817,673,934,
16: 2104,943,637,871,5110,
16: 259,493,637,871,1015,
16: 295,1051,817,673,439,
17: 278,584,3410,6101,917,
17: 287,971,6110,3104,548,
17: 1610,3104,548,782,926,
17: 1106,962,728,584,3410,
19: 1810,2107,379,496,568,
19: 1108,586,469,397,2710,
最大的16位数字串是:6531031914842725
69,欧拉函数之比值
在小于 n 的数中,与 n 互质的数的数目记为欧拉函数φ(n)(有时也称为φ函数).例如:1,2,4,5,7 和 8 均小于 9 且与 9 互质,故φ(9)=6.
euler.png
从上图可以看出,对于 n ≤ 10,当 n=6 时 n/φ(n) 最大.当 n ≤ 1,000,000 时,求使得 n/φ(n) 取得最大值的 n.
Python3 解答
n = 1000000
isprime = [True] * (n + 1) #质数标识
isprime[0] = isprime[1] = False
result = [] #质数列表
euler = [1, 1] + list(range(2, n + 1))#欧拉函数表
for i in range(2, n + 1):
if not isprime[i]:
continue
else:
result.append(i)
euler[i] = i - 1
for j in range(i * 2, n + 1, i):
isprime[j] = False
euler[j] *= (1 - (1 / i))
#n/φ(n)
funceuler = {i : i /euler[i] for i in range(0, n + 1)}#计算n/φ(n)
print(max(funceuler.items(), key = lambda x : x[1])[0])#计算n/φ(n)最大值对应的n值
答案:510510
70,欧拉函数之重排
在小于 n 的数中,与 n 互质的数的数目记为欧拉函数φ(n)(有时也称为φ函数).例如,因为 1,2,4,5,7 和 8 均小于 9 且与 9 互质,故φ(9)=6.1 被认为和任意正整数互质,所以φ(1)=1.
有趣的是,φ(87109)=79180,而 79180 是 87109 的一个重排.
在 1 < n < 107 中,有些 n 满足φ(n) 是 n 的一个重排,求这些值中使 n/φ(n) 最小的一个.
Python3 解答
n = 10000000
isprime = [True] * (n + 1) #质数标识
isprime[0] = isprime[1] = False
result = [] #质数列表
euler = [n, n] + list(range(2, n + 1))#欧拉函数表
for i in range(2, n + 1):
if not isprime[i]:
continue
else:
result.append(i)
euler[i] = i - 1
for j in range(i * 2, n + 1, i):
isprime[j] = False
euler[j] *= (1 - (1 / i))
#n/φ(n)
funceuler = {i : i /euler[i] for i in range(0, n + 1) if sorted(str(i)) == sorted(str(int(euler[i])))}#只选择φ(n)和n是重排的.
minkey = min(funceuler.items(), key = lambda x : x[1])[0]
print(euler[minkey])
print(minkey)
答案:φ(8319823)=8313928
最小的n值为8319823
持续更新,欢迎讨论,敬请关注!!!
来源: http://www.jianshu.com/p/d0fad6213433