โจทย์
เริ่มจากจำนวนบวก n ใด ๆ กฎของคอลลาตซ์กำหนดให้พจน์ถัดไปเป็น n / 2 เมื่อ n เป็นจำนวนคู่ และเป็น 3n + 1 เมื่อ n เป็นจำนวนคี่ โดยลำดับจะหยุดเมื่อถึง 1 ลำดับของ 6 คือ 6, 3, 10, 5, 16, 8, 4, 2, 1 ซึ่งมีเก้าพจน์ ในบรรดาจำนวนเริ่มต้นตั้งแต่ 1 ถึง limit ให้หาจำนวนที่ให้ลำดับที่มีพจน์มากที่สุด
จงเขียนฟังก์ชัน longest_collatz_chain(limit)
ลำดับต่าง ๆ มักลงท้ายด้วยพจน์ชุดเดียวกัน การจำความยาวที่หาได้แล้วของแต่ละจำนวนจึงช่วยลดงานได้มาก พจน์ระหว่างทางอาจมีค่าเกิน limit ได้ ให้ใช้จำนวนเต็ม 64 บิต
อินพุต
limit: จำนวนเริ่มต้นที่มากที่สุดที่ต้องลอง
เอาต์พุต
คืนค่าจำนวนเริ่มต้นที่ลำดับมีพจน์มากที่สุด (นับทั้งจำนวนเริ่มต้นและเลข 1 ตัวสุดท้าย) ถ้ามีหลายจำนวนเท่ากัน ให้คืนค่าตัวที่น้อยที่สุด
เงื่อนไข
1 ≤ limit ≤ 100,000
ตัวอย่าง
อินพุต:
limit = 6
ผลลัพธ์ที่คาดหวัง:
expected = 6
อินพุต:
long long limit = 6;
ผลลัพธ์ที่คาดหวัง:
long long expected = 6;
อินพุต:
long limit = 6;
ผลลัพธ์ที่คาดหวัง:
long expected = 6;
คำอธิบาย
ความยาวลำดับของ 1 ถึง 6 คือ 1, 2, 8, 3, 6 และ 9 พจน์ คำตอบจึงเป็น 6
อินพุต:
limit = 10
ผลลัพธ์ที่คาดหวัง:
expected = 9
อินพุต:
long long limit = 10;
ผลลัพธ์ที่คาดหวัง:
long long expected = 9;
อินพุต:
long limit = 10;
ผลลัพธ์ที่คาดหวัง:
long expected = 9;
คำอธิบาย
9 ให้ลำดับยาว 20 พจน์ (9, 28, 14, 7, ...) ซึ่งมากกว่าจำนวนเริ่มต้นอื่นทุกตัวที่ไม่เกิน 10 คำตอบจึงเป็น 9
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ลองนับจำนวนพจน์ของลำดับหนึ่งลำดับก่อน โดยนับทั้งจำนวนเริ่มต้นและเลข 1
คำใบ้ 2
เมื่อลำดับไปถึงจำนวนที่รู้ความยาวอยู่แล้ว ให้นำความยาวนั้นมาบวกแทนการไล่ต่อ
คำใบ้ 3
เปลี่ยนจำนวนเริ่มต้นที่ดีที่สุดเฉพาะเมื่อความยาวมากกว่าเดิมจริง ๆ เท่านั้น
ความซับซ้อนที่คาดหวัง
เวลา O(limit × average new steps), หน่วยความจำเพิ่ม O(limit)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน