Project Euler針對數學和程式愛好者，設計了一系列的問題，至今已有五百多道，供大家挑戰，每一題都要求應在1分鐘內計算出答案。
我將以Python語言來解題，原始碼放在GitHub（yehnan/project_euler_python），基本上都是先採用暴力法，若運算量太大，無法在1分鐘內算出答案，才著手研究想出更快的演算法。當題目的數字很小時，隨便寫就能在1分鐘內算出答案，但是，也就只有幾題而已，大部分的題目都需要大量計算，可沒那麼好混。
我使用硬體Raspberry Pi 2與軟體Raspbian，作為執行速度的依據。
注意：不提供詳細的說明與分析。
Problem 11: Largest product in a grid，20×20格子，每格有個數字，把相鄰的四個數相乘，找出乘積最大的。所謂相鄰是指同一方向的連續四個數，方向有上下、左右、左上右下的對角線、右上左下的對角線。
把題目給的20×20格子，放進檔案裡，然後讀取放進二維串列。
from io import open
grid = []
with open('p011_data.txt', 'r', encoding='ascii') as fin:
for line in fin:
grid.append(list(map(int, line.split())))
給定含有數字的串列，算出乘積。
def product(li):
result = 1
for n in li:
result *= n
return result
給定串列、個數count，找出相鄰count個數字相乘後乘積最大的。
def product_max(li, count):
max = 0
for i in range(0, len(li)-count + 1):
m = product(li[i:i+count])
if m > max:
max = m
return max
底下函式可拿出左上右下或右上左下的對角線，由參數slant決定。
def diag(grid, row, col, slant):
d = []
while True:
try:
d.append(grid[row][col])
row += 1
col += slant
except IndexError:
break
return d
終於到了問題本身，底下函式可找出相鄰四個數乘積最大的，但只會尋找一半：每一列、右上半部對角線為左上右下、左上半部對角線為右上左下。
def find_max(grid, count):
max = 0
for row in grid:
m = product_max(row, count)
if m > max:
max = m
for col in range(len(grid[0])):
m = product_max(diag(grid, 0, col, 1), count)
if m > max:
max = m
for col in range(len(grid[0])):
m = product_max(diag(grid, 0, col, -1), count)
if m > max:
max = m
return max
不過，只要把格子旋轉90度，再丟進上面的函式，便可處理另外一半。
def lpiad(grid, count):
m = find_max(grid, count)
grid_rotated = list(zip(*grid))
mr = find_max(grid_rotated, count)
return max(m, mr)
Problem 12: Highly divisible triangular number，找出第一個擁有超過500個因數的三角數（triangle number）。
暴力法太慢，應該先作質因數分解，根據質因數的次方數，便可算出因數的個數。不過此處並未作質因數分解，而是作2與奇數的分解。底下函式，給定參數n，求出n的因數個數。
def divisors_count(n):
dc = 1
cnt = 0
while n % 2 == 0:
n //= 2
cnt += 1
dc *= (cnt + 1)
p = 3
while n != 1:
cnt = 0
while n % p == 0:
n //= p
cnt += 1
dc *= (cnt + 1)
p += 2
return dc
下面這個產生器函式，會不斷給出下一個三角數。
def triangle_number_gf():
tn = 0
i = 1
while True:
tn += i
i += 1
yield tn
最後是問題本身，傳入參數500，便可算出答案。
def hdtn(dc):
for tn in triangle_number_gf():
if divisors_count(tn) > dc:
return tn
Problem 13: Large sum，給定100個數字，皆為50位數，算出總和後，取出前10個位數。
因為只要記憶體夠大，Python的整數便能不斷變大，所以這題對Python來說很簡單。把給定的東西放在檔案裡，呼叫底下函式傳入檔名，即可算出答案。
from io import open
def ls(filename):
with open(filename, 'r', encoding='ascii') as fin:
total = sum(int(line) for line in fin)
return str(total)[:10]
Problem 14: Longest Collatz sequence，根據奇偶歸一猜想，每個正整數經過數次Collatz轉換後，最終會得到1。在小於一百萬的數字中，哪個數需要最多次轉換才能到1。
首先，底下函式給定參數n（起始數），回傳Collatz轉換的次數。
memo = {1: 1}
def collatz(n):
if n not in memo:
if n % 2 == 0:
memo[n] = 1 + collatz(n // 2)
else:
memo[n] = 1 + collatz(3 * n + 1)
return memo[n]
然後，以迴圈迭代所有起始數，找出轉換次數最多的那一個。底下函式傳入1000000即可求出答案。
def lcs(m):
n = 1
n_len = 1
for i in range(2, m+1):
i_len = collatz(i)
if n_len < i_len:
n = i
n_len = i_len
return n
Problem 15: Lattice paths，20×20的格子，從最左上走到最右下，只能向左或向下移動，請問有幾種路徑。
此題等同於：有40個位置，手上有20個紅球和20個綠球，請問共有幾種擺法。也就是40! / 20! / 20!。所以先寫階乘函式。
def factorial(n):
result = 1
for i in range(2, n+1):
result *= i
return result
然後是問題本身，底下函式傳入20與20，即可求出答案。
def lp(row, col):
return factorial(row+col) // factorial(row) // factorial(col)
Problem 16: Power digit sum，求2**1000的所有位數的總和。
因Python支援無限大的整數（只要記憶體足夠的話），所以這題對Python來說很簡單。底下函式傳入1000即可求出答案。
def pds(n):
num = 2 ** n
result = 0
for d in str(num):
result += int(d)
return result
Problem 17: Number letter counts，把1到1000寫成英文，總共有幾個字母。
嗯，只能根據規則把數字轉成英文字串，底下函式只能處理1到1000的情況。
d3 = {1: 'one thousand'}
d2a = { 10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen',
14: 'fourteen', 15: 'fifteen', 16: 'sixteen',
17: 'seventeen', 18: 'eighteen', 19: 'nineteen' }
d2b = { 2: 'twenty', 3: 'thirty', 4: 'forty', 5: 'fifty',
6: 'sixty', 7: 'seventy', 8: 'eighty', 9: 'ninety' }
d1 = { 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five',
6: 'six', 7: 'seven', 8: 'eight', 9: 'nine' }
def i2s(i): # from 1 to 1000
a4 = i // 1000
a3 = (i % 1000) // 100
a2 = (i % 100) // 10
a1 = i % 10
result = []
if a4 == 1:
result.append('one thousand')
if a3 != 0 or a2 != 0 or a1 != 0:
result.append(' and ')
if a3 != 0:
result.append(d1[a3])
result.append(' hundred')
if a2 != 0 or a1 != 0:
result.append(' and ')
if a2 == 1:
result.append(d2a[a2*10 + a1])
elif a2 >= 2:
result.append(d2b[a2])
if a1 != 0:
result.append('-')
if a2 != 1 and a1 != 0:
result.append(d1[a1])
return ''.join(result)
然後是問題本身，底下函式傳入1與1000，即可算出答案。
def nlc(n, m=None):
if m is None:
m = n
result = 0
for i in range(n, m+1):
s = i2s(i)
s = s.replace(' ', '').replace('-', '')
result += len(s)
return result
Problem 18: Maximum path sum I，Problem 67: Maximum path sum II，給定呈現三角形的數字層，從頂端開始走，往下一層走時可往左或往右，走到底部時形成一條路徑，把走過的數字加總，請問路徑加總和最大的是多少。
首先寫函式把代表三角形的資料從檔案載入，變成多維串列。
from io import open
def get_triangle(filename):
triangle = []
with open(filename, 'r', encoding='ascii') as fin:
for line in fin:
triangle.append([int(n) for n in line.split()])
return triangle
然後是尋找最大路徑加總和的函式，屬於從上往下的遞迴形式。當你站在某一個位置時，只要算出左下三角形的最大路徑加總和、以及右下三角形的最大路徑加總和，挑出比較大的那一條，便可決定往哪走。
def max_path_sum(tri, row, col):
if row == len(tri)-1:
return tri[row][col]
else:
sub = max(max_path_sum(tri, row+1, col),
max_path_sum(tri, row+1, col+1))
return tri[row][col] + sub
最後是題目本身，傳入資料檔名，即可求出答案。
def mpsi(filename):
tri = get_triangle(filename)
return max_path_sum(tri, 0, 0)
不過，當三角形層數一多（Problem 67），上述寫法就太慢了，必須由下往上，從倒數第二層開始，位置(r, c)的最大路徑加總和，會是(r, c) + (r+1, c)與(r, c) + (r+1, c+1)兩個之中較大的那一個。一層一層往上，最後便可算出頂端(0, 0)的最大路徑加總和。
def max_path_sum(tri, row, col):
for r in range(len(tri)-1 -1, -1, -1):
for c in range(len(tri[r])):
tri[r][c] += max(tri[r+1][c], tri[r+1][c+1])
return tri[row][col]
Problem 19: Counting Sundays，二十世紀每個月第一天是星期日的日子，有幾天。
我們知道1900年1月1日是星期一，定其天數為1；而1900年1月7日是星期日，天數為7，所以只要算出某日期（日月年）的天數，能被7整除的話即是星期日。
首先是判斷潤年的函式。
def is_leapyear(year):
if year%4 == 0 and year%100 != 0 or year%400 == 0:
return 1
else:
return 0
給定月份與年份，回傳該月份有幾天。
month = [31, 28, 31, 30, 31, 30,
31, 31, 30, 31, 30, 31]
def days_of_month(m, y):
return month[m-1] + (is_leapyear(y) if m == 2 else 0)
給定年份，回傳該年份有幾天。
def days_of_year(y):
return sum(month) + is_leapyear(y)
給定日期（日月年），算出其天數。
def date_to_days(date):
dy, mn, yr = date
days = dy
for y in range(1900, yr):
days += days_of_year(y)
for m in range(1, mn):
days += days_of_month(m, yr)
return days
能被7整除，則為星期日。
def is_sunday(days):
return days % 7 == 0
迭代所有年份的每月第一天。
def cs():
count = 0
for y in range(1901, 2000+1):
for m in range(1, 12+1):
days = date_to_days((1, m, y))
if is_sunday(days):
count += 1
return count
Problem 20: Factorial digit sum，加總100階乘的所有位數。
沒什麼好說的，算出階乘，然後把每個位數加起來。
def fact(n):
result = 1
for i in range(1, n):
result *= i
return result
底下函式傳入100，便可求得答案。
def fds(n):
s = str(fact(n))
result = 0
for c in s:
result += int(c)
return result
No comments:
Post a Comment