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

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 09:47, 4 กันยายน 2552 โดย Aoy (คุย | มีส่วนร่วม)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

อินพุต: ลำดับของจำนวนเต็ม จำนวน และช่วง

เอาพุต: จำนวนของลำดับย่อยที่มีพิสัยในช่วง

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

จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> FINDMAX(A,i,j) {

   max<-- -1000000
   for k=i to i<=j
   {
       if A[k] > max
       { 
            max= A[k]
            max_k=k
       }
   }
   return max_k

} </geshi>

<geshi lang="c"> FINDMIN(A,i,j) {

    min<-- 1000000
    for k=i to k<=j
    {
        if A[k] < min
        {
            min= A[k]
            min_k=k
        }
    }
    return min_k

} </geshi>

<geshi lang="c"> COUNTINTERVAL(A,n) {

    count <-- 0
    for i=0 to i<n
    {
        for j=i to j<n
        {
           max=FINDMAX(A,i,j)
           min=FINDMIN(A,i,j)
           r=max-min
           for k=p to k<=q
           { 
                if r=k
                     count <-- count + 1
           } //end for k
         } //end for j
    } //end for i
     return count

} </geshi>

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