ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 16: | แถว 16: | ||
PALINDROMIC(s,n) | PALINDROMIC(s,n) | ||
for i = 1 to n do | for i = 1 to n do | ||
| − | for j = | + | M[i,i] = 1 |
| − | + | for i = 2 to n do | |
| − | + | for j = i-1 downto 1 | |
| − | + | M[i,j] = 0 | |
| − | M[i,j] = 1 | + | for i = n-1 downto 1 do |
| + | for j = i+1 to n-1 do | ||
| + | if s[i] != s[j] then | ||
| + | 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]) | |
| − | + | retrun M[1,n] | |
| − | |||
| − | |||
| − | |||
</geshi> | </geshi> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 08:22, 6 ตุลาคม 2552
เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร
ให้ คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง
พิจารณากรณีที่ จะได้ว่า
กรณีที่ จะได้ว่า
ส่วนกรณีที่เหลือจะได้ว่า ถ้า
หรือ ถ้า
![{\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
M[i,i] = 1
for i = 2 to n do
for j = i-1 downto 1
M[i,j] = 0
for i = n-1 downto 1 do
for j = i+1 to n-1 do
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])
retrun M[1,n]
</geshi>
