ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 1"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
อินพุต: เซตของจำนวนเต็ม <math>A=\{ a_1, a_2,... ,a_n \} \, </math> ที่มีสมาชิก <math> n \, </math> ตัว และจำนวนเต็ม <math> S \, </math> | อินพุต: เซตของจำนวนเต็ม <math>A=\{ a_1, a_2,... ,a_n \} \, </math> ที่มีสมาชิก <math> n \, </math> ตัว และจำนวนเต็ม <math> S \, </math> | ||
| + | |||
| + | เอาพุต: คำตอบว่า "ใช่" หรือ "ไม่ใช่" | ||
| + | |||
| + | แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต <math>A \,</math> ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่นั่นเอง | ||
| + | |||
| + | จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้ | ||
| + | |||
| + | เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง | ||
รุ่นแก้ไขเมื่อ 05:36, 18 สิงหาคม 2552
อินพุต: เซตของจำนวนเต็ม ที่มีสมาชิก ตัว และจำนวนเต็ม
เอาพุต: คำตอบว่า "ใช่" หรือ "ไม่ใช่"
แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม หรือไม่นั่นเอง
จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้
เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ หรือไม่ ซึ่งใช้เวลาอย่างมาก ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ นั่นเอง
