2015/03/29

Project Euler與Python:Problem 1~10

Project Euler針對數學和程式愛好者,設計了一系列的問題,至今已有五百多道,供大家挑戰,每一題都要求應在1分鐘內計算出答案。

我使用硬體Raspberry Pi 2與軟體Raspbian,作為執行速度的依據。

十八世紀數學家Leonhard Euler。
根據目前的統計,解出25~49題的人數將近四萬(38392),而解出超過450題的人數僅有45。
各種賞心悅目的成就徽章。
可先上去看看有哪些題目,若想開始解題,先註冊個帳號,然後便可輸入答案。每道問題經過設計,都以某數字作為明確的答案,在題目頁面的欄位「Answer:」裡提交,便可檢查是否正確解題。
若答案正確,可進入該問題的論壇,看看別的語言的解法,觀看其他人的討論文章。當然啦,網路上也可找到他人公布分享的程式原始碼,但如果直接照抄就失去意義了。
接下來試試第1~10題吧,我將以Python語言來解題,原始碼放在GitHub(yehnan/project_euler_python),基本上我都是先採用暴力法,若運算量太大,無法在1分鐘內算出答案,才著手研究想出更快的演算法。當題目的數字很小時,隨便寫就能在1分鐘內算出答案,但是,也就只有幾題而已,大部分的題目都需要大量計算,可沒那麼好混。

注意:並提供詳細的說明與分析。

Problem 1: Multiples of 3 and 5,小於1000的正整數中,找出3或5的倍數,相加求總和。

底下函式直接使用暴力法,傳入參數1000可算出此題的答案。

def m35(n):
    result = 0
    for i in range(1, n):
        if i % 3 == 0 or i % 5 == 0:
            result += i
    return result


也可縮成一行,其中運用了產生器運算式(generator expression)。

def m35(n):
    return sum(i for i in range(1, n) if i%3==0 or i%5==0)


Problem 2: Even Fibonacci numbers,找出小於四百萬而且是偶數的費波那契數,相加求總和。

首先是計算費波那契數(fibonacci number)的函式,採取遞迴形式,但會記憶算過的值,免得重複計算。

memo = {0: 0, 1: 1}
def fib(n):
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

然後是題目本身,使用暴力法,從小到大算出費波那契數,小於四百萬而且是偶數的話就加起來。底下函式傳入參數4000000,即可得到答案。

def efn(max):
    result = 0
    n = 1
    fn = fib(n)
    while fn <= max:
        if fn % 2 == 0:
            result += fn
        n += 1
        fn = fib(n)
    return result

Problem 3: Largest prime factor,找出600851475143最大的質因數。

首先是能從小到大、不斷給出質數的函式,底下prime_gf是產生器函式,prime_f則是產生器。

def prime_gf():
    primes = [2]
    def is_prime(n):
        for i in primes:
            if n % i == 0:
                return False
        return True
    while True:
        p = primes[-1]
        yield p
        while True:
            p += 1
            if is_prime(p):
                primes.append(p)
                break
prime_f = prime_gf()


然後是題目本身,底下函式傳入參數600851475143,即可得到答案。

def lpf(n):
    max = 1
    for i in prime_f:
        if i <= n:
            while n % i == 0:
                n /= i
                max = i
        else:
            break
    return max


Problem 4: Largest palindrome product,迴文數,譬如9009,從頭端看過來、與從尾端看過去都一樣,而且9009是兩個2位數相乘後的迴文數中最大的(91 × 99),請問兩個3位數相乘後最大的迴文數是多少。

首先,底下函式可判斷是否為迴文數。

def is_palindrome(n):
    ns = str(n)
    a, b = 0, len(ns)-1
    while a < b:
        if ns[a] != ns[b]:
            return False
        else:
            a += 1
            b -= 1
    return True


然後,底下函式的參數d代表幾位數,以暴力法列出所有的兩個d位數組合,相乘後判斷是不是迴文數,通通記錄起來。

def palindromes(d):
    result = []
    for x in range(10**d-1, 10**(d-1)-1, -1):
        for y in range(x, 10**(d-1)-1, -1):
            if is_palindrome(x * y):
                result.append((x*y, x, y))
    return result


最後進行排序,便可得到最大的迴文數。底下函式傳入參數3可得到答案。

def palindromes_max(d):
    return sorted(palindromes(d), key=lambda x: x[0])[-1][0]


Problem 5: Smallest multiple,能夠被1到20所有數字整除的正整數裡,最小是多少。

首先是計算最大公因數與最小公倍數的函式。

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)


然後是題目本身,一次處理兩個數,不斷算出兩個數的最小公倍數,1跟2的最小公倍數是2,2跟3的最小公倍數是6,6跟4的最小公倍數是12,依此類推。底下函式傳入參數1與20,即可算出答案。

def sm(x, y):
    m = 1
    for n in range(x, y+1):
        m = lcm(m, n)
    return m


Problem 6: Sum square difference,前100個自然數(正整數)的平方和與和平方的差值。

呃,沒什麼好說的,數字小、計算量少,直接暴力法即可。底下函式傳入參數100可得到答案。

def ssd(n):
    sum_sq = sum(i**2 for i in range(1, n+1))
    sq_sum = sum(range(1, n+1)) ** 2
    return sq_sum - sum_sq


Problem 7: 10001st prime,求第10001個質數。

底下函式可判斷參數n是否為質數,檢查小於n的數之中,是否有可以整除n的數存在,但不需要檢查「小於n」的數,只需檢查「小於n開根號+1」的數即可。

def is_prime(n):
    if n % 2 == 0:
        return False
       
    p = 3
    n_sqrt = n**0.5 + 1
    while p < n_sqrt:
        if n % p == 0:
            return False
        p += 2
    return True

然後是問題本身,從3開始,逐一判斷下一個(+2)是否為質數,直到目標。底下函式傳入參數10001便可算出答案。

def nth_prime(n):
    prime = 2
    count = 1
    p_next = 3
    while count < n:
        if is_prime(p_next):
            prime = p_next
            count += 1
        p_next += 2
    return prime

Problem 8: Largest product in a series,給定一個有100位數的數字,找出其中相鄰的13個位數、位數的乘積最大。

暴力法,逐一算出乘積,比較哪個大。

def lpias(num, n):
    num_str = str(num)
    num_len = len(num_str)
   
    def prod(ns):
        p = 1
        for i in ns:
            p *= int(i)
        return p
       
    max = 1
    for i in range(0, num_len - n + 1):
        m = prod(num_str[i:i+n])
        if m > max:
            max = m
    return max


Problem 9: Special Pythagorean triplet,只有一組畢氏三元數組a、b、c能使得a+b+c等於1000,請算出a*b*c。

首先,判斷a、b、c是否為畢氏三元數組。

def is_pythagorean_triplet(a, b, c):
    return a**2 + b**2 == c**2


然後,底下產生器函式可產生出a + b + c = n而且a < b < c的三數組。注意,其中range的參數並非最佳化。

def abc_gf(n):
    for c in range(n//3, n):
        for b in range((n-c)//2, n-c):
            a = n - c - b
            if a < b < c:
                yield a, b, c


最後是問題本身,底下函式傳入參數1000,即可找出答案。

def spr(n):
    for a, b, c in abc_gf(n):
        if is_pythagorean_triplet(a, b, c):
            return a*b*c


Problem 10: Summation of primes,找出小於兩百萬的所有質數,加總求和。

使用埃拉托斯特尼篩法找出小於n的質數。

def prime_sieve(n):
    primes = set(range(2, n+1))
    for i in range(2, (n+1+1) // 2):
        if i in primes:
            m = 2
            while i*m <= n:
                primes.discard(i*m)
                m += 1
    return primes


然後加總即可。底下函式傳入參數2000000即可算出答案。

def sop(n):
    return sum(prime_sieve(n))


參考資料:

No comments:

Post a Comment