ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย 'ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่…')
 
แถว 12: แถว 12:
 
* <math>A[i+1] > B[j] \,</math> และ
 
* <math>A[i+1] > B[j] \,</math> และ
 
* <math>B[j+1] > A[i] \,</math>
 
* <math>B[j+1] > A[i] \,</math>
แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> คือ <math>A[i+1] \,</math> หรือไม่ก็ <math>B[j+1] \,</math>
+
แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> คือ <math>\min(A[i+1], B[j+1]) \,</math>
  
'''พิสูจน์:'''
+
'''พิสูจน์:''' ให้ <math>x \,</math> เป็นจำนวนที่น้อยกว่าระหว่าง <math>A[i+1] \,</math> และ <math>B[j+1] \,</math> แล้วจะได้ว่ามีจำนวน <math>i \,</math> ตัวใน <math>A \,</math> ที่น้อยกว่า <math>x \,</math> และจำนวน <math>j \,</math> ตัวใน <math>B \,</math> ที่น้อยกว่ามัน ฉะนั้นมีจำนวน <math>i + j = k-1 \,</math> ตัวใน <math>A \,</math> และ <math>B \,</math> ที่น้อยกว่ามันพอดี ดังนั้น <math>x \,</math> เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> พอดี

รุ่นแก้ไขเมื่อ 13:53, 2 กันยายน 2552

ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่ผ่านๆ มา แต่วัตถุที่เราทำการค้นหาจะแตกต่างจากข้ออื่นมาก

เพื่อความสะดวก เราจะกำหนดให้อะเรย์ และ มีช่อง และ โดยที่ และ กล่าวคือ และ จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด

เราจะพิสูจน์ข้อความสองข้อความต่อไปนี้


lemma 1: ถ้า และ เป็นจำนวนเต็มที่

  • และ
  • และ
  • และ
  • และ

แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ ในอะเรย์ และ คือ

พิสูจน์: ให้ เป็นจำนวนที่น้อยกว่าระหว่าง และ แล้วจะได้ว่ามีจำนวน ตัวใน ที่น้อยกว่า และจำนวน ตัวใน ที่น้อยกว่ามัน ฉะนั้นมีจำนวน ตัวใน และ ที่น้อยกว่ามันพอดี ดังนั้น เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ พอดี