Project Euler Problem #25

ลำดับฟีโบนัชชี (Fibonacci Sequence) กำหนดโดย ความสัมพันธ์เวียนเกิด (Recurrence Relation) ต่อไปนี้:

F_n = F_n−1 + F_n−2 โดยที่ F_1=1 และ F_2=1

ดังนั้น 12 จำนวนแรก จะเป็น:

F_1 = 1
F_2 = 1
F_3 = 2
F_4 = 3
F_5 = 5
F_6 = 8
F_7 = 13
F_8 = 21
F_9 = 34
F_{10} = 55
F_{11} = 89
F_{12}= 144

ลำดับที่ 12 คือ F_{12} เป็นจำนวนแรกที่มีตัวเลขสามหลัก

ลำดับฟีโบนัชชีจำนวนแรกที่มี 1000 หลัก คืออะไร

(โจทย์นี้แปลมาจาก projecteuler.net สามารถเผยแพร่ภายใต้ลิขสิทธิ์ CC BY-NC-SA 2.0 UK )


Rain’s answer for #25

@Rain
ชัดเจน: 2/3 สร้างสรรค์: 2/3 กระชับ 2/3 ความเร็ว 1/3
Comment: while loop สวยงามครับ ทีนี้เรื่องความเร็ว อย่าลืมครับว่าทุกครั้งที่แปลงเป็น string มันจะกินเวลามากกว่าเพราะต้องแปลงเป็น string ก่อน ขอยกตัวอย่างโค้ดนะครับ

sequence = 111111111111111111
thousand_digits = 10 ** 1000

def compare_int():
   if sequence // thousand_digits < 0:
       pass 

def compare_string():
    if len(str(sequence)) < 1000:
        pass

if __name__ == '__main__':
    import timeit
    # 0.266510009766 seconds
    print(timeit.timeit("compare_int()", setup="from __main__ import compare_int"))
    # 0.327558040619 seconds
    print(timeit.timeit("compare_string()", setup="from __main__ import compare_string"))

ถ้าแปลงเป็น string ก่อน จะใช้เวลา 0.32 วินาที แต่ถ้าเราคำนวน integer ของเลขหนึ่งพันหน่วยออกมาเก็บไว้ แล้วเอามาเปรียบเทียบ จะใช้เวลา 0.26 วินาที ลดเวลาในการคำนวนลงไปได้ประมาณ 30% เลยครับ

@STGSafe
ชัดเจน: 2/3 สร้างสรรค์: 2/3 กระชับ 1/3 ความเร็ว 1/3
Comment: สามารถตัดบรรทัดที่ 13 ออกไปแล้วเอา print() มาไว้นอก loop ได้ครับ

@Akira
ชัดเจน: 2/3 สร้างสรรค์: 2/3 กระชับ 1/3 ความเร็ว 2/3
Comment: ดีครับ แต่ผมว่าถ้าใช้คำเต็มๆ เช่น thousand แทน thsnd จะอ่านเข้าใจง่ายกว่านี้ครับ

@IMPREM
ชัดเจน: 1/3 สร้างสรรค์: 2/3 กระชับ 1/3 ความเร็ว 2/3
Comment: ไม่ชอบ while True ครับ ควรเป็น while fibnew <= 10**999 ไปเลย

10 ** 1000 มี 1001 หลักครับต่องเป็น 10 ** 999 ครับ
if sequence // thousand_digits < 0: เครืองหมาย < ต้องเป็น == ครับ

1 Like

อ๋อ ขอบคุณครับ ผมยกตัวอย่างสำหรับ benchmark ครับ เน้นความชัดเจน ไม่ได้คิดมากเรื่องรายละเอียด ตาไวนะครับ :slight_smile: