ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 2"
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'อินพุต: อะเรย์ <math> A[.] \, </math> ที่เรียงจากน้อยไปหามากแล้…') |
|||
| (ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน) | |||
| แถว 15: | แถว 15: | ||
เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้ | เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้ | ||
| + | <geshi lang="c"> | ||
FindI(a,b,e) | FindI(a,b,e) | ||
| − | + | { | |
| − | + | if e < b | |
| − | + | return -1 | |
| − | + | else | |
| − | + | k=(b+e)/2 | |
| − | + | if a[k] = k | |
| − | + | return k | |
| − | + | else if a[k] > k | |
| − | + | retrun FindI(a,b,k-1) | |
| − | + | else if a[k] < k | |
| + | return FindI(a,k+1,e) | ||
| + | } | ||
| + | </geshi> | ||
ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี | ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี | ||
รุ่นแก้ไขปัจจุบันเมื่อ 04:22, 28 กรกฎาคม 2553
อินพุต: อะเรย์ ที่เรียงจากน้อยไปหามากแล้ว โดยที่ตัวเลขทุกตัวในอะเรย์มีค่าต่างกัน
![{\displaystyle A[.]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d7c94f2709bd2a774f6ba82f90c80116d6baeb6)
เอาพุต: ตอบว่ามี ถ้ามี และไม่มีถ้ากรณีดังกล่าวไม่เป็นจริง
![{\displaystyle A[i]=i\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecc875193bdfa68566ffcd6bf44216fa0bfe21ad)
วัตถุที่เราต้องตรวจสอบคือ ตัวเลข โดยที่เงื่อนไขคือ ตัวเลข ที่อยู่ในช่วงดังกล่าวที่ทำให้ และโจทย์ต้องการให้เวลาการทำงานทั้งหมดเป็น ดังนั้นเราจะใช้ binary search ที่เรียนกันไปในห้องเรียน
เนื่องจากเราใช้ binary search เราต้องรู้ให้ได้ว่าเงื่อนไขสามเงื่อนไขที่ใช้ในการตรวจสอบคืออะไร
แน่นอนว่าเงื่อนไขในการหยุดคือ พิจารณากรณีที่ สมมติให้ เนื่องจากอะเรย์เรียงจากน้อยไปมากแล้ว ดังนั้นเมื่อพิจารณาอะเรย์ฝั่งซ้ายของตำแหน่งที่ จะได้ สำหรับ index ดังนั้นคำตอบ ที่จะทำให้ จึงไม่อยู่ในฝั่งซ้ายนี้แน่นอน เพราะว่าค่าในอะเรย์ทุกค่าน้อยกว่า ค่า index มันหมดเลย ดังนั้นเราจึงควรไปค้นหาในฝั่งขวา และเมื่อพิจารณาแบบเดียวกันก็จะได้เงื่อนไขทั้งสามเงื่อนไขเป็นดังนี้
![{\displaystyle A[i]<i\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c76fa0da618bf27fb165367ec7fb6b045b557596)
![{\displaystyle A[i]=x\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c0021eb2fccaa7a3d4cbec53a38b42540fe47c)
![{\displaystyle A[i-1]\leq x-1,A[i-2]\leq x-2,A[i-3]\leq x-3\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3621095b97715c6d0ae7ba77abdc32df486fb0fb)
- เงื่อนไขหยุดคือ
- เงื่อนไขไปทางซ้ายคือ
- เงื่อนไขไปทางขวาคือ
![{\displaystyle A[i]>i\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5fc11fde9a30f7377b3c0533850505938dcb09e)
เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้
<geshi lang="c"> FindI(a,b,e) { if e < b
return -1
else
k=(b+e)/2
if a[k] = k
return k
else if a[k] > k
retrun FindI(a,b,k-1)
else if a[k] < k
return FindI(a,k+1,e)
} </geshi>
ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น เหมือน binary serach พอดี
