คุณยังไม่ได้ Log in | สมัครสมาชิก ฟรี
กลับหน้าแรก วิชาการ.คอม
คุณสามารถแสดงบทความนี้  บนเว็บไซท์ของคุณ หรือที่ไหนก็ได้ โดยตัดโค๊ดนี้ไปแปะไว้
<script language="JavaScript" src="http://www.vcharkarn.com/vlesson/javafeed.php?lessonid=7" type="text/javascript"></script>

66874
การแก้ปัญหาด้วยคอมพิวเตอร์ (Programming and Algorithm)
    วิชานี้ว่าด้วยปัญหา และการแก้ปัญหาด้วยคอมพิวเตอร์ โดยอาศัยพื้นฐานวิธีคิด (algorithm) ต่างๆ ที่เคยมีคนคิดค้นไว้แล้วเป็นฐานในการแก้ปัญหาของเราเอง หรือ พัฒนาเป็น algorithm ใหม่ๆ
อยู่ในส่วน คอมพิวเตอร์
ระดับของบทเรียน ปริญญาตรี
ปรับปรุงล่าสุด 20 พ.ย. 2550 (00:26)
เข้าชมแล้ว 37772 ครั้ง (รวมทุกหน้า)
[Vote : 83 | Rating : 4.75]
หน้าที่ 1 - ปัญหา และ การแก้ปัญหา

ปัญหาและการแก้ปัญหาด้วยคอมพิวเตอร์ (Problem Solving and Algorithm) เรียบเรียงมาจากเอกสารประกอบการเรียนการสอน นักศึกษาชั้นปีที่ 1 ภาควิชา เทคโนโลยีสารสนเทศ (IT) วิทยาการคอมพิวเตอร์ (CS) การจัดการเทคโนโลยี (MT) และ เทคโนโลยีสิ่งแวดล้อม (EV) เป็นส่วนหนึ่งใน วิชา ITS033 Programming & Algorithms ของ สถาบันเทคโนโลยีนานาชาติสิรินธร ภายใต้ มหาวิทยาลัยธรรมศาสตร์ ที่ว่าด้วยการใช้คอมพิวเตอร์ในการแก้ปัญหาต่างๆ วิเคราะห์แนวทางการแก้ปัญหาก่อนที่จะลงมือเขียนโปรแกรม แต่ถอดความมาเป็นภาษาไทยให้น้องๆคนอื่นๆได้อ่านได้ง่ายๆทั่วกัน


ดร.บุญญฤทธิ์ อุยยานนวาระ

ภาควิชาคอมพิวเตอร์และเทคโนโลยีสารสนเทศ
สถาบันเทคโนโลยีนานาชาติสิรินธร
มหาวิทยาลัยธรรมศาสตร์

Algoritmics

วิชานี้เป็นการเรียนเกี่ยวกับ Algorithm (อัลกอริทึ่ม) ซึ่งเป็นกระบวนการคิดในการแก้ปัญหาที่สามารถใช้คอมพิวเตอร์ในการแก้ได้ หรือพูดง่ายๆว่าเขียนโปรแกรมเพื่อแก้ปัญหาได้ (อันนี้ไม่รวมปัญหาอกหัก และ ปัญหาเงินไม่พอใช้ นะครับ) วิชานี้ไม่ใช่วิชาการเขียนโปรแกรม (Progamming 1) (ซึ่งถ้าสนใจเรื่องนั้น ก็อ่านได้จากบทเรียนของ ดร.จันทร์จิรา ที่นี่ครับ การเขียนโปรแกรมภาษา C เบื้องต้น (Introduction to C Programming))

วิชานี้จะต่างจากวิชาการเขียนโปรแกรมนะครับ เพราะวิชาการเขียนโปรแกรม (Programming 1) คือวิชาที่ว่าด้วย grammar ของภาษาโปรแกรมนั้นๆ เช่น if ใช้งานอย่างไร for loop ใช้งานอย่างไร การอ่าน array ทำอย่างไร เป็นต้น แต่วิชานี้ไม่ได้เน้นที่ตัวโปรแกรม แต่ละเน้นที่ปัญหา และ การแก้ปัญหา ซึ่งแน่นอนว่าถ้าคุณมีพื้นฐานการเขียนโปรแกรมที่ดี การแก้ปัญหาด้วยคอมพิวเตอร์ก็ทำได้ดีขึ้นด้วย

บางคนบอกว่าถ้าฉลาดก็จะเรียนวิชานี้ได้ดี ถ้าไม่ฉลาดก็ลำบาก ตรงนี้ก็ไม่ถูกนัก ทั้งนี้แน่นอนคนฉลาดก็ย่อมเข้าใจปัญหาได้ดี แต่ถ้าหากคุณคิดว่าตัวเองไม่ฉลาด (ซึ่งที่แน่ๆคือคุณคิดผิด - ไอน์สไตน์บอกว่าเราเกิดมามีสมองเท่ากันทุกคน) คุณก็เพียงพยายามแก้ปัญหา ตามแนววิธีการแก้ปัญหาที่ได้เรียนไปในวิชานี้นั่นเอง เพราะวิชานี้จะบอกแนวทางการแก้ปัญหา คุณก็ต้องพยายามนำแนวทางเหล่านี้ไปประยุกต์ใช้กับปัญหาใหม่ที่คุณเจอ เพราะโดยเนื้อหาวิชานี้ จะเป็นการเรียนรู้วิธีการแก้ปัญหา จากวิธีการที่มีคนคิดไว้แล้วในอดีต ซึ่งจริงๆเราก็พบว่าส่วนใหญ่ของปัญหามากมายที่เราพบเจอ ได้มีคนคิดวิธีแก้ปัญหาเหล่านั้นไว้แล้วอย่างชาญฉลาด หากปัญหาใหม่ของเรา ที่เราต้องการจะแก้นั้น ใกล้เคียงกับปัญหาที่เคยมีคนแก้ได้แล้ว เราก็ไม่จำเป็นต้องคิดใหม่หรือมองหาวิธีใหม่ เพราะวิธีการแก้ปัญหา หรือ algorithm เหล่านั้น ได้รับการขัดเกลาผ่านเวลามานานจนเรียกได้ว่าเกือบจะสมบูรณ์ เราก็เพียงแค่เลียนแบบการแก้ปัญหาด้วยวิธีนั้นๆ ในการแก้ปัญหาของเราเอง หรือแม้แต่หากว่า เราต้องการจะหาวิธีแก้ปัญหาแบบใหม่ที่ดีกว่านั้น หรือแก้ปัญหาใหม่ๆ ที่ไม่เคยมีใครแก้ได้มาก่อน วิชานี้ก็จะพูดถึงแนวคิด การคิดอย่างมีระบบ เพื่อเป็นเครื่องมือและพื้นฐาน ในการแก้ปัญหาทางคอมพิวเตอร์ของคุณต่อไป

ปัญหาและการแก้ปัญหา

การแก้ปัญหา ในที่นี่ ไม่ได้หมายถึงเพียงแค่การที่ให้เราใช้คอมพิวเตอร์แก้ปัญหา แล้วแก้ปัญหาได้ แต่เราหมายถึงการแก้ปัญหาอย่างเป็นระบบ (Systematically) และ และอย่างมีประสิทธิภาพด้วย (Efficiently) คำว่ามีประสิทธิภาพ หมายถึงการที่เราสามารถคิดวิธีแก้ปัญหา ที่รวดเร็ว ใช้ทรัพยากรของระบบน้อย เช่น ใช้ Memory เพียงนิดเดียว ใช้ Harddisk เพียงนิดเดียว หรือ CPU ที่มีความเร็วต่ำก็ยังใช้ในการประมวลผลเพื่อแก้ปัญหานี้ได้ (เอ๋ รู้สึกว่า Windows Vista จะตรงข้ามกับอันนี้ทุกอย่างเลยนะเนี่ย..)

ปัญหา (Problem)

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


จงหาค่าเฉลี่ยของ x เมื่อ
x = y4+2y3+5 เมื่อ y เป็นจำนวนเต็มที่มีค่า ตั้งแต่ 1 ไปถึง 30

ที่เป็นแบบนั้น เพราะวิธีการคิดเพื่อการแก้ปัญหาข้างต้น ในแง่ของการทำงานของคอมพิวเตอร์แล้ว ถ้าคิดง่ายๆก็แทบจะไม่มีอะไรจะต้องคิด (แปลว่าถ้าคิดยากๆ โจทย์นี้ก็มีเรื่องให้คิดอยู่เหมือนกัน) แค่เอาค่า y ไปแทนเรื่อยๆ แล้วเก็บค่า x ไว้ แล้วมาหาค่าเฉลี่ยของ x เมื่อแทน y ในสมการครบทุกตัว (เรียกว่าเป็นวิธีที่ผมขอเรียกว่า "ตรงไปตรงมา" ที่สุดก็แล้วกัน) คราวนี้ลองดูปัญหาแบบนี้บ้างครับ


สมมติว่าคุณเป็นเจ้าของร้านค้า 11-7 ทุกร้านในเมืองไทย ซึ่งมีสาขาทั้งหมด 500 สาขาอยู่ทั่วประเทศไทย ทุกๆวัน ศูนย์กลางที่อยู่ที่ กทม. จะต้องจัดสินค้าใส่รถส่งสินค้า หลายสิบคัน แล้วรถทั้งหลาย ก็ต้องนำสินค้า ไปส่งให้ทุกสาขาทั่วประเทศ เอาหล่ะ ลองดูปัญหาย่อยๆเหล่านี้ครับ

ปัญหาย่อยที่ 1. สมมติว่าเกิดเหตุไม่คาดฝัน รถเสียทั้งบริษัทเลย วิ่งไม่ได้ซักคันเดียว เอาละสิ แต่บังเอิญว่าเครื่องบินบรรทุกสินค้าที่คุณเช่ามาจาก DHL ยังทำงานได้อยู่ คุณจำเป็นต้องให้เครื่องบินลำเดียวนี้ เิดินทางไปส่งของ 500 จุดทั่วประเทศ (อาจจะด้วยวิธีทิ้งลงจากเครื่องบิน เมื่อบินอยู่เหนือจุดเป้าหมาย) ถามว่า จะให้เครื่องนี้บินยังไงดี ถึงจะจัดส่งสินค้าไปทุกจุด และประหยัดที่สุด ลองคิดเล่นๆดูสิ ว่าคุณจะบินจาก กทม ไป ทางเชียงใหม่ก่อนดี แล้ววนแถวภาคเหนือก่อนดี หรือ ว่าบิน zigzag ดี หรือว่าบินวนเป็นวงดี (ปัญหานี้เป็นปัญหา classic มากเลย นักคอมพิวเตอร์ทุกคน (หรือคนที่ผ่านวิชา Algorithm design) รู้จักดี เรามักจะเรียกปัญหาประเภทนี้ ว่า "Travelling Salesman Problem")

ปัญหาย่อยที่ 2. เอาหล่ะ สมมติว่าเหตุการณ์ทุกอย่างปกติดี บริษัทมีรถที่วิ่งครบทุกคัน แต่ปัญหาอยู่ที่ผู้บริหาร ที่อยากจะเพิ่มประสิทธิภาพของบริษัท เลยมาถามคุณให้คำนวณซิว่า จะใช้รถกี่คันดี คันนึงบรรทุกของเท่าไหร่ดี คันนึงๆวิ่งเส้นทางไหนดี ที่จะส่งของไปทุกจุดทั้งประเทศ แล้วประหยัดค่าใช้จ่ายค่าคนขับ ค่าน้ำมัน ค่าซ่อมบำรุงรถ ถูกที่สุดและดีที่สุด (ปัญหาประเภทนี้ก็ classic ครับ มีพารามิเตอร์มาหลายๆๆตัว เราต้องการหาจุดที่ดีที่สุดจากพารามิเตอร์ทั้งหมด ภายใตเงื่อนไขหรือเป้าหมายอย่างหนึ่ง เราเรียกปัญหาประเภทนี้ ว่า "Optimization Problem" ซึ่งไม่ใช่แค่นักคอมพิวเตอร์หล่ะครับคราวนี้ ที่ต้องเจอปัญหาประเภทนี้ วิศวกรต่างๆ โดยเฉพาะพวกอุตสาหการ (IE) หรือ พวกการจัดการเทคโนโลยี (MT) ก็เรียนเรื่องพวกนี้เป็นวิชาๆเลย)

อ้าว....นี่มันเกี่ยวกับคอมพิวเตอร์ยังไงเหรอครับอาจารย์ ? ไม่เห็นจะเกี่ยวเลย ... หรือถ้ามันเีกี่ยวกัน แล้วอย่างนี้ผมจะเริ่มเขียนโปรแกรมยังไงดีเนี่ย โอย...งง ไม่รู้จะเริ่มตรงไหนดี... เอ้า..ผมใช้มือคิดบนกระดาษทดนี่เอาก็แล้วกัน!!

แหะๆๆ ถ้าคิดแบบนี้ก็จบแน่ครับ 11-7 ทั้ง 500 สาขา ของคุณเจ๊งหมด เพราะหนทางความเป็นไปได้ทั้งหมดของปัญหานี้ (possible path) มีมากมายถึง 499! (สี่ร้อยเก้าสิบเก้าแฟค โอ! พระเจ้าจอร์จ กล้วยทอด มันยอดมาก 499 แฟคทอเรียล นี่มัน กี่พัน กี่ล้าน หนทางกันละเนี่ย) - (ลองคิดดูเล่นๆนะครับว่าทำไมถึง 499! ถ้าคิดไม่ออกก็อดใจรอ บทถัดไปมีคำตอบเรื่องนี้)

ส่วนวิธีว่าจะแก้ปัญหานี้ยังไงนั่นก็ต้องอดใจรอนานอีกนิดครับ ในบทถัดๆไปของบทเรียนนี้ เราจะพูดเรื่องนี้กันเรื่องเดียวเลย เรื่องที่ว่า "เราจะเปลี่ยนปัญหาทั่วๆไป ในชีวิตประจำวัน ไปให้คอมพิวเตอร์ช่วยแก้ได้ยังไง"

โอว มันยอดมากเลยจอร์จ... ใช่เลย ซาร่า... แต่ช้าก่อน เราลองมาดูอีกซัก 2 ตัวอย่าง ที่ classic ระดับอมตะนิรันดร์กาล เหมือนกันครับ

พวกนี้เป็น puzzle แต่อย่ามองว่ามันเป็น puzzle ปรกติ เพราะจริงๆพวกนี้ล้อมาจากปัญหาจริงๆ เช่น บริษัทต้องการส่งสินค้าให้ลูกค้าภายใต้เงื่อนไขจำกัดจำนวนหนึ่ง แต่ puzzle พวกนี้เอาเงื่อนไขมาทำให้ soft ขึ้นและใส่ตัวละครที่ทำให้ปัญหาสนุกขึ้นนั่นเอง ลองมองให้มันเป็นปัญหา logistic ดูสิครับ


ปัญหาการข้ามแม่น้ำ ที่ริมแม่น้ำแห่งหนึ่ง มีชายคนนึง, แพะ 1 ตัว, สุนัขจิ้งจอก 1 ตัว, และ หัวผักกาด 1 หัว ทั้งหมดนี้ต้องการข้ามแม่น้ำ ไปยังอีกฟาก แต่ปัญหาก็คือว่าเรือที่จอดอยู่ลำหนึ่ง มีขนาดเล็กเกินไปที่จะขนทุกอย่างในเที่ยวเดียว มันบรรทุกได้เพียงชายคนนี้กับอีกอย่างเดียวเท่านั้น แต่อีกปัญหาก็คือว่า ถ้าไม่มีชายคนนี้อยู่ด้วย ปล่อยให้อยู่กันสองอย่าง สุนัขจิ้งจอกจะหม่ำแพะ และ แพะก็จะหม่ำหัวผักกาด ปัญหาของเราก็คือว่า หากเราต้องเขียนโปรแกรม ให้คอมพิวเตอร์ช่วยหาหนทางในการทำให้ทั้ง 4 ข้ามฟากไปโดยปลอดภัย (ที่ต้องเขียนเป็นโปรแกรม ก็เพราะว่า ถ้าเราเจอปัญหาคล้ายๆกัน เช่น ชาย, แมว, หมา, ปลา หรือ ชาย, ไก่, ข้าวเปลือก, งู, พังพอน - เราจะได้ใช้โปรแกรมนี้ได้เลย)

ปัญหา 8Queen (Facility Allocation Problem)

ลองดูปัญหานี้นะครับ เรามีตารางหมากรุกขนาด 8x8 อยู่ อันนึงเราต้องการจะวาง Queen ซึ่งเป็นตัวหมากรุกสากลที่มีอำนาจเยอะที่สุดเลย คือ สามารถเดินและกินได้ ยาว ทั้งแนวตั้ง แนวนอน และ แนวทะแยง ดังภาพด้านซ้ายด้านล่างนี้ เราต้องการจะวาง Queen ทั้งหมด 8 ตัวลงบนกระดานเดียวกัน โดยไม่ให้มี Queen ตัวไหนกินกันได้เลย เอ๋ เราจะวางอย่างไรดี ลองเล่นดูนะครับ ตัวอย่างของรูปแบบการวางที่ประสบความสำเร็จคือ รูปด้านขวาครับ วางได้ และไม่มีใครกินใครได้เลย

      
โจทย์นี้ดูเหมือนจะไร้สาระ แต่จริงๆก็เป็นเวอร์ชั่นง่ายๆของปัญหาประเภทที่เรียกว่า Facility Allocation Problem คือว่าเรามีของหลายอย่าง หรือ โรงงานหลายอันที่ต้องการวางในพื้นที่ โดยการจะวางก็มีเงื่อนไขหรือกฏเกณฑ์ต่างๆมากกำหนดไว้ ยกตัวอย่างเช่น เราเป็น 11-7 (อีกแล้ว) ถ้าหากว่าเราต้องการเปิด 11-7 อีก 8 สาขาโดยมีเงื่อนไขว่า ห้ามอยู่บนถนนเดียวกัน ห้ามอยู่ซอยเดียวกัน ห้ามอยู่ในรหัสไปรษณีย์เดียวกัน เป็นต้น หรือแม้แต่ ห้ามอยู่ใกล้ BigC ห้ามอยู่ติดกับ Tesco หรือเงื่อนไขอะไรอื่นๆอีกสารพัด ปัญหา 8-Queen ของเราก็เป็นแค่เวอร์ชั่นตัวแทนของปัญหาพวกนั้นนั่นเอง


มีอีกปัญหานะครับเดี๋ยวมาเติมให้
ปัญหาการจัดตัวผู้เล่น (Optimization Problem)



ปัญหาที่ดูเหมือนว่าจะธรรมดา และมองแล้วอาจไม่เกี่ยวอะไรกับคอมพิวเตอร์พวกนี้ และอีกหลายๆปัญหาคล้ายๆกัน ที่เราจะลองใช้ computer ในการแก้ปัญหาดู และจริงๆแล้วปัญหาพวกนี้ ส่วนใหญ่ มีคนคิดวิธีแก้ไว้หมดแล้ว ทำไมเราต้องมาเริ่มคิดใหม่ เราก็สามารถประยุกต์วิธีแก้ปัญหาของพวกเค้ามาแก้ปัญหาที่คล้ายๆกันได้เลย ซึ่งในวิชา Algorithm Design นี้จะพูดถึง Algorithm ต่างๆที่มีคนคิดไว้แล้วมากมายว่ามันทำงานอย่างไร ใช้งานแบบไหนบ้าง พอเรารู้แล้ว เราก็สามารถมาประยุกต์ใช้กับปัญหาของเรา หรือ ปัญหาใหม่ๆที่ใกล้เคียงกับปัญหาเดิมนั่นเอง

ผมขอนอกเรื่องตรงนี้นิดนึงครับ แน่นอนในบางปัญหาถ้าเรามี โครงสร้างข้อมูล (Data Structure) ที่ดี มันจะทำให้แก้ปัญหาได้มีประสิทธิภาพขึ้น แต่เอาเป็นว่าในวิชานี้ เราแยกเรื่องของ Data Structure ออกไปก่อน เราจะสมมติว่าโครงสร้างข้อมูลที่เราใช้เป็นแบบพื้นฐาน เช่น array แต่ในวิชาถัดไป เราจะว่าด้วยเรื่องของ Data Structure อย่างเดียว แล้วตอนนั้นคุณจะเห็นว่า Data structure มาเสริมกับ Algorithm ได้เป็นอย่างดี ทำให้ Algorithm ของคุณเร็วและฉลาดยิ่งขึ้นไปอีก

ในหลายมหาวิทยาลัยที่หลักสูตรไม่ได้เน้นเรื่องของ Algorithm และ Data Structure มากนัก ก็เลยรวบเอาสองวิชานี้ (Algorithm Design และ Data Structure) มาเป็นวิชาเดียวกันซะเลย ก็ไม่ผิดตรงไหนและไม่แปลกอะไรเพราะทั้งคู่มันต้องไปด้วยกันอยู่แล้ว หรือ บางแห่งก็รวบสาม คือ ควบวิชา Programming เข้ามาด้วย เพื่อให้นักศึกษาได้เห็นภาพรวมก่อน แต่จะได้ส่วนละนิดละหน่อย ซึ่งก็ไม่ว่ากัน แต่ของเราจะแยกทั้ง 3 วิชาออกจากกัน เพราะเราจะได้เจาะละเอียดขึ้นทั้งในส่วนของ Algorithm และ Data structure นั่นเอง (พวก CS และ IT เจอ Data structure ตอนปี 2 เทอม 1 นะครับ)

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



หน้าถัดไป (หน้า 2) »»
หน้าที่ -1- 2-

ความคิดเห็นที่ 17 25 เม.ย. 2551 (20:22)
ขอบคุณ kenessar ที่ตอบครับ วิธีการของคุณดีครับ
แต่ถ้าในการคำนวณ ถ้าเราตรวจสอบจำนวนที่เป็นจำนวนเฉพาะจะช้ามาก
เนื่องจากว่าต้องทำการหารด้วยจำนวนที่น้อยกว่าทุกตัวครับ

ถ้าจำนวนนั้นมาก ๆ ก็จะทำให้ช้าครับ


โดย noonenodead

ความคิดเห็นที่ 16 24 เม.ย. 2551 (13:24)
ที่ผมเคยคิดมา เรื่องการแก้ปัญหาจำนวนเฉพาะในแบบของผมก็คือว่า
ให้หาเลขที่จะทำการทดสอบว่าเป็นจำนวนเฉพาะหรือไม่มาเป็นตัวตั้ง
แล้วไล่หารไปเรื่อยๆตั้งแต่เลข1ไปจนถึงตัวมันเอง หากมีการหารลงตัวเกิน2ครั้ง หมายความว่าไม่ใช่จำนวนเฉพาะครับ

ยกตัวอย่างเช่น
ผมจะตรวจว่าเลข5กับ6เป็นจำนวนเฉพาะหรือไม่
ผมต้องหารแล้วดูเศษ อันไหนลงตัวเกินสองครั้ง มันไม่ใช่จำนวนเฉพาะแล้วครับ

5 หาร 1 = 5 เศษ 0
5 หาร 2 = 2 เศษ 1
5 หาร 3 = 1 เศษ 2
5 หาร 4 = 1 เศษ 1
5 หาร 5 = 1 เศษ 0

สังเกตนะครับว่าหารลงตัวแค่เลข 1 กับตัวมันเอง
ฉะนั้นฟันธง "5 คือจำนวนเฉพาะ"

6 หาร 1 = 6 เศษ 0
6 หาร 2 = 3 เศษ 0
6 หาร 3 = 2 เศษ 0
6 หาร 4 = 1 เศษ 2
6 หาร 5 = 1 เศษ 1
6 หาร 6 = 1 เศษ 0

เอาล่ะครับ จำนวนเฉพาะต้องหารลงตัวแค่ 1 กับตัวมันเองใช่มั้ยครับ
แต่ไอ้เลข 6 นี่จำนวนอื่นๆหารมันลงตัวได้ แล้วมีจำนวนหารลงตัวได้ถึง 4 ตัว

ฉะนั้น "6 ไม่ใช่จำนวนเฉพาะ"

----------------------------------------------------------
การตรวจจับได้ว่าเลขนั้นเป็นจำนวนเฉพาะหรือเปล่า โจทย์บอกเอาไว้ว่า จำนวนเฉพาะคือจำนวนที่หารตัวมันเองและเลข 1 ลงตัว เลขอื่นจะหารมันลงตัวไม่ได้เลย

เคล็ดลับอยู่ที่ "หารลงตัวได้ไม่เกินสองครั้ง"

ถ้าเป็นในการเขียนโปรแกรม ทำอย่างไร ให้นับผลลัพท์ที่หารลงตัวได้
ก็สร้างตัวแปรขึ้นมาตัวหนึ่งเอาไว้นับ
ตอนแรกก็เซ็ต 0 ให้มัน
เมื่อใดที่ทำการตรวจสอบจำนวน
ทันทีที่หารลงตัว ให้ +1 ให้กับตัวนับด้วย
และเมื่อตรวจสอบจำนวนเสร็จ เอาตัวนับมาตรวจสอบ ว่าเกิน 2 หรือไม่ ถ้าเกิน ไม่ใช่จำนวนเฉพาะแล้วครับ

หลังการตรวจสอบแต่ละจำนวน อย่าลืม เซ็ต 0 ให้ตัวนับด้วยนะครับ

ถ้าอยากให้โปรแกรมคำนวณเร็ว ก็ให้ตรวจสอบตัวนับไปในตัวด้วยครับ ถ้าเกิน 2 ปุ๊บ ใช้คำสั่ง break ออกจากลูปเลย

-------------------------------------------------------------
ตัวอย่างโจทย์ปัญหา (มันเป็นภาษาจาวานะครับ)

จงเขียนโปรแกรมเพื่อคำนวณหาตัวเลขที่เป็นจำนวนเฉพาะ 100 ตัวแรก โดยให้แสดงผลบรรทัดละ 10 ตัว ดังตัวอย่างต่อไปนี้


2 3 5 7 11 13 17 19 23 29

31 37 ...

...

-------------------------------------------------
class Prime
{
public static void main(String[] args)
{
int prime=0,i=1,col=1,count=0;
while (prime<100)
{
for (int j=1 ; j<=i ; j++ )
{
if (i%j==0)
{
count++;
}
} // end of for

if (count<=2)
{
if (col>10)
{
col=1;
System.out.println("");
}
System.out.print(i+"\t");
prime++;
col++;
}
i++;
count=0;
} //end of while
} //end of main()
} //end of class Prime

-------------------------------------------------------
87834

โดย kenessar

ความคิดเห็นที่ 15 20 เม.ย. 2551 (12:33)
ช่วยดูทีครับ(อันนี้ source ถูกต้อง)
ตรวจสอบว่าเป็นจำนวนเฉพาะ
ตรวจสอบว่าเป็นจำนวนเฉพาะ
บทความอันนี้ผมพยายามเขียนให้ทุกคนเข้าใจแม้ไม่ได้เรียนอัลกอริทึมหรือภาษา C ภาษา Python หรือภาษาอื่น ๆ ก็ตาม

ผมมีปัญหาเรื่องขั้นตอนการหาจำนวนเฉพาะด้วยคอมพิวเตอร์ ไม่แน่ใจว่าวิธีนี้ถูกต้องหรือเปล่าดังนั้นจึงขอให้ผู้ที่มีความรู้หรือพบข้อผิดพลาดในวิธีการนี้ช่วย โพส ตอบด้วยครับ

จากความเข้าใจของผมคือ จำนวนเฉพาะคือจำนวนที่ มีเพียง 1 และตัวมันเองเท่านั้นที่หารลงตัว (คิดแต่จำนวนเฉพาะบวกเท่านั้น) ผมได้วิธีการจากหนังสือคอมฯ ทั่วไปวิธีหนึ่งซึ่งเป็นวิธีที่ถูกต้องแต่จะช้าถ้าจำนวนที่ต้องการตรวจสอบมีค่ามากๆ คือวิธีดังนี้คือ

สมมติว่าผมต้องการเช็คว่า 1009 เป็นจำนวนเฉพาะหรือไม่
วิธีการคือใช้จำนวนตั้งแต่ 2 ถึง 1008 หารแล้วดูว่ามีตัวใดที่หารลงตัวหรือไม่
ถ้ามีตัวใดที่หารแล้วลงตัวก็ไม่ใช่จำนวนเฉพาะ

แล้วผมก็ตั้งตารอ คอมพิวเตอร์ก็คิดเริ่มจาก
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173,
…………………………., …………………………….., ………………………………..,
886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008
คิดดูครับว่าต้องตรวจสอบด้วยตัวเลขมากมายขนาดไหน
และแล้วจากที่ผมคิดว่า 1009 มันลงท้ายด้วย 9 น่าจะหารด้วย 3 ลงตัว ผมก็ต้องพบกับความผิดหวัง
เพราะว่า 1009 เป็นจำนวนเฉพาะครับ

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

ก่อนอื่นเราต้องการตรวจสอบว่า 1009 เป็นจำนวนเฉพาะหรือเปล่า
(หลักการของอัลกอริทึมต่อไปนี้คือ ตัดตัวที่ไม่จำเป็นต้องคำนวณออกไป และข้ามเลขคู่)
เราจะเริ่มตรวจสอบด้วยการหาร 1009 ด้วย 2, 3, 4, 5, … ไปเรื่อย จนถึง 1008
เรากำลังหาตัวเลขในกลุ่ม 2, 3, 4, ..., 1008 สักตัวที่หาร 1009 ลงตัวเพื่อบอกว่ามันไม่ใช่จำนวนเฉพาะ

เมี่อตัวหารเป็น 2
ขอบเขตการตรวจสอบ 2 ถึง 1008
1009 หาร 2 = 504.5
หารไม่ลงตัว
มาถึงตอนนี้ผมคิดได้ว่า 1009 หาร 504.5 ก็เท่ากับ 2 เพราะฉะนั้น ถ้า 1009 หารด้วยจำนวนที่มากกว่า 504.5 ก็จะได้ผลลัพท์น้อยกว่า 2 ถ้ามีจำนวนที่ มากกว่า 504.5 ที่หาร 1009 ลงตัวละก็ ผลลัพธ์ก็ต้องออกมาเป็น 1 ครับ และตัวนั้นก็คือ 1009 นั่นเอง แสดงว่าตั้งแต่ 504.5 ถึง 1008 ไม่มีตัวใดที่หาร 1009 ลงตัว เราจึงเพียงตรวจสอบจากตัวเลขที่เหลือคือ 3 ถึง 504 (ไม่ถึง 504.5 เพราะไม่ใช่จำนวนเต็ม)

เมี่อตัวหารเป็น 3
ขอบเขตการตรวจสอบ 3ถึง 504

1009 หาร 3 = 336.3333333
หารไม่ลงตัว
เช่นเดียวกับตัวอย่างข้างบน 1009 หาร ด้วยจำนวนที่มากกว่า 336.33 ย่อมได้น้อยกว่า 3 ถ้ามีตัวเลขที่เป็นจำนวนเต็มที่หาร 336.33 ลงตัว ผลหารจะเป็น 2 หรือ 1 ถ้าหารแล้วได้ 2 แสดงว่า 2 ก็หารตัวตั้ง(1009) ลงตัว
ซึ่งตัวเลขนี้ต้องตรวจพบตั้งแต่ขั้นตอนที่แล้ว ๆ (ขั้นตอนที่หารด้วย 2) แต่ถ้าหารได้ 1 ก็คือ 1009 ซึ่งไม่ใช่ตัวเลขในช่วง 2 ถึง 1008
ดังนั้นจำนวนที่เหลือที่ต้องตรวจสอบคือ 4 ถึง 336


เมื่อตัวหารเป็น 4
เราจะไม่เช็คที่ 4 เพราะถ้า 4 หารลงตัว 2 ก็หารลงตัว ซึ่งเราเช็คไปแล้ว

เมื่อตัวหารเป็น 5
ขอบเขตที่ตรวจสอบคือ 5 ถึง 1009 หาร 5 คือ 201.8
หารไม่ลงตัว
ตัวเลขที่มากกว่า 201.8 ก็หาร 1009 ไม่ลงตัวเช่นกัน เราสรุปจากขั้นตอนที่แล้ว เพราะถ้าหารลงตัว ผลหารจะได้ 1, 2, 3, 4 ซึ่งเราเช็คไปแล้ว

เราทำไปเรื่อย ๆ จนกระทั่งตัวหารเป็น 31
แน่นอน 1009 หาร 31 = 32.548 ไม่ลงตัวอยู่แล้ว
ฉะนั้นเราจึงเหลือตัวเลขที่ต้องตรวจสอบเพียง 32 ถึง 32.548 ซึ่ง เหลือเพียง 32 ตัวเดียว
และ 1009 หาร 32 ได้ 31.531 ไม่ลงตัวเช่นกัน
เราจึงตรวจสอบตัวเลข จาก 3 ถึง 1008 ครบทุกตัวแล้ว ปรากฏว่าไม่มีตัวเลขในช่วงนี้ที่หาร 1009 ลงตัว
ดังนั้น เราสรุปว่า 1009 เป็นจำนวนเฉพาะ
จะเห็นได้ว่า เราตรวจสอบแค่ตัวเลขในช่วง 2 ถึง 32 เท่านั้น เราตรวจสอบเพียง 32-2+1 = 31 จำนวนแต่ในอัลกอริทึมของผมจะข้ามเลขคู่ไปยกเว้น 2 จะเหลือการตรวจสอบเพียง 15 จำนวนเท่านั้น

และต่อไปนี้เป็น code ในภาษา C++ ครับ มีภาษา python อันต่อไปด้วย
bool isprime(const unsigned long input){
if(input==1||input==0)
return false;
if(input==2)//Must add this line alway.
return true;
if((input%2)==0)
return false;
unsigned long endrank=input/2;
unsigned long i;
for(i=3;i<=endrank;i+=2){
if((input%i)==0)
return false;
endrank=input/i;
}
return true;
}
คืนค่า true ถ้าเป็นจำนวนเฉพาะ นอกจากนั้นคือค่า false
ต่อไปเป็น code ภาษา Python
# โค้ดภาษา Python
def isprime(chk):
chk=long(chk)
if(chk==0 or chk==1):
return False
if chk==2 :
return True
if (chk%2)==0 :
return False
endrank=chk/2 # endrank คือตัวสุดท้ายที่จะค้นหา
i=3
while i<=endrank :
if (chk%i)==0 : # chk หารด้วย i แล้วลงตัว
return False
endrank=chk/i
i+=2
print i
return True

วานผู้อ่านช่วยตรวจสอบด้วยนะครับ

ปล. แต่ผมพึ่งจำได้ว่าที่เรียนคณิตศาสตร์มามีวิธีคิดอีกอย่างหนึ่ง
ถ้า 1009 เป็นจำนวนเฉพาะ แล้ว จะไม่มี จำนวนเต็มบวกที่มากกว่า 2 แต่น้อยกว่าหรือเท่ากับ รากที่สองของ 1009 หารลงตัว
ซึ่งมันก็จริง เพราะรากที่สองของ 1009 เท่ากับ 31.76476034853718 (คำนวณด้วย IDLE ของ Python)

นี่เป็นอีกเหตุผลหนึ่งว่าอัลกอริทึมที่เขียนด้วยโปรแกรมเมอร์ ที่เก่งและชำนาญคณิตศาสตร์ มีความรวดเร็ว
แต่บางครั้งอัลกอรึทึมนี้น่าจะเป็นการคิดสร้างสรรค์ที่ดีก็ได้นะครับ ฝึกให้เราคิดหาวิธีที่ดีที่สุด

ขอบคุณ คนที่อ่าน และ Post แสดงความคิดเห็น ที่สำคัญคนที่ช่วยตรวจสอบด้วยนะครับ

noonenodead
(no one no dead)


โดย noonenodead

ความคิดเห็นที่ 14 20 เม.ย. 2551 (12:30)
ช่วยดูทีครับ
ตรวจสอบว่าเป็นจำนวนเฉพาะ
บทความอันนี้ผมพยายามเขียนให้ทุกคนเข้าใจแม้ไม่ได้เรียนอัลกอริทึมหรือภาษา C ภาษา Python หรือภาษาอื่น ๆ ก็ตาม

ผมมีปัญหาเรื่องขั้นตอนการหาจำนวนเฉพาะด้วยคอมพิวเตอร์ ไม่แน่ใจว่าวิธีนี้ถูกต้องหรือเปล่าดังนั้นจึงขอให้ผู้ที่มีความรู้หรือพบข้อผิดพลาดในวิธีการนี้ช่วย โพส ตอบด้วยครับ

จากความเข้าใจของผมคือ จำนวนเฉพาะคือจำนวนที่ มีเพียง 1 และตัวมันเองเท่านั้นที่หารลงตัว (คิดแต่จำนวนเฉพาะบวกเท่านั้น) ผมได้วิธีการจากหนังสือคอมฯ ทั่วไปวิธีหนึ่งซึ่งเป็นวิธีที่ถูกต้องแต่จะช้าถ้าจำนวนที่ต้องการตรวจสอบมีค่ามากๆ คือวิธีดังนี้คือ

สมมติว่าผมต้องการเช็คว่า 1009 เป็นจำนวนเฉพาะหรือไม่
วิธีการคือใช้จำนวนตั้งแต่ 2 ถึง 1008 หารแล้วดูว่ามีตัวใดที่หารลงตัวหรือไม่
ถ้ามีตัวใดที่หารแล้วลงตัวก็ไม่ใช่จำนวนเฉพาะ

แล้วผมก็ตั้งตารอ คอมพิวเตอร์ก็คิดเริ่มจาก
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173,
…………………………., …………………………….., ………………………………..,
886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008
คิดดูครับว่าต้องตรวจสอบด้วยตัวเลขมากมายขนาดไหน
และแล้วจากที่ผมคิดว่า 1009 มันลงท้ายด้วย 9 น่าจะหารด้วย 3 ลงตัว ผมก็ต้องพบกับความผิดหวัง
เพราะว่า 1009 เป็นจำนวนเฉพาะครับ

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

ก่อนอื่นเราต้องการตรวจสอบว่า 1009 เป็นจำนวนเฉพาะหรือเปล่า
(หลักการของอัลกอริทึมต่อไปนี้คือ ตัดตัวที่ไม่จำเป็นต้องคำนวณออกไป และข้ามเลขคู่)
เราจะเริ่มตรวจสอบด้วยการหาร 1009 ด้วย 2, 3, 4, 5, … ไปเรื่อย จนถึง 1008
เรากำลังหาตัวเลขในกลุ่ม 2, 3, 4, ..., 1008 สักตัวที่หาร 1009 ลงตัวเพื่อบอกว่ามันไม่ใช่จำนวนเฉพาะ

เมี่อตัวหารเป็น 2
ขอบเขตการตรวจสอบ 2 ถึง 1008
1009 หาร 2 = 504.5
หารไม่ลงตัว
มาถึงตอนนี้ผมคิดได้ว่า 1009 หาร 504.5 ก็เท่ากับ 2 เพราะฉะนั้น ถ้า 1009 หารด้วยจำนวนที่มากกว่า 504.5 ก็จะได้ผลลัพท์น้อยกว่า 2 ถ้ามีจำนวนที่ มากกว่า 504.5 ที่หาร 1009 ลงตัวละก็ ผลลัพธ์ก็ต้องออกมาเป็น 1 ครับ และตัวนั้นก็คือ 1009 นั่นเอง แสดงว่าตั้งแต่ 504.5 ถึง 1008 ไม่มีตัวใดที่หาร 1009 ลงตัว เราจึงเพียงตรวจสอบจากตัวเลขที่เหลือคือ 3 ถึง 504 (ไม่ถึง 504.5 เพราะไม่ใช่จำนวนเต็ม)

เมี่อตัวหารเป็น 3
ขอบเขตการตรวจสอบ 3ถึง 504

1009 หาร 3 = 336.3333333
หารไม่ลงตัว
เช่นเดียวกับตัวอย่างข้างบน 1009 หาร ด้วยจำนวนที่มากกว่า 336.33 ย่อมได้น้อยกว่า 3 ถ้ามีตัวเลขที่เป็นจำนวนเต็มที่หาร 336.33 ลงตัว ผลหารจะเป็น 2 หรือ 1 ถ้าหารแล้วได้ 2 แสดงว่า 2 ก็หารตัวตั้ง(1009) ลงตัว
ซึ่งตัวเลขนี้ต้องตรวจพบตั้งแต่ขั้นตอนที่แล้ว ๆ (ขั้นตอนที่หารด้วย 2) แต่ถ้าหารได้ 1 ก็คือ 1009 ซึ่งไม่ใช่ตัวเลขในช่วง 2 ถึง 1008
ดังนั้นจำนวนที่เหลือที่ต้องตรวจสอบคือ 4 ถึง 336


เมื่อตัวหารเป็น 4
เราจะไม่เช็คที่ 4 เพราะถ้า 4 หารลงตัว 2 ก็หารลงตัว ซึ่งเราเช็คไปแล้ว

เมื่อตัวหารเป็น 5
ขอบเขตที่ตรวจสอบคือ 5 ถึง 1009 หาร 5 คือ 201.8
หารไม่ลงตัว
ตัวเลขที่มากกว่า 201.8 ก็หาร 1009 ไม่ลงตัวเช่นกัน เราสรุปจากขั้นตอนที่แล้ว เพราะถ้าหารลงตัว ผลหารจะได้ 1, 2, 3, 4 ซึ่งเราเช็คไปแล้ว

เราทำไปเรื่อย ๆ จนกระทั่งตัวหารเป็น 31
แน่นอน 1009 หาร 31 = 32.548 ไม่ลงตัวอยู่แล้ว
ฉะนั้นเราจึงเหลือตัวเลขที่ต้องตรวจสอบเพียง 32 ถึง 32.548 ซึ่ง เหลือเพียง 32 ตัวเดียว
และ 1009 หาร 32 ได้ 31.531 ไม่ลงตัวเช่นกัน
เราจึงตรวจสอบตัวเลข จาก 3 ถึง 1008 ครบทุกตัวแล้ว ปรากฏว่าไม่มีตัวเลขในช่วงนี้ที่หาร 1009 ลงตัว
ดังนั้น เราสรุปว่า 1009 เป็นจำนวนเฉพาะ
จะเห็นได้ว่า เราตรวจสอบแค่ตัวเลขในช่วง 2 ถึง 32 เท่านั้น เราตรวจสอบเพียง 32-2+1 = 31 จำนวนแต่ในอัลกอริทึมของผมจะข้ามเลขคู่ไปยกเว้น 2 จะเหลือการตรวจสอบเพียง 15 จำนวนเท่านั้น

และต่อไปนี้เป็น code ในภาษา C++ ครับ มีภาษา python อันต่อไปด้วย
bool isprime(const unsigned long input){
if(input==1||input==0)
return false;
if(input==2)//Must add this line alway.
return true;
if((input%2)==0)
return false;
unsigned long endrank=input/2;
unsigned long i;
for(i=3;i<=endrank;i+=2){
if((input%i)==0)
return false;
endrank=input/i;
}
return true;
}
คืนค่า true ถ้าเป็นจำนวนเฉพาะ นอกจากนั้นคือค่า false
ต่อไปเป็น code ภาษา Python
# โค้ดภาษา Python
def isprime(chk):
chk=long(chk)
if(chk==0 or chk==1):
return False
if chk==2 :
return True
if (chk%2)==0 :
return False
endrank=chk/2 # endrank คือตัวสุดท้ายที่จะค้นหา
i=3
while i<=endrank :
if (chk%i)==0 : # chk หารด้วย i แล้วลงตัว
return False
endrank=chk/i
i+=2
print i
return True

วานผู้อ่านช่วยตรวจสอบด้วยนะครับ

ปล. แต่ผมพึ่งจำได้ว่าที่เรียนคณิตศาสตร์มามีวิธีคิดอีกอย่างหนึ่ง
ถ้า 1009 เป็นจำนวนเฉพาะ แล้ว จะไม่มี จำนวนเต็มบวกที่มากกว่า 2 แต่น้อยกว่าหรือเท่ากับ รากที่สองของ 1009 หารลงตัว
ซึ่งมันก็จริง เพราะรากที่สองของ 1009 เท่ากับ 31.76476034853718 (คำนวณด้วย IDLE ของ Python)

นี่เป็นอีกเหตุผลหนึ่งว่าอัลกอริทึมที่เขียนด้วยโปรแกรมเมอร์ ที่เก่งและชำนาญคณิตศาสตร์ มีความรวดเร็ว
แต่บางครั้งอัลกอรึทึมนี้น่าจะเป็นการคิดสร้างสรรค์ที่ดีก็ได้นะครับ ฝึกให้เราคิดหาวิธีที่ดีที่สุด

ขอบคุณ คนที่อ่าน และ Post แสดงความคิดเห็น ที่สำคัญคนที่ช่วยตรวจสอบด้วยนะครับ

noonenodead
(no one no dead)


โดย noonenodead

ความคิดเห็นที่ 13 20 เม.ย. 2551 (12:28)
ผมมีข้อสงสัยช่วยอบทีครับ
ทดสอบว่าเป็นจำนวนเฉพาะ.pdf

โดย noonenodead

ความคิดเห็นที่ 11 5 เม.ย. 2551 (23:50)
เป็นบทความที่ดีมากครับ แต่หลายๆปัญหาก็ค้างคาใจผมเหมือนกัน แก้ไม่ค่อยออกเลยบางที หุหุ

โดย -+Infinite Life+-

ความคิดเห็นที่ 10 26 มี.ค. 2551 (02:13)
ชอบครับ

โดย suratat

ความคิดเห็นที่ 7 10 ม.ค. 2551 (21:17)
Star to You

โดย varayus

ความคิดเห็นที่ 6 7 ม.ค. 2551 (11:44)
ปัญหาพวกนี้ถึงจะเป็นคำถามที่คลาสสิก แต่ก็ทำให้งงได้ในบางทีเหมือนกันนะครับ

โดย tonkuaw

ความคิดเห็นที่ 5 16 ธ.ค. 2550 (23:33)
อุอุ เรื่องนี้อนกันยาก นะ อัลกอเนี่ย ขึ้นอยู่กับ ความฉลาด(IQ)ของแต่ละคนด้วย ยิ่ง โปรแกรมเมอร์ ถ้าอยากเก่ง ต้องเขียนโปรแกรมให้ อัลกอ ดีถ้าไม่ดี ไม่ดังแน่ คริๆ เขียนโปรแกรมง่ายนะ ถ้าจะให้มันคิดคำตอบออก แต่ยากตรงที่ทำยังไง ให้มันสั้นสุด ดีสุด

โดย Runa-Light

ขอโทษครับ กรุณา login ก่อนถึงจะสามารถแสดงความคิดเห็นได้ครับ

ล๊อกอินถาวร | Login: Password: สมัครสมาชิกใหม่ | ลืม password
xx
Google
 
ติดต่อลงโฆษณา :   คุณอันนา 081 4965363
สำนักงาน :   02 2015735
อีเมล์ :   
Copyright© 2000-2007, Vcharkarn.Com. All rights reserved.
คลิ๊กเพื่อดูสถิติ
รับรองและสนับสนุนโดย

สสวท.

มูลนิธิ พสวท.

พสวท.