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

รุ่นแก้ไขปัจจุบันเมื่อ 07:40, 22 ตุลาคม 2552

ให้ $OPT(i,j)\,$ เป็นความยาวที่มากที่สุดของ common subsequence ของ $x[1...i]\,$ และ $y[1...j]\,$

แนวคิดจะทำการพิจารณาว่าตัวอักษร $y_{j}\,$ ตรงกับตัวอักษร $x_{i}\,$ หรือไม่ ถ้าตรงแสดงว่าเราได้ common subsequence มาแล้วหนึ่งตัว แต่ถ้าไม่ตรง อาจเป็นไปได้ที่ตัวอักษร $y_{j}\,$ นี้ไปตรงกับตัวอักษรที่ $x_{i-1}\,$ หรือ ตัวอักษร $x_{i}\,$ ไปตรงกับตัวอักษร $y_{j-1}\,$ ซึ่งการที่เราจะเลือกกรณีไหน ก็ขึ้นอยู่กับว่ากรณีนั้นต้องมี common subsequence ยาวที่สุด ดังนั้นเราจะได้ว่า

$OPT(i,j)=0\,$ ถ้า $i=0\,$ หรือ $j=0\,$

$OPT(i,j)=max(OPT(i-1,j),OPT(i,j-1))\,$ ถ้า $x_{i}!=y_{j}\,$

$OPT(i,j)=1+OPT(i-1,j-1)\,$ ถ้า $x_{i}=y_{j}\,$

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

<geshi lang="c"> LCS(x,n,y,m)

   for i=1 to n do
       M[i,0] = 0
   for j=1 to m do
       M[0,j] = 0
   for i = 1 to n do
       for j = 1 to m do
           if x[i] = y[j] then
               M[i,j] = 1+M[i-1,j-1]
           else
               M[i,j] = max(M[i-1,j],M[i,j-1])
   return M[n,m]

</geshi>

เห็นได้ชัดว่าอัลกอริทึมข้างต้นใช้เวลาทำงานเป็น $O(n)+O(m)+O(nm)=O(nm)\,$

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

รุ่นแก้ไขปัจจุบันเมื่อ 07:40, 22 ตุลาคม 2552

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 1: / แถว 1: @@
-ให้ <math> OPT(i,j) \,</math> เป็นความยาวที่มากที่สุดของ common substring ของ <math> x[1...i] \,</math> และ <math> y[1...j] \,</math>
+ให้ <math> OPT(i,j) \,</math> เป็นความยาวที่มากที่สุดของ common subsequence ของ <math> x[1...i] \,</math> และ <math> y[1...j] \,</math>
-แนวคิดจะทำการพิจารณาว่าตัวอักษร <math> y_j \,</math> ตรงกับตัวอักษร <math> x_i \,</math> หรือไม่ ถ้าตรงแสดงว่าเราได้ common substring มาแล้วหนึ่งตัว แต่ถ้าไม่ตรง อาจเป็นไปได้ที่ตัวอักษร <math> y_j \,</math> นี้ไปตรงกับตัวอักษรที่ <math> x_{i-1} \,</math> หรือ ตัวอักษร <math> x_i \,</math> ไปตรงกับตัวอักษร <math> y_{j-1} \,</math> ซึ่งการที่เราจะเลือกกรณีไหน ก็ขึ้นอยู่กับว่ากรณีนั้นต้องมี common substring ยาวที่สุด ดังนั้นเราจะได้ว่า
+แนวคิดจะทำการพิจารณาว่าตัวอักษร <math> y_j \,</math> ตรงกับตัวอักษร <math> x_i \,</math> หรือไม่ ถ้าตรงแสดงว่าเราได้ common subsequence มาแล้วหนึ่งตัว แต่ถ้าไม่ตรง อาจเป็นไปได้ที่ตัวอักษร <math> y_j \,</math> นี้ไปตรงกับตัวอักษรที่ <math> x_{i-1} \,</math> หรือ ตัวอักษร <math> x_i \,</math> ไปตรงกับตัวอักษร <math> y_{j-1} \,</math> ซึ่งการที่เราจะเลือกกรณีไหน ก็ขึ้นอยู่กับว่ากรณีนั้นต้องมี common subsequence ยาวที่สุด ดังนั้นเราจะได้ว่า
 <math> OPT(i,j) = 0 \,</math> ถ้า <math> i= 0 \,</math> หรือ <math> j=0 \,</math>
-<math> OPT(i,j)= max(OPT(i-1,j),OPT(i,j-1) \,</math> ถ้า <math> x_i != y_j \,</math>
+<math> OPT(i,j)= max(OPT(i-1,j),OPT(i,j-1)) \,</math> ถ้า <math> x_i != y_j \,</math>
-<math> OPT(i,j) = 1+OPT(i-1,j-1))\,</math> ถ้า <math> x_i=y_j \,</math>
+<math> OPT(i,j) = 1+OPT(i-1,j-1)\,</math> ถ้า <math> x_i=y_j \,</math>
 เขียนเป็น pseudocode ได้ดังนี้
 <geshi lang="c">
-LCS(x,i,y,j)
+LCS(x,n,y,m)
-     if i=0 or j=0 then
+     for i=1 to n do
-         return 0
+        M[i,0] = 0
-     else
+    for j=1 to m do
-         if x[i] = y[j] then
+         M[0,j] = 0
-            M[i,j] = 1+M[i-1,j-1]
+     for i = 1 to n do
-        else
+         for j = 1 to m do
-            M[i,j] = max(M[i-1,j],M[i,j-1])
+            if x[i] = y[j] then
-     return M[i,j]
+                M[i,j] = 1+M[i-1,j-1]
+            else
+                M[i,j] = max(M[i-1,j],M[i,j-1])
+     return M[n,m]
 </geshi>
+เห็นได้ชัดว่าอัลกอริทึมข้างต้นใช้เวลาทำงานเป็น <math> O(n)+O(m)+O(nm)=O(nm) \,</math>