โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ลำดับคอลลาตซ์ที่ยาวที่สุด

หาจำนวนเริ่มต้นที่ไม่เกินค่าที่กำหนดซึ่งให้ลำดับคอลลาตซ์ยาวที่สุด

สิ่งที่คุณจะได้เรียนรู้

  • สร้างลำดับคอลลาตซ์
  • เก็บผลลัพธ์ไว้เพื่อไม่ต้องคำนวณซ้ำ
  • ตัดสินกรณีเสมอด้วยค่าที่น้อยที่สุด

โจทย์

เริ่มจากจำนวนบวก 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก