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

2009-10-03T09:05:22Z

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i) \,$ มีค่าเป็น $yes \,$ ถ้าตัวอักษรที่ $1 ...…'$

2009-10-03T09:01:48Z

หน้าที่ถูกสร้างด้วย 'ให้ <math> OPT(i) \,</math> มีค่าเป็น <math> yes \,</math> ถ้าตัวอักษรที่ <math> 1 ...…'

หน้าใหม่

ให้ <math> OPT(i) \,</math> มีค่าเป็น <math> yes \,</math> ถ้าตัวอักษรที่ <math> 1 ... i \,</math> สามารถตัดคำได้ หรือมีค่าเป็น <math> no \,</math> ถ้าตัวอักษรที่ <math> 1 ... i \,</math> ไม่สามารถตัดคำได้

การที่ตัวอักษรตัวที่ <math> 1 ...i \,</math> สามารถตัดคำได้นั้น หมายความว่า สตริงที่ประกอบด้วยตัวอักษรตัวที่ <math> 1 ... i \,</math> นั้นต้องมีคำสุดท้ายที่ถาม <math> dict \,</math> แล้ว valid และต้องมีส่วนข้างหน้าของคำสุดท้ายนี้ที่สามารถตัดได้เหมือนกัน

ดังนั้น พิจารณากรณีที่ <math> i=0 \,</math> จะได้ว่า <math> OPT(0) = yes \,</math>

ส่วนกรณีที่ <math> i \neq 0 \,</math> นั้น ถ้ามันจะตัดได้มันต้องเป็นกรณีที่อธิบายไปข้างต้น ดังนั้นสิ่งที่ต้องคิดต่อคือ ถ้าเรารู้แล้วว่ามันตัดได้ แล้วตำแหน่งเริ่มต้นของคำสุดท้าย ที่ทำให้คำนี้ valid และส่วนที่เหลือข้างหน้าตัดได้อีก ควรจะอยู่ตรงไหน สมมติให้เราสามารถตัดคำได้โดยแบ่งตำแหน่งของคำสุดท้ายกับกลุ่มคำที่อยู่ข้างหน้าที่ตำแหน่ง <math> k \,</math> เราจะทำการลองทุก ๆ ค่า <math> k \,</math> ที่เป็นไปได้ ดังนั้นเราจะได้ว่า <math> OPT(i) = \bigvee_{k=1}^{i-1}(OPT(k) \wedge dict(s[k+1,...,i])) \,</math> ถ้า <math> i > 0 \,</math>

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c">
WORD(s,n)
M[0] = 1
for i = 1 to n do
for k =1 to i-1 do
if M[k] and dict(s[k+1,...,i])
M[i] = 1
break // ถ้ามีหนึ่งวิธีที่ตัดได้ก็หยุดเลย
</geshi>

@@ แถว 17: / แถว 17: @@
                  M[i] = 1
                  break // ถ้ามีหนึ่งวิธีที่ตัดได้ก็หยุดเลย
 </geshi>

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

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

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ OPT(i) \, มีค่าเป็น yes \, ถ้าตัวอักษรที่ 1 ...…'

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i) \,$ มีค่าเป็น $yes \,$ ถ้าตัวอักษรที่ $1 ...…'$