ดังตัวอย่างที่ยกไปเมื่อตอนที่แล้ว คือ

ฝึกวิเคราะห์ algorithm ด้วยตะแกรงร่อน Palindrome (2) 

ผมทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 9x xxx xx9 ซึ่งโอกาสที่จะผิด มีเพียง 0.0514 ยกกำลัง 1000 (โอกาสผิดราว 2 ใน 10 ยกกำลังหนึ่งพันเศษ ๆ)

ด้วยแนวคิดแบบเดียวกัน ผมลองนำไปใช้แบบให้สุดกู่ขึ้นอีก คือทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 99 xxx x99 ซึ่งโอกาสที่จะผิด มีเพียง 0.0514 ยกกำลัง 100 (โอกาสผิดราว 1 ใน 10 ยกกำลัง 129) ซึ่งขอเรียกว่า เป็นกรณีที่สอง

เอาให้ตึงขึ้นมาอีกล่ะ คือทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 99 9xx 999 ซึ่งโอกาสที่จะผิด มีเพียง 0.0514 ยกกำลัง 10 (โอกาสผิดราว 1 ใน 10 ยกกำลัง 13) ซึ่งในที่นี้ ขอเรียกว่า เป็นกรณีที่ 3

กรณีที่ 3 ซึ่งเป็นกรณีหลังสุด มีความเสี่ยงสูงไปนิดนึง เห็นแล้วไม่สบายใจที่จะใช้ 

ดังนั้น ผมจะรู้สึกว่า กรณีที่ 2 น่าจะลงตัว คือ ทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 99 xxx x99

คราวนี้ผมจะใช้งานอย่างไรต่อล่ะ ?

ใช้การสังเกตุครับ 

จากการสังเกตุ 99 xxx x99 จะต้องเกิดจากการคูณกันระหว่าง 99xx กับ 99yy (ดูตรงนี้ให้ดี ๆ นะครับ เพราะผมพลาดตรงนี้ !)

ดังนั้น กฎย่อยข้อแรกของเราคือ ใช้วิธีบังคับคูณแบบหักโหม แต่เลือกค่าตั้งต้นให้เหมาะสม ในที่นี้ เริ่มจาก 9900 ถึง 9999 มาคูณกันเองแบบพบกันหมด ซึ่งก็เป็นไปได้เพียง 1 หมื่นคู่เท่านั้นเอง

แล้วอันที่จริง ผมไม่ต้องคูณทุกรายการด้วย เพราะการที่ผลคูณลงท้ายด้วย 9 เกิดจากความเป็นไปได้เพียง 4 แบบ จาก 100 แบบเท่านั้นเอง

คือ

ลงท้ายด้วย 1 เจอกับลงท้ายด้วย 9

ลงท้ายด้วย 3 เจอกับลงท้ายด้วย 3

ลงท้ายด้วย 7 เจอกับลงท้ายด้วย 7

ลงท้ายด้วย 9 เจอกับลงท้ายด้วย 1

กฎข้อสองคือ กรองด้วยการดูเลขลงท้ายดังกล่าว ก็จะทำให้ 1 หมื่นคู่ ลดลงมาอีก เหลือเพียง 4 ร้อยคู่

ยังไม่หนำใจ ลองนึกถึงว่า การคูณแบบพบกันหมด มีความสมมาตรหน้าหลัง เลขมากคูณเลขน้อย ก็คือเลขน้อยคูณเลขมาก เวลาคูณ ก็อาจบังคับว่า ตัวหน้าใหญ่กว่าตัวหลังเสมอ จะได้ไม่ต้องคูณซ้ำซาก

เกิดเป็นกฎข้อสาม คือ ไม่ต้องคูณซ้ำคู่ที่เคยคูณไปแล้ว เพราะผมสามารถเลือกแต่กรณีที่ตัวเลขตัวหลัง ไม่ต่ำกว่าตัวเลขตัวแรก ก็พอ (เช่นถ้ารู้ 9953 x 9933 ก็ไม่ต้องหา 9933 คูณ 9953)

ทำแบบนี้ ก็จะลดฮวบ คูณทดสอบแค่สองร้อยคู่โดยประมาณเท่านั้นเอง (ผลคือ ความอืด จะลดจาก 8 ลงมาได้เหลือ 2.3 ซึ่งเยอะโขอยู่)

เขียนเป็น pseudocode ดังนี้ (ยืมคำศัพท์ภาษา Basic มาใช้ ... ก็เขียนเป็นอยู่ภาษาเดียวนิ  -_-!)

  • for x=9901 to 9999
  •   for y=x to 9999
  •      z=multiply if ended with {1,9} or {9,1} or {3,3} or {7,7}
  •      check for palindrome and keep the new-high
  •   next y
  • next x

ลองรันดูจริง ต้องคูณกันทั้งหมด 210 ครั้ง

และได้ 9901 x 9999 = 99000099

ใน 210 ครั้งของการคูณ น่าจะมี palindrome ราว 95 % คือราวเกือบ 200 ครั้ง

แต่มี palindrome แค่ตัวเดียวเท่านั้น

เอ๊ะ ที่เหลือหายไปไหน ?

palindrome = ต้องแยก factor ได้

prime  =  แยก factor ไม่ได้

มี prime ราว 5 % จึงควรมี palindrome ราว 95 % สิ

ไม่ใช่ครับ

palindrome ต้องแยก factor ได้ แต่แยก factor ได้ไม่จำเป็นต้องเป็น palindrome

แถม palindrome ที่มีอยู่ชุกชุม ก็ไม่จำเป็นต้องเกิดจากเลข 4 หลักคูณเลข 4 หลักด้วย 

หน้าแตกครับ แหกเป็นริ้วเลย !

ดังนั้น ในกรณีนี้ ต้องถือว่า algorithm นี้ ให้คำตอบแบบบังเอิญเฉียดฉิวมาก

ชัณสูตรแล้วเดาได้ไหมว่า ทำไมเจอแค่ 1 รายการที่เป็น palindrome ที่เป็นผลจากการที่ใช้เลข 4 หลักคูณเลข 4 หลัก ?

พอจะนึกออกราง ๆ ครับ แต่มองว่า เหตุผลที่อธิบายตรงนี้ได้ เป็นหัวข้อใหญ่เรื่องหนึ่งได้เลย

แต่ตอนนี้ ยังคิดไม่ค่อยลงตัว ไว้โอกาสหน้าถ้าคิดออก และไม่ลืมซะก่อน ค่อยมาต่อภาค 4 (อิ อิ อิ...)

 

ลองมาสรุปปฎิบัติการกันหน่อยดีไหม ?

แนวคิดทั้งหมดที่กล่าวมา จะเห็นได้ว่า ผมทำความเข้าใจกับโจทย์ และมีการปรับโจทย์ก่อน (optimize โจทย์) ให้อยู่ในสเกลที่กำลังพอจัดการได้

แล้วตามด้วยการพลิกแพลงแนวคิดในการเขียนโปรแกรม (optimize algorithm)

หลังจากนั้น ค่อยตามด้วยการเขียนโปรแกรมจริง 

ในกรณีนี้ ปัญหามีลักษณะเฉพาะ บังเอิญว่ามองเชิงวิเคราะห์ออกก่อนเขียนโปรแกรม โดยใช้ความเข้าใจเรื่องเลข prime มาช่วย "ฟันธง" ถางทางไว้

แต่การใช้เทคนิคแบบนี้ ก็มีข้อจำกัด คืออาจมีกรณีที่มองไม่รอบด้าน ทำให้ล้มเหลวได้ ดังที่ผมสาธิตให้ดู (ทั้งที่ถูก และที่ผิด)

(ในที่นี้ ผมคาดว่า จะเจอ palindrome เยอะ จากการใช้เลข 4 หลักคูณเลข 4 หลัก ทั้ง 210 ครั้ง แต่เจอจริงแค่ 1 รายการ ซึ่งแม้ไม่ล้มเหลว แต่ถือว่าเป็นความสำเร็จที่ฟลุ้คไปหน่อย)

อย่างไรก็ตาม ปัญหาในสเกลใหญ่จริง ๆ ที่เกิดประโยชน์มาก ๆ มักต้องใช้ความพลิกแพลงเข้าช่วย เลี่ยงไม่ได้ เช่น ใน bioinformatics 

เช่น การใช้ mass spectroscopy หา amino acid sequence ที่ยาวสัก 100 ตัวต่อกัน ระดับปัญหาที่คำนวณแบบหักโหม ต้องทำถึง 100! ครั้ง ซึ่งยังไม่มีฮาร์ดแวร์ที่ไหนรองรับได้ในบัดเดี๋ยวนี้ ต้องใช้วิธีพลิกแพลงด้วยการตั้งกฎย่อย ๆ มากระหนาบ กรองทิ้งหย่อมใหญ่ที่ไม่ต้องเสียเวลาตรวจสอบ

แต่ขนาดกรองแล้วเร็วขึ้นล้านล้านล้านเท่า ก็ยังช้ามากๆๆๆๆ ในกรณีเช่นนี้

algorithm จึงสำคัญสุด ๆ ในปัญหาโหด ๆ เช่นนั้น

แต่ใช่ว่า เราต้องพลิกแพลงคิดเสมอไป

ในบางงาน เขาอาจใช้วิธีที่ทื่อ ตรงดิ่ง แบบขวานผ่าซาก เช่น การเขียนโปรแกรมให้ใช้กำลังแบบหักโหม (brute force) เพื่อใช้ประเมินสมรรถนะของ hardware เช่น ในการแข่งขันหมากรุกระหว่างคนกับคอมพิวเตอร์

หรือในงานที่เล็กมาก หรือดูแล้วว่า ต่อให้ brute force ใช้เวลานานแค่ไหน ก็รอได้สบาย ๆ  

แบบนั้น ไม่ต้องคิดให้เมื่อยก็ได้ เอาเวลาไปเขียนบล็อกซะดีกว่า

 

"การเลือกใช้ algorithm จึงต้องนับเป็นส่วนหนึ่งของตัว algorithm เองเสมอ"