ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
แถว 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>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: ถ้า และ เป็นจำนวนเต็มที่
- และ
- และ
- และ
- และ
แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ ในอะเรย์ และ คือ
พิสูจน์: ให้ เป็นจำนวนที่น้อยกว่าระหว่าง และ แล้วจะได้ว่ามีจำนวน ตัวใน ที่น้อยกว่า และจำนวน ตัวใน ที่น้อยกว่ามัน ฉะนั้นมีจำนวน ตัวใน และ ที่น้อยกว่ามันพอดี ดังนั้น เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ พอดี