ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 1"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 4: | แถว 4: | ||
แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต <math>A \,</math> ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่นั่นเอง | แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต <math>A \,</math> ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่นั่นเอง | ||
| + | |||
| + | ให้อะเรย์ A เก็บค่าจำนวนเต็ม <math> n /, </math> ตัว อะเรย์ G แต่ละช่องเก็บค่า 1 หรือ 2 ถ้า G[i] เก็บค่า 1 หมายถึง สมาชิกตัวที่ i ในอะเรย์ A เป็นสมาชิกของซับเซต แต่ถ้าเก็บค่า 2 คือไม่เป็นสมาชิกของซับเซต | ||
จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้ | จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้ | ||
| แถว 9: | แถว 11: | ||
SUM(A,G,n) | SUM(A,G,n) | ||
| − | :sum <- 0 | + | :sum <-- 0 |
| − | :for i<-0 to n-1 | + | ::for i<--0 to n-1 |
| − | :if | + | :::if G[i] = 1 |
| − | :sum = sum + A[i] | + | ::::sum = sum + A[i] |
| − | :return(sum) | + | ::return(sum) |
เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง | เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง | ||
รุ่นแก้ไขเมื่อ 06:32, 18 สิงหาคม 2552
อินพุต: เซตของจำนวนเต็ม ที่มีสมาชิก ตัว และจำนวนเต็ม
เอาพุต: คำตอบว่า "ใช่" หรือ "ไม่ใช่"
แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม หรือไม่นั่นเอง
ให้อะเรย์ A เก็บค่าจำนวนเต็ม ตัว อะเรย์ G แต่ละช่องเก็บค่า 1 หรือ 2 ถ้า G[i] เก็บค่า 1 หมายถึง สมาชิกตัวที่ i ในอะเรย์ A เป็นสมาชิกของซับเซต แต่ถ้าเก็บค่า 2 คือไม่เป็นสมาชิกของซับเซต
จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้
SUM(A,G,n)
- sum <-- 0
- for i<--0 to n-1
- if G[i] = 1
- sum = sum + A[i]
- return(sum)
เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ หรือไม่ ซึ่งใช้เวลาอย่างมาก ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ นั่นเอง
