ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 25: | แถว 25: | ||
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],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] | return M[1,n] | ||
</geshi> | </geshi> | ||
รุ่นแก้ไขเมื่อ 09:52, 4 ตุลาคม 2552
เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร
ให้ คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง
![{\displaystyle s[i,i+1,...,j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbacb8f49dd4659fd60caca3d7e58bda176e319b)
พิจารณากรณีที่ จะได้ว่า
กรณีที่ จะได้ว่า
ส่วนกรณีที่เหลือจะได้ว่า ถ้า
![{\displaystyle s[i]!=s[j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/804a13f704a64b7d120ed973f2a180322a766d4e)
หรือ ถ้า
![{\displaystyle s[i]=s[j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c50adf0ac4f834f911db164bfeecc496cc2ae249)
เขียนเป็น pseudocode ได้ดังนี้
<geshi lang="c"> PALINDROMIC(s,n)
i =1
j = n
if i < j then
M[i,j] = 0
else if i = j then
M[i,j] = 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],2+M[i+1,j-1])
return M[1,n]
</geshi>
