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

202.29.77.40 เมื่อ 07:40, 22 ตุลาคม 2552

2009-10-22T07:40:56Z

158.108.183.136 เมื่อ 10:17, 5 ตุลาคม 2552

2009-10-05T10:17:30Z

Aoy เมื่อ 08:10, 3 ตุลาคม 2552

2009-10-03T08:10:59Z

Aoy เมื่อ 08:09, 3 ตุลาคม 2552

2009-10-03T08:09:40Z

Aoy เมื่อ 08:03, 3 ตุลาคม 2552

2009-10-03T08:03:32Z

Aoy เมื่อ 08:01, 3 ตุลาคม 2552

2009-10-03T08:01:47Z

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i,j) \,$ เป็นความยาวที่มากที่สุดของ common substring ขอ…'

2009-10-03T07:55:26Z

หน้าที่ถูกสร้างด้วย 'ให้ <math> OPT(i,j) \,</math> เป็นความยาวที่มากที่สุดของ common substring ขอ…'

หน้าใหม่

ให้ <math> OPT(i,j) \,</math> เป็นความยาวที่มากที่สุดของ common substring ของ <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> 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),1+OPT(i-1,j-1))\,</math> ถ้า <math> x_i=y_j \,</math>

@@ แถว 5: / แถว 5: @@
 <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 ได้ดังนี้

@@ แถว 23: / แถว 23: @@
              else
                  M[i,j] = max(M[i-1,j],M[i,j-1])
-     return M[i,j]
+     return M[n,m]
 </geshi>

@@ แถว 12: / แถว 12: @@
 <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]
 </geshi>

@@ แถว 5: / แถว 5: @@
 <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),1+OPT(i-1,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>
 เขียนเป็น pseudocode ได้ดังนี้
@@ แถว 15: / แถว 17: @@
      else
          if x[i] = y[j] then
-             M[i,j] = max(M[i-1,j],M[i,j-1],1+M[i-1,j-1])
+             M[i,j] = 1+M[i-1,j-1]
      return M[i,j]
 </geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:01, 3 ตุลาคม 2552
แถว 6:		แถว 6:

	<math> OPT(i,j)= max(OPT(i-1,j),OPT(i,j-1),1+OPT(i-1,j-1))\,</math> ถ้า <math> x_i=y_j \,</math>		<math> OPT(i,j)= max(OPT(i-1,j),OPT(i,j-1),1+OPT(i-1,j-1))\,</math> ถ้า <math> x_i=y_j \,</math>
		+
		+	เขียนเป็น pseudocode ได้ดังนี้
		+
		+	<geshi lang="c">
		+	LCS(x,i,y,j)
		+	if i=0 or j=0 then
		+	return 0
		+	else
		+	if x[i] = y[j] then
		+	M[i,j] = max(M[i-1,j],M[i,j-1],1+M[i-1,j-1])
		+	return M[i,j]
		+	</geshi>

@@ แถว 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>