ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 3"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
แถว 21: | แถว 21: | ||
== ข้อย่อย 2 == | == ข้อย่อย 2 == | ||
+ | สังเกตว่าถ้าเราเรียงจำนวนที่อยู่ใน A ได้แล้ว พิจารณาจำนวน <math>a \in A \,</math> เราจะทำการตรวจสอบจำนวนที่ติดกับ <math>a \,</math> ไปทางขวาอีกแค่สองตัวเท่านั้น (นั่นคือจำนวน <math>b,c \,</math> จะอยู่ทางขวาของ a ไปอีกสองตำแหน่ง) ตามเงื่อนไข <math>a < b < c \,</math> เพราะจำนวนถัดไปจำนวนที่สาม ตรวจสอบไปก็ไม่เกิดประโยชน์ ดังนั้นการเรียงจำนวนที่อยู่ใน A ก่อนจะทำให้เราลดจำนวนวัตถุที่เราต้องพิจารณาลงไปได้ | ||
+ | |||
+ | ซึ่งจากแนวคิดดังกล่าวนำมาเขียนเป็น pseudocode ได้ดังนี้ | ||
+ | |||
+ | GENERATE(A) | ||
+ | :for i=0 to i < n | ||
+ | :: if A[i] + A[i+1] > A[i+2] | ||
+ | ::: return 1 | ||
+ | :: else | ||
+ | ::: return 0 | ||
+ | |||
+ | ซึ่งเราจะได้ว่าเวลาการทำงานของอัลกอริทึมข้างต้นคือเวลาที่ใช้ในการเรียง A ก่อนหน้านี้ กับเวลาที่สมาชิกในแต่ละตัวตรวจสอบกับสมาชิกตัวถัดไปอีกสองตัว ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(f(n)+ n)\,</math> |
รุ่นแก้ไขเมื่อ 07:08, 2 กันยายน 2552
ข้อย่อย 1
อินพุต: เซตของจำนวนเต็ม ที่มีสมาชิกอยู่ ตัว
เอาพุต: มีจำนวนเต็ม โดยที่ และ หรือไม่
แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ สิ่ง จากของทั้งหมด สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ หรือไม่
จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้ (ให้ค่า l=3)
GENERATE(m,l)
- if l=0
- if c[0] + c[1] > c[2] // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
- then return 1
- else
- return 0
- if c[0] + c[1] > c[2] // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
- else
- for c[l-1] = l to m
- GENERATE(c[l-1]-1,l-1)
- for c[l-1] = l to m
เวลาการทำงานของอัลกอริทึมข้างต้น คือเวลาที่ใช้ในการคำนวณหา combination ที่มีสมาชิก 3 ตัว คือ นั่นเอง
ข้อย่อย 2
สังเกตว่าถ้าเราเรียงจำนวนที่อยู่ใน A ได้แล้ว พิจารณาจำนวน เราจะทำการตรวจสอบจำนวนที่ติดกับ ไปทางขวาอีกแค่สองตัวเท่านั้น (นั่นคือจำนวน จะอยู่ทางขวาของ a ไปอีกสองตำแหน่ง) ตามเงื่อนไข เพราะจำนวนถัดไปจำนวนที่สาม ตรวจสอบไปก็ไม่เกิดประโยชน์ ดังนั้นการเรียงจำนวนที่อยู่ใน A ก่อนจะทำให้เราลดจำนวนวัตถุที่เราต้องพิจารณาลงไปได้
ซึ่งจากแนวคิดดังกล่าวนำมาเขียนเป็น pseudocode ได้ดังนี้
GENERATE(A)
- for i=0 to i < n
- if A[i] + A[i+1] > A[i+2]
- return 1
- else
- return 0
- if A[i] + A[i+1] > A[i+2]
ซึ่งเราจะได้ว่าเวลาการทำงานของอัลกอริทึมข้างต้นคือเวลาที่ใช้ในการเรียง A ก่อนหน้านี้ กับเวลาที่สมาชิกในแต่ละตัวตรวจสอบกับสมาชิกตัวถัดไปอีกสองตัว ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น