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

Aoy เมื่อ 08:22, 6 ตุลาคม 2552

2009-10-06T08:22:50Z

Aoy เมื่อ 08:21, 6 ตุลาคม 2552

2009-10-06T08:21:58Z

Aoy เมื่อ 07:44, 6 ตุลาคม 2552

2009-10-06T07:44:19Z

Aoy เมื่อ 09:54, 4 ตุลาคม 2552

2009-10-04T09:54:35Z

Aoy เมื่อ 09:52, 4 ตุลาคม 2552

2009-10-04T09:52:25Z

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

2009-10-03T08:31:44Z

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

2009-10-03T08:30:31Z

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

2009-10-03T08:20:43Z

Aoy: หน้าที่ถูกสร้างด้วย 'เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาห…'

2009-10-03T08:14:54Z

หน้าที่ถูกสร้างด้วย 'เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาห…'

หน้าใหม่

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

@@ แถว 26: / แถว 26: @@
              else
                  M[i,j] = max(M[i+1,j],M[i,j-1],2+M[i+1,j-1])
 </geshi>

@@ แถว 15: / แถว 15: @@
 <geshi lang="c">
 PALINDROMIC(s,n)
 </geshi>

@@ แถว 15: / แถว 15: @@
 <geshi lang="c">
 PALINDROMIC(s,n)
 </geshi>

@@ แถว 15: / แถว 15: @@
 <geshi lang="c">
 PALINDROMIC(s,n)
-     i =1
+     for i = 1 to n do
-    j = n
+        for j = n downto 1 do
-    if i < j then
+            if i < j then
-        M[i,j] = 0
+                M[i,j] = 0
-    else if i = j then
+            else if i = j then
-        M[i,j] = 1
+                M[i,j] = 1
-    else
+            else
-        if s[i] != s[j] then
+                if s[i] != s[j] then
-            M[i,j] = max(M[i+1,j],M[i,j-1])
+                    M[i,j] = max(M[i+1,j],M[i,j-1])
-        else
+                else
-            M[i,j] = max(M[i+1,j],M[i,j-1],2+M[i+1,j-1])
+                    M[i,j] = max(M[i+1,j],M[i,j-1],2+M[i+1,j-1])
      return M[1,n]
 </geshi>

@@ แถว 25: / แถว 25: @@
              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])
+             M[i,j] = max(M[i+1,j],M[i,j-1],2+M[i+1,j-1])
      return M[1,n]
 </geshi>

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

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:20, 3 ตุลาคม 2552
แถว 1:		แถว 1:
	เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร		เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร
		+
		+	ให้ <math> OPT(i,j) \,</math> คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง <math> s[i,i+1,...,j] \,</math>