Tag Archives: Mathematics

แก้ Euler Project 551

ไปเจอปัญหาจาก Euler Project ข้อ 551 สรุปได้ว่า กำหนดลำดับ a(0), a(1), a(2), … โดย

a(n) = d(a(n-1)) + d(a(n-2)) + d(a(n-3)) + .. + d(a(1)) + d(a(0))

โดย a(0)=1 และ d(n) คือการเอาตัวเลขโดดของทุกหลักของเลข n มาบวกกัน (sum of digits) โจทย์ให้หาค่าของ a(1015)

ดูดีๆ จะเห็นว่า a(n) = d(a(n-1)) + a(n-1) ด้วยเช่นกัน ถ้าจะแก้แบบ recursive งานนี้ถ้าจะแก้กันง่ายๆ ตรงไปตรงมา เขียนด้วยภาษาสคริป Python ได้ว่า

def d(n):
    r = 0
    while n:
        r += n % 10
        n //= 10
    return r   

a=1
for i in xrange(1, 10**6):
    a+=d(a)

ซึ่งคำนวณถึงแค่ a(106) ก็ได้ค่า 31054319 ตรงกับที่ตัวอย่างให้มา ถ้าจะเอาให้ถึงตามโจทย์ สงสัยต้องหาทางแก้ non-homogeneous linear recurrence relation ให้ได้ก่อนครับ ก็อาจจะได้สมการที่มียกกำลัง n ออกมา หรืออาจต้องหาทางว่า มีความสัมพันธ์ที่จะย่อย n ให้ลงไปเป็เท่าๆ ตัว เช่น a(2n) = … ที่มี a(n..)

ปล. มีคนแจก source code วิธีแก้ในภาษา Python แล้วครับ ผมรันดูแล้วเสร็จในแป็ปเดียว https://git.icpc-camp.org/ftiasch/acm-icpc/blob/6d1d563a1dea39b8a8f525c836c5f3b0a243678b/project-euler/p551/p551.py

Advertisements

หาจำนวน Fibonacci ด้วย Matrix

ตัวเลขฟิโบนักซี ซึ่งเป็นความสัมพันธ์เวียนบังเกิดที่มีสูตร

f(n)=f(n-1)+f(n-2); f(1)=f(2)=1

สมมติอยากรู้ f(3) ถ้าเขียนในรูป matrix (ขอเขียนแบบ Python list นะครับ) จะได้ว่า

[[f(3)]] = [[1, 1]] * [[f(2)], [f(1)]] = [[f(2) + f(1)]]

\left[ \begin{array}{cc} f(3) \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \end{array} \right] * \left[ \begin{array}{cc} f(2) \\ f(1) \end{array} \right] = \left[ \begin{array}{cc} f(2) + f(1) \end{array} \right]

ซึ่ง matrix ตัวหนึ่ง เก็บค่าตัวคูณ (สัมประสิทธิ์) ซึ่งก็เป็นค่าคงที่ไม่ขึ้นกับค่า n ส่วนอีก matrix เก็บเลข fibonacci ตัวก่อนๆ เพื่อใช้คำนวณตามสูตร

แต่ถ้าต้องการจะรู้ตัวถัดไป คือ f(4) จะมีปัญหาว่า matrix ที่เราได้ มีแค่ f(3) โดยไม่่มี f(2) งานนี้เราจึงต้องคูณ matrix แล้วเก็บค่าเก่าที่จำเป็นในการหาเลข fibonacci ตัวต่อไปด้วย คือเก็บ f(2) วิธีง่ายๆ ก็แค่คูณ 1 เก็บไว้ ที่เหลือ คูณ 0

\left[ \begin{array}{cc} f(3) \\ f(2) \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] * \left[ \begin{array}{cc} f(2) \\ f(1) \end{array} \right] = \left[ \begin{array}{cc} f(2) + f(1) \\ f(2) + 0 \end{array} \right]

\left[ \begin{array}{cc} f(4) \\ f(3) \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] * \left[ \begin{array}{cc} f(3) \\ f(2) \end{array} \right]

ถ้าแทน F(n) = \left[ \begin{array}{cc} f(n) \\ f(n-1) \end{array} \right] และ M = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] จะได้ว่า

F(3) = M*F(2)
F(4) = M*F(3) = M*M*F(2) = M2F(2)
F(5) = M*F(4) = M*M*M*F(2) = M3F(2)

น้้นคือ

F(n) = M(n-2)F(2) ; F(2) = \left[ \begin{array}{cc} f(2) \\ f(1) \end{array} \right] = \left[ \begin{array}{cc} 1 \\ 1 \end{array} \right]

จะเห็นว่า เราเปลี่ยนรูปความสัมพันธ์จากการบวกไปเรื่อย มาเป็นการยกกำลังหรือการคูณเลข (หรือ matrix) ตัวเดียวกันหลายๆ ครั้ง
ซึ่งเป็นการคูณที่มักจะใช้ขั้นตอนการคำนวณมากกว่าการบวก การเปลี่ยนจากการบวกมาเป็นการยกกำลังนั้นน่าจะคำนวณยุ่งยากกว่า แต่การยกกำลังนั้น เราไม่จำเป็นต้องใช้อัลกอริทึมที่มีขั้นตอนอยู่ใน O(n) แต่ทำแบบ O(log(n)) ได้ โดยอาศัยหลักการที่ว่า Mn = (Mn/2)2 คือถ้าเราจะหา Mn ก็หใ้หา Mn/2 แล้วเอามายกกำลังสอง งานนี้เขียนโปรแกรมแบบ recursive จนกว่าจะถึง M หรือ M2 ก็หยุดเรียกตัวเอง ถ้าเกิด n เป็นเลขคี่ นั้นคือ n-1 เป็นเลขคู่ ก็ใช้สูตร Mn = M*Mn-1 = M*(M(n-1)/2)2

แนวทางจาก http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

วิธีแปลง NFA-Λ ให้ไปเป็น NFA

ต่อจากตอนที่แล้ว ซึ่งถ้าเจอเส้นที่เป็น Λ (บางตำราใช้ตัวอักษร ε แทน) เราต้องหาวิธีแปลงให้ NFA-Λ ให้ไม่มี Λ ไปเป็น NFA ที่ใช้วิเคราะห์ string เดียวกันได้

ขอนิยาม Λ(a) หมายถึง closure ที่ input เป็น set a แบบที่มีสมาชิกเป็น state และ output จาก Λ(a) จะเป็น set ของ state ที่สามารถเดินทางไปถึงได้จาก state ที่อยู่ใน a ด้วยเส้น Λ ทั้งนี้ให้ถือว่า state ใน a สามารถเดินทางไปหา a ได้เสมอ (สมาชิกทุกตัวของ a จะเจอใน Λ(a) เสมอ) และต้องมองข้ามช็อตหลายชิ่ง ถ้า state ปลายทางที่ไปถึงด้วย Λ นั้น มีไปต่อด้วย Λ ไปยัง state อื่นๆ ได้อีก ต้องรวม state นั้นๆ เพิ่มเข้าไปด้วย

การแปลงจาก NFA-Λ ไปเป็น NFA นั้นจำนวน state และชื่อ state จะไม่เปลี่ยน วิธีการหาว่า state หนึ่งๆ ใน NFA-Λ นั้น เมื่อได้รับ input แล้วจะไปยัง state ไหนของ NFA บ้าง ขั้นแรกให้เราหา Λ({q}) ของ state q นั้นๆ จากนั้นให้แยกออกไปตาม input ในแต่ละแบบ (ไม่รวม Λ) ว่า จากทุก state ที่ Λ({q}) ตอบค่ากลับมานั้น ไปยัง state ไหนได้บ้าง สมมติให้เป็น set p จะได้ว่าจาก state q เมื่อใส่ input นั้นๆ จะไป state ที่ตอบกลับมาโดย Λ(p)

สำหรับ state เริ่มต้นนั้นไม่เปลี่ยน ส่วน accept state ของ NFA ที่แปลงได้มาจาก NFA-Λ นั้นเหมือนเดิมแต่จะรวม state เริ่มต้นเข้าไปด้วย ถ้า closure ของ state เริ่มต้นนั้นมี accept state ปะปนอยู่ด้วย ขอยกตัวอย่าง ซึ่งทำเป็นตาราง คงเห็นภาพมากกว่า

(ตัวอย่างรอแป๊ปนะครับ)

อ้างอิง http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-lambda-2-nfa.html

 

แก้ Euler Project 501

มีปัญหา Euler Project หมายเลข 501 ให้หาจำนวนตั้งแต่ 1 ถึง 1012 ว่ามีกี่ตัว ที่จำนวนตัวหารซึ่งหารแล้วลงตัวของมันนั้น มีเท่ากับ 8 ตัว

ถ้าใช้วิธีวนลูปตรงๆ คืิอไล่เลข 1 ถึง 1012 ที่ละตัว เอามาหารด้วยเลข 1 จนถึงตัวมันเอง แล้วนับว่ามีหารลงตัวแปดตัวหรือไม่ ช้าแน่ ต้องหาวิธีอื่น โดยใช้หลักคณิตศาตร์มาช่วย คือเมื่อเอาตัวเลขมาแยกตัวประกอบ ให้กลายเป็นผลคูณของจำนวนเฉพาะ ถ้าจำนวนเฉพาะมีซ้ำกันให้เขียนเป็นเลขยกกำลัง จำนวนของตัวหารที่ลงตัว เท่ากับเอาเลขชี้กำลังของแต่ละจำนวนเฉพาะนั้น มาบวกเพิ่มอีกหนึ่งแล้วคูณกัน

เช่น 24 = 2331 เลขชี้กำลังมี 3 และ 1 เอามาบวกเพิ่มอีก 1 จะได้ 4 และ 2 เมื่อคูณกันได้ 8 คือมีจำนวนตัวหารเท่ากับ 8 ตัว (24 นี้มี 1, 2, 3, 4, 6, 8, 12, 24) โดยเลข 8 สามารถได้มาจากการคูณ 8×1, 4×2, 2×4, 2x2x2 ถ้าเราจะไล่หาจำนวนที่มีตัวหารลงตัวแปดตัวโดยทำย้อนไป โดยเอาจำนวนเฉพาะมายกกำลังและคุณกัน โดยเลขชี้กำลังต้องเข้ากับเงื่อนไขที่จะทำให้มีตัวหารลงตัวแปดตัว ก็จะมีได้สี่กรณี

p7
p3q1
p1q3
p1q1r1

โดย 1 < p < q < r และทั้งสามเป็นจำนวนเฉพาะ

ลอง coding คร่าวๆ

##

import itertools
import math

def is_prime(num):
    if num < 2:
        return False
    for x in range(2, int(math.sqrt(num))+1):
        if num % x == 0:
            return False
    else:
        return True

def fd0(p, lmbd):
    r=0
    for x in (itertools.combinations(p, lmbd.__code__.co_argcount)):
        if lmbd(*x):
            r+=1
    return r
    
nn=100
lp=list(filter(is_prime, range(1, nn+1)))
a=fd0(lp, lambda x: x**7 <= nn)
b=fd0(lp, lambda x, y: x**3 *y <= nn)
c=fd0(lp, lambda x, y: y**3 *x <= nn)
d=fd0(lp, lambda x, y, z: x*y*z <= nn)
t1=a+b+c+d

nn=1000
lp=list(filter(is_prime, range(1, nn+1)))
a=fd0(lp, lambda x: x**7 <= nn)
b=fd0(lp, lambda x, y: x**3 *y <= nn)
c=fd0(lp, lambda x, y: y**3 *x <= nn)
d=fd0(lp, lambda x, y, z: x*y*z <= nn)
t2=a+b+c+d


##

แต่ถ้าทำถึงเลข 1012 ยังช้าอยู่นะครับ ต้องหาทางออกจากวนลูปเอง เมื่อการคูณเกินจำนวนที่กำหนดไว้

##
def is_prime(num):
    if num < 2:
        return False
    x=2
    while x*x<=num:
        if num % x == 0:
            return False
        x+=1
    return True

nn=10**6
lp=list(filter(is_prime, range(1, nn//6 +2)))
lp.sort()

r=0
for i in range(len(lp)):
    if lp[i]**7 > nn:
        break
    else:
        r+=1

for i in range(len(lp)):
    for j in range(i+1, len(lp)):
        if lp[i]**3 *lp[j] > nn:
            break
        else:
            r+=1

for i in range(len(lp)):
    for j in range(i+1, len(lp)):
        if lp[j]**3 *lp[i] > nn:
            break
        else:
            r+=1

for i in range(len(lp)):
    for j in range(i+1, len(lp)):
        if lp[i]*lp[j] > nn:
            break
        for k in range(j+1, len(lp)):
            if lp[i]*lp[j]*lp[k] > nn:
                break
            else:
                r+=1
          
print(r)
##