ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 3"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 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
else
for c[l-1] = l to m
GENERATE(c[l-1]-1,l-1)

เวลาการทำงานของอัลกอริทึมข้างต้น คือเวลาที่ใช้ในการคำนวณหา 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

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