September 20, 2012

let's code: แก้โจทย์คณิตศาสตร์กับ Project Euler

Project Euler คือสถานที่ฝึกปรือฝีมือการแก้โจทย์ปัญหาอีกที่หนึ่ง โดยโจทย์ส่วนใหญ่จะเป็นโจทย์ทางคณิตศาสตร์-คอมพิวเตอร์ ทำให้งานนี้เขียนโปรแกรมเป็นอย่างเดียวไม่พอ ยังต้องงัดสารพัดเทคนิคทางคณิตศาสตร์ออกมาเพื่อให้แก้ปัญหาได้อย่างสวยงามอีกด้วย

ถึงแม้จะไม่มีข้อกำหนดที่ชัดเจนว่าควรใช้ภาษาอะไร/เวลาประมวลผลเท่าไหร่ แต่ทางเว็บก็ได้ออกแบบโจทย์ทุกข้อไว้ให้สามารถแก้ได้ภายในเวลาที่น้อยกว่า 1 นาที (ด้วย algorithm ที่ optimize มาอย่างถูกต้อง) นอกจากนี้ผู้เล่นก็ควรจะซื่อสัตย์ต่อตัวเองด้วย เพราะโจทย์ทุกข้อจะใช้ test case เดิมไปตลอดครับ

ภาษาที่ใช้ได้
ภาษาใดก็ได้ หรือจะทดคำตอบในกระดาษก็ยังไหว

รูปแบบการตรวจคำตอบ
รับ test case จากหน้าเว็บมาประมวลผล แล้วส่งเฉพาะคำตอบ

ตัวอย่างโจทย์
  • 1: หาผลรวมของเลขจำนวนเต็มบวกทุกตัวที่ต่ำกว่า 1000 ซึ่งเลขแต่ละตัวเป็นผลคูณของ 3 หรือ 5
  • 25: จงหาลำดับของเลขฟีโบนักชีตัวแรก ที่เมื่อเขียนเป็นเลขฐานสิบแล้ว มีตัวเลขถึง 1000 หลัก
  • 80: สังเกตว่า √2 สามารถเขียนเป็นทศนิยมไม่รู้จบได้คือ 1.41421356237309504880... จงหาผลรวมของผลรวมของตัวเลข 100 หลักแรกในทศนิยมไม่รู้จบนี้ สำหรับรากที่สองของจำนวนเต็มบวกที่น้อยกว่า 100 ที่เป็นทศนิยมไม่รู้จบ
  • 206: จงหาจำนวนเต็มบวกเพียงหนึ่งเดียว ที่กำลังสองของมันสามารถเขียนให้อยู่ในรูป 1_2_3_4_5_6_7_8_9_0 เมื่อ _ แทนตัวเลขอะไรก็ได้ 1 หลัก

2 comments: