Tag Archives: Computer Science

แก้ 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)
##

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

วิธีแปลง Non-deterministic Finite Automata (NFA) ให้เป็น Deterministic Finite Automata (DFA) แต่ผมขอเรียกสั้นๆ ว่า FA นะครับ (เพราะมันไม่มี N) ทั้งนี้ ถ้ามีเส้นที่เป็น Λ คือเส้นซึ่งสามารถไปต่อได้โดยไม่ต้องอ่านตัวอักษรเข้ามา (ค่อยไปอ่านที่หลังใน state ถัดๆ ไป) ก็คือ NFA ของเราเป็นแบบ NFA-Λ ก็ต้องเปลี่ยนมันให้เป็น NFA ที่ไม่มี Λ เสียก่อน วิธีการจะขอกล่าวในภายหลังนะครับ ตอนนี้ขอแบบ NFA ไม่มี Λ ก่อน

การแปลงเราจะสร้างตารางที่คอลัมน์เป็นตัวอักษรที่จะเป็น input เข้ามาได้ ส่วนแถวจะเป็น state ของ FA ที่เราจะค่อยๆ สร้างขึ้นมาใหม่จาก NFA โดยชื่อ state ที่สร้างขึ้นใหม่นี้ จะเป็น set ที่ได้จากการประสมชื่อของ state จาก NFA ทำให้จำนวน state ใหม่ของ FA นี้ อาจพุ่งไปได้สูงสุดเท่ากับ 2 ยกกำลังจำนวน state ของ NFA ถ้าพูดแบบคณิตศาสตร์แล้ว state ของ FA ที่สร้างขึ้นมาใหม่ ก็คือ subset ของ set ที่มี state ทั้งหมดของ NFA และเพราะว่าเป็น set ทำให้ลำดับของชื่อ state ที่ได้จาก NFA นั้นไม่มีความสำคัญ ตัวอย่างเช่น {0, 1} เท่ากับ {1, 0}

ให้เราเริ่มจาก state แรกเริ่มต้นก่อน (ตั้งต้น) ซึ่งชื่อ state จะเป็น set ที่มีสมาชิกเป็น state เริ่มต้นจาก NFA ใส่ในแถวแรกของตาราง จากนั้นไล่แต่ละ state ใน set นั้น (กรณีนี้ มีแต่ state เริ่มต้น) ว่าตัวอักษรนั้นๆ ไปยัง state ไหนได้บ้าง ก็ให้เอา state ที่ไปได้นั้น มาเพิ่มใน set ที่เป็น state ใหม่ ที่อยู่ภายใต้ตัวอักษรนั้นๆ ขั้นต่อมา

จากนั้นจะมี set ของ state เกิดขึ้นมา ก็เอาไปใส่ในแถวถัดไป แล้วแก้โจทย์แบบเดิมต่อ จนกว่าจะไม่มี set ของ state ให้แก้โจทย์อีก

ตัวอย่างนะครับ

nfa01

ถ้าจะเขียนเป็นตารางแสดงวิธีการเปลี่ยน state ของ NFA นี้ (WordPress.com ทำตารางยังไงเนี้ย)

state  | a | b
0 | 1 | 2
1 | 1,2 | 2
2 | null | 1

null หมายถึงไม่มีที่ให้ไปต่อนะครับขั้นแรกเริ่มจาก state เริ่มต้นก่อน พบว่าอักษร a พาไป state 1 ได้ ส่วนอักษร b พาไป state 2 ได้

state  | a | b
{0} | {1} | {2}

แก้ {1} พบว่า a ไปได้ทั้ง 1 หรือ 2 ส่วน b ไปไหนไม่ได้ ในส่วนของ {2} ไป {1} ได้ ถ้าเป็นอักษร b เข้ามา

state  | a | b
{0} | {1} | {2}
{1} | {1, 2} | null
{2} | null | {1}

เราได้ตารางสำหรับ FA มาแล้ว สำหรับ state ปลายทาง

ก็จะเหลือ state {1, 2} ก็ให้ไล่เรียงในแต่ละสมาชิกของ set นี้ ซึ่งก็มีสอง state คือ {1} และ {2} ถ้าอักษรเข้ามาเป็น a แล้วเดินจาก state 1 จะไปได้ทั้งที่ state 1 หรือ state 2 และถ้าเดินจาก state 2 จะไปไหนไม่ได้ รวมแล้วจึงได้ {1, 2}

จากนั้น ไล่ตามอักษรต่อไป ถ้าอักษรเข้ามาเป็น b ถ้าเดินจาก state 1 จะไปไหนไม่ได้ และถ้าเดินจาก state 2 จะไป {1} รวมกันได้ {1}

state | a | b
{0} | {1} | {2}
{1} | {1, 2} | null
{2} | null | {1}
{1, 2} | {1, 2}| {1}

เราก็จะได้ FA สำหรับ NFA ดังกล่าว สำหรับ state ปลายทาง ของ FA (accepting state ที่ FA จะชี้ว่า string ที่เข้ามานั้น ยอมรับได้) คือ set ที่มี state ที่เป็นปลายทางของ NFA กรณีนี้ state 0 และ 1 เป็น accepting state ของ NFA ดังนั้นจาก state ทั้งหมดของ FA จะได้ว่า accepting state ของ FA คือ {0}, {1} และ {1, 2}

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