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

รุ่นแก้ไขปัจจุบันเมื่อ 09:47, 4 กันยายน 2552

อินพุต: ลำดับของจำนวนเต็ม $n\,$ จำนวน และช่วง $[p,q]\,$

เอาพุต: จำนวนของลำดับย่อยที่มีพิสัยในช่วง $[p,q]\,$

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

จากแนวคิดข้างต้น นำมาเขียนเป็น 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 สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก $O(n)\,$ ดังนั้นเวลารวมของสองขั้นตอนนี้คือ $O(n^{3})\,$ ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง $[p,q]\,$ หรือไม่ใช้เวลาอีก $q-p+1\,$ ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น $O(n^{3})\,$

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

รุ่นแก้ไขปัจจุบันเมื่อ 09:47, 4 กันยายน 2552

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 7: / แถว 7: @@
 จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
+<geshi lang="c">
 FINDMAX(A,i,j)
-:max<-- -1000000
+{
-:for k=i to i<=j
+    max<-- -1000000
-::if A[k] > max
+    for k=i to i<=j
-::: max= A[k]
+    {
-::: max_k=k
+        if A[k] > max
-: return max_k
+        {
+             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
+     min<-- 1000000
-::if A[k] < min
+     for k=i to k<=j
-::: min= A[k]
+     {
-::: min_k=k
+         if A[k] < min
-: return min_k
+         {
+             min= A[k]
+             min_k=k
+         }
+     }
+     return min_k
+}
+</geshi>
+<geshi lang="c">
 COUNTINTERVAL(A,n)
-:count <-- 0
+{
-:for i=0 to i<n
+     count <-- 0
-:: for j=i to j<n
+     for i=0 to i<n
-::: max=FINDMAX(A,i,j)
+     {
-::: min=FINDMIN(A,i,j)
+         for j=i to j<n
-::: r=max-min
+         {
-::: for k=p to k<=q
+            max=FINDMAX(A,i,j)
-:::: if r=k
+            min=FINDMIN(A,i,j)
-:::::   count <-- count + 1
+            r=max-min
-: return count
+            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 สองชั้น และการคำนวณค่าพิสัยของแต่ละลำดับย่อยใช้เวลาอีก <math>O(n) \,</math> ดังนั้นเวลารวมของสองขั้นตอนนี้คือ<math>O(n^3) \,</math> ส่วนการตรวจสอบว่าค่าพิสัยของลำดับย่อยอยู่ในช่วง <math>[p,q] \,</math> หรือไม่ใช้เวลาอีก <math>q-p+1 \, </math> ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(n^3) \,</math>