罗马不是一天建成的，你也不会一下成为梦想中的人，但是只要在学习在努力，就是越来越接近的。
继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是31~40题。
(奇怪，这人怎么又开始用python写了
Problem 31: Coin sums
嗯。。挺经典挺常见的完全背包DP问题，但是我满脑子不知道在想什么，愣是没做出来，后来看了看别人的提示才想到应该按照硬币种类去循环。一直在想怎么去处理重复的情况。
这里是这道题的详细解释
这里是完全背包、01背包、多重背包的比较的参考资料（我没看
def pro31():
# 完全背包DP
coin = [1, 2, 5, 10, 20, 50, 100, 200]
methods = [0]*300
methods[0] = 1
for k in coin:
for i in range(1, 210):
if i >= k:
methods[i] += methods[i-k]
print(methods[200])
Problem 32: Pandigital products
很蠢的一个做法，每一个去遍历判断的
def pro32():
out = []
for i in range(10, 10000):
numl = []
k = i
while k != 0:
if k % 10 not in numl:
numl.append(k % 10)
k = k//10
else:
break
if k == 0:
for j in range(2, int(math.sqrt(i))):
if i % j == 0:
numll = []
k = j
while k != 0:
if (k % 10 not in numl) and (k % 10 not in numll):
numll.append(k % 10)
k = k//10
else:
break
if k == 0:
k = i//j
while k != 0:
if (k % 10 not in numl) and (k % 10 not in numll):
numll.append(k % 10)
k = k//10
else:
break
if (k == 0) and (len(numl)+len(numll) == 9) and (0 not in numl) and (0 not in numll):
print("%d %d %d" % (i, j, i//j))
if i not in out:
out += [i]
print(sum(out))
Problem 33: Digit cancelling fractions
这个问题第一次考虑的时候考虑错了，以为分子和分母相同的数字肯定一个在十位一个在个位的，导致一开始答案是错误的。其实可以在外层循环增加一些判断，这样速度会快一些。。。
def pro33():
for i in range(10, 98):
for k in range(i+1, 99):
for j in str(i):
if j in str(k):
if i % 10 == int(j) and (k % 10) != 0:
if ((i//10) / (int(str(k).replace(j, '', 1)))) == i/k:
print("%d %d" % (i, k))
elif k % 10 != 0:
if ((i % 10) / (int(str(k).replace(j, '', 1)))) == i/k:
print("%d %d" % (i, k))
Problem 34: Digit factorials
算就对了
def pro34():
out = 0
for i in range(3, 100000):
k = i
sum = 0
while k != 0:
sum += math.factorial(k % 10)
k = k//10
if sum == i:
print(i)
out += i
print(out)
Problem 35: Circular primes
遍历，判断质数的程序又写了python版的，在最后贴上来
def pro35():
out = 4
for i in range(11, 1000000, 2):
if isPrime(i):
if i == 11:
i = 11
num = 0
for k in range(1, len(str(i))):
j = int(str(i)[k:]+str(i)[:k])
if not isPrime(j):
num += 1
break
if num == 0:
print(i)
out += 1
print(out)
Problem 36: Double-base palindromes
遍历，不讲（不过python确实行数少很多
def pro36():
out = 0
for i in range(1, 1000000):
k = str(i)
if k == k[::-1]:
k = bin(i)[2:]
if k == k[::-1]:
print(i)
out += i
print(out)
Problem 37: Truncatable primes
遍历。。。
def pro37():
out = 0
for i in range(11, 1000000, 2):
if isPrime(i):
n = 0
for k in range(1, len(str(i))):
if not isPrime(int(str(i)[k:])):
n += 1
break
if not isPrime(int(str(i)[:k])):
n += 1
break
if n == 0:
print(i)
out += i
print(out)
Problem 38: Pandigital multiples
同上。。。（这次题没有好玩的呀
def pro38():
for i in range(5, 10000):
nums = []
leng = 0
k = i
while k != 0:
if k % 10 not in nums:
nums.append(k % 10)
k = k//10
if len(nums) != len(str(i)):
continue
leng += len(nums)
for j in range(2, 10):
k = j*i
while k != 0:
if k % 10 not in nums:
nums.append(k % 10)
k = k//10
if len(nums)-leng != len(str(j*i)):
break
leng = len(nums)
if (leng == 9) and (0 not in nums):
print(i)
Problem 39: Integer right triangles
遍历。。，这个题判断条件可以仔细思考一下，能节约很多无效的计算
def pro39():
# solution计算有问题，有重复情况，但是题目不要求~~~
solution = 0
out = 0
for p in range(10, 1000):
so = 0
for a in range(p//3, p-2):
for b in range(1, a-1):
c = p-a-b
if c > 0 and a*a == b*b+c*c:
so += 1
if so > solution:
solution = so
out = p
print(out)
Problem 40: Champernowne’s constant
蠢遍历
def pro40():
# 蠢办法 is coming
out = 1
count = 1
nums = [1, 10, 100, 1000, 10000, 100000, 1000000]
for i in range(1, 100000):
k = str(i)
while len(k) != 0:
if count in nums:
out = out*int(k[0])
print(k[0])
count += 1
k = k[1:]
print(out)
Prime (python)
def isPrime(n):
if not hasattr(isPrime, 'prime'):
isPrime.prime = [2, 3, 5, 7]
if n < isPrime.prime[-1]:
return n in isPrime.prime
else:
i = isPrime.prime[-1]+2
while n > isPrime.prime[-1]:
num = 0
for k in isPrime.prime:
if i % k == 0:
num += 1
break
if k > math.sqrt(i):
break
if num == 0:
isPrime.prime.append(i)
i += 2
return n in isPrime.prime
def isPrimeS(n):
if n < 2:
return False
if n % 2 == 0:
return False
if n % 3 == 0:
return False
for k in range(2, int(math.sqrt(n))):
if n % k == 0:
return False
return True