ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 15: | แถว 15: | ||
<geshi lang="c"> | <geshi lang="c"> | ||
PALINDROMIC(s,n) | PALINDROMIC(s,n) | ||
| − | i =1 | + | for i = 1 to n do |
| − | + | for j = n downto 1 do | |
| − | + | 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] | return M[1,n] | ||
</geshi> | </geshi> | ||
รุ่นแก้ไขเมื่อ 09:54, 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)
for i = 1 to n do
for j = n downto 1 do
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>
