ลำดับ Collatz สามารถสร้างได้โดย 3 เงื่อนใข 1.ถ้า n = 1 ให้ หยุด
2.ถ้า n เป็นเลขคู่ ให้ n/23.ถ้า n เป็นเลขคี่ ให้ 3n+1
เช่น n = 13 ลำดับก็จะเป็น 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 เมื่อ n = 13 ลำดับนี้จะมีความยาว = 10 โจทย์ข้อนี้ต้องการให้เราหาความยาวของลำดับที่มากที่สุด ที่ถูกสร้างโดยเลขที่ <= n
นั่นหมายความว่า ถ้า n เป็น 13 เราจะต้องไล่หาลำดับของ 13 , 12 , 11 ,10 ,...,1 แล้วดูว่าลำดับไหนมีความยาวมากที่สุด
แนวคิด ถ้ามองโจทย์ดีๆแล้วเมื่อเราสร้าง Collatz ของ 13 เราจะสร้างของ 40,20,10,5,16,8,2,1 เช่นเดียวกัน เพราะฉะนั้นเราสามารถใช้เทคนิคการ Memoization เข้ามาช่วยได้ จะทำให้เราสามารถหาลำดับ Collatz ได้ไวขึ้นมาก เมื่อเราหาได้แล้วเราจะต้องไล่ตั้ง 1 จนถึง n เพื่อหาว่าตัวไหนมากสุด แต่ถ้าหากคิดดีๆแล้ว
ถ้าเราจำค่าความยาวที่มากสุดแล้วนำไปเปรียบเทียบกับตัวถัดไปเรื่อยๆ เราก็สามารถทำการ precompute ทุกคำตอบได้เหมือนกัน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น