ลำดับฟีโบนัชชี (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: เครืองหมาย < ต้องเป็น == ครับ
อ๋อ ขอบคุณครับ ผมยกตัวอย่างสำหรับ benchmark ครับ เน้นความชัดเจน ไม่ได้คิดมากเรื่องรายละเอียด ตาไวนะครับ 