ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6"

รุ่นแก้ไขเมื่อ 08:30, 3 ตุลาคม 2552

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

ให้ $OPT(i,j)\,$ คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง $s[i,i+1,...,j]\,$

พิจารณากรณีที่ $i>j\,$ จะได้ว่า $OPT(i,j)=0\,$

กรณีที่ $i=j\,$ จะได้ว่า $OPT(1,1)=1\,$

ส่วนกรณีที่เหลือจะได้ว่า $OPT(i,j)=max(OPT(i+1,j),OPT(i,j-1))\,$ ถ้า $s[i]!=s[j]\,$

หรือ $OPT(i,j)=max(OPT(i+1,j),OPT(i,j-1),OPT(i+1,j-1))\,$ ถ้า $s[i]=s[j]\,$

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> PALINDROMIC(s,n)

   i =1
   j = n
   if i < j then
       return 0
   else if i = j then
       return 1
   else
       if s[i] != s[j] then
           M[i,j] = max(M[i+1,j],M[i,j-1])
       else
           M[i,j] = max(M[i+1,j],M[i,j-1],M[i+1,j-1])
   return M[1,n]

</geshi>

ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6"

รุ่นแก้ไขเมื่อ 08:30, 3 ตุลาคม 2552

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 2: / แถว 2: @@
 ให้ <math> OPT(i,j) \,</math> คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง <math> s[i,i+1,...,j] \,</math>
+พิจารณากรณีที่ <math> i > j \,</math> จะได้ว่า <math> OPT(i,j) = 0 \,</math>
+กรณีที่ <math> i=j \,</math> จะได้ว่า <math> OPT(1,1)=1 \,</math>
+ส่วนกรณีที่เหลือจะได้ว่า <math> OPT(i,j)= max(OPT(i+1,j),OPT(i,j-1))\,</math> ถ้า <math> s[i] != s[j] \,</math>
+หรือ <math> OPT(i,j) = max(OPT(i+1,j),OPT(i,j-1),OPT(i+1,j-1))\,</math> ถ้า <math> s[i] = s[j] \,</math>
+เขียนเป็น pseudocode ได้ดังนี้
+<geshi lang="c">
+PALINDROMIC(s,n)
+    i =1
+    j = n
+    if i < j then
+        return 0
+    else if i = j then
+        return 1
+    else
+        if s[i] != s[j] then
+            M[i,j] = max(M[i+1,j],M[i,j-1])
+        else
+            M[i,j] = max(M[i+1,j],M[i,j-1],M[i+1,j-1])
+    return M[1,n]
+</geshi>