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

ทศนิยมซ้ำที่มีคาบยาวที่สุด

หา d ที่ไม่เกินค่าที่กำหนดซึ่งเศษส่วน 1/d มีชุดทศนิยมซ้ำยาวที่สุด

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

  • จำลองการหารยาวด้วยเศษ
  • ตรวจหาค่าซ้ำด้วยตารางค้นหา
  • หาความยาวคาบจากตำแหน่งที่พบครั้งแรก

โจทย์

เศษส่วนที่มีตัวเศษเป็น 1 บางตัวเป็นทศนิยมรู้จบ (1/4 = 0.25) ส่วนที่เหลือเป็นทศนิยมซ้ำไม่รู้จบ เช่น 1/6 = 0.1666... ซ้ำเป็นชุดละ 1 หลัก และ 1/7 = 0.142857142857... ซ้ำเป็นชุดละ 6 หลัก ในบรรดา d = 2, 3, ..., limit ให้หา d ที่ 1/d มีชุดตัวเลขที่ซ้ำยาวที่สุด ให้เขียนโค้ดจำลองการหารยาวแบบที่ทำด้วยมือ ตัวเลขจะเริ่มซ้ำทันทีที่ได้เศษเดิมกลับมา

จงเขียนฟังก์ชัน longest_recurring_cycle(limit)

อินพุต

limit: ตัวส่วนที่มากที่สุดที่ต้องลอง

เอาต์พุต

คืนค่า d ที่มีชุดซ้ำยาวที่สุด เศษส่วนที่เป็นทศนิยมรู้จบถือว่ามีความยาวชุดซ้ำเป็น 0 ถ้ามีหลายค่าของ d ที่ยาวเท่ากัน ให้คืนค่าที่น้อยที่สุด

เงื่อนไข

2 ≤ limit ≤ 2000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
limit = 8

ผลลัพธ์ที่คาดหวัง:
expected = 7
อินพุต:
long long limit = 8;

ผลลัพธ์ที่คาดหวัง:
long long expected = 7;
อินพุต:
long limit = 8;

ผลลัพธ์ที่คาดหวัง:
long expected = 7;

คำอธิบาย

ความยาวชุดซ้ำของ 2 ถึง 8 คือ 0, 1, 0, 0, 1, 6, 0 คำตอบจึงเป็น 7

ตัวอย่างที่ 2
อินพุต:
limit = 5

ผลลัพธ์ที่คาดหวัง:
expected = 3
อินพุต:
long long limit = 5;

ผลลัพธ์ที่คาดหวัง:
long long expected = 3;
อินพุต:
long limit = 5;

ผลลัพธ์ที่คาดหวัง:
long expected = 3;

คำอธิบาย

1/3 ซ้ำหนึ่งหลัก ส่วน 1/2, 1/4 และ 1/5 เป็นทศนิยมรู้จบ คำตอบจึงเป็น 3

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

เลขโดดใหม่แต่ละตัวของ 1/d ได้จากเศษคูณด้วย 10

คำใบ้ 2

จำไว้ว่าเศษแต่ละค่าปรากฏครั้งแรกที่ขั้นตอนใด

คำใบ้ 3

ถ้าเศษเป็น 0 แสดงว่าเป็นทศนิยมรู้จบ มิฉะนั้นความยาวคาบคือระยะห่างระหว่างการพบเศษค่าเดิมสองครั้ง

ความซับซ้อนที่คาดหวัง

เวลา O(limit²), หน่วยความจำเพิ่ม O(limit)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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

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

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

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

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