ผลต่างระหว่างรุ่นของ "418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I"

รุ่นแก้ไขปัจจุบันเมื่อ 14:10, 22 ตุลาคม 2552

เนื้อหา

1 ข้อ 1
2 ข้อ 2
3 ข้อ 3
4 ข้อ 4
5 ข้อ 5
6 ข้อ 6
7 ข้อ 7
8 ข้อ 8

ข้อ 1

[Dasgupta, Papadimitriou, Vazirani 6.1] ลำดับย่อยที่ติดกันของลำดับ $S\,$ คือสมาชิกกลุ่มหนึ่งของลำดับ $S\,$ ที่อยู่ติดกัน ยกตัวอย่างเช่นถ้า $S\,$ คือลำดับ

5, 15, -30, 10, -5, 40, 10

แล้ว 15, -30, 10 เป็นลำดับย่อยที่ติดกันของ $S\,$ แต่ 5, 15, 40 ไำม่ใช่ จงหาอัลกอริทึมเพื่อแก้ปัญหาทางการคำนวณต่อไปนี้

ข้อมูลเข้า: ลำดับของจำนวน

a_{1},a_{2},\ldots ,a_{n}\,

ข้อมูลออก: ลำดับย่อยที่ติดกันทีมีผลบวกรวมของตัวเลขที่อยู่ในลำดับย่อยนั้นมากที่สุด (ลำดับที่มีความยาว 0 มีผลบวกรวมเท่ากับ 0)

สำหรับตัวอย่างข้างบน คำตอบคือ 10, -5, 40, 10 ซึ่งมีผลบวกรวมเท่ากับ 55

อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n)\,$

เฉลย

ข้อ 2

[Dasgupta, Papadimitriou, Vazirani 6.2] คุณกำลังจะเดินทางไกลบนถนนยาวเส้ันหนึ่ง คุณเริ่มต้นเดิน ณ หลักกิโลเมตรที่ 0 ริมถนนมีโรงแรมอยู่ $n\,$ โรงแรม ตั้งอยู่ที่ตำแหน่ง $a_{1},a_{2},\ldots ,a_{n}\,$ โดยที่ค่า $a_{i}\,$ แต่ละค่านั้นจะเริ่มวัดจากแหล่งกิโลเมตรที่ 0 คุณสามารถหยุดพักการเดินทางได้โรงแรม $n\,$ โรงแรมนี้เท่านั้น แต่คุณสามารถเลือกได้ว่าจะหยุดพักที่โรงแรมไหน และคุณจะสิ้นสุดการเดินทางที่โรงแรมสุดท้าย ซึ่งตั้งอยู่ที่ตำแหน่ง $a_{n}\,$

คุณต้องการที่จะเดินทางเป็นระยะทาง 200 กิโลเมตรต่อวัน แต่มันอาจจะเป็นไปไม่ได้ เนื่องจากโรงแรมอาจจะไม่อยู่ห่างกันเท่ากับ 200 กิโลเมตรพอดี ถ้าคุณเดินทางเป็นระยะทางเท่ากับ $x\,$ กิโลเมตรในวันหนึ่ง คุณจะได้รับ penalty เท่ากับ $(200-x)^{2}\,$ คุณต้องการที่จะวางแผนการเดินทางของคุณให้ได้รับ penalty รวมน้อยที่สุดเท่าที่จะทำได้

จงออกแบบอัลกอริทึมที่มีประสิทธิภาพสำหรับแก้ปัญหา

เฉลย

ข้อ 3

[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขาใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ $n\,$ คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ $m_{1},m_{2},\ldots ,m_{n}\,$ ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้

ที่ตำแหน่งทีเ่ป็นไปได้ตำแหน่งหนึ่งๆ ยัคโดนัลด์สามารถตั้งสาขาได้อยากมากเพียงสาขาเดียวเท่านั้น โดยหากตั้งสาขาที่ตำแหน่ง $m_{i}\,$ แล้วยัคโดนัลด์จะได้กำไรโดยเฉลี่ยต่อวันเท่ากับ $p_{i}\,$ โดยที่ $p_{i}>0\,$ สำหรับ $i=1,2,\ldots ,n\,$
สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย $k\,$ กิโลเมตร โดยที่ $k\,$ เป็นจำนวนเต็มบวก

จงออกแบบอัลกอริทึมเพื่อคำนวณหาำกำไรเฉลี่ยต่อวันสูงสุดที่ยัคโดนัลด์จะได้จากการตั้งสาขา ณ ตำแหน่งต่างๆ ตามเงื่อนไขข้างบน

เฉลย

ข้อ 4

[Dasgupta, Papadimitriou, Vazirani 6.4] คุณได้รับสตริงความยาว $n\,$ $s[1\ldots n]\,$ ซึ่งคุณคิดว่าเป็นข้อความที่ถูกตัดเครื่องหมายวรรคตอนทิ้งไปทั้งหมด (ยกตัวอย่างเช่น "iwasthebestoftime") คุณต้องการสร้างข้อความเดิมขึ้นมาโดยใช้ดิกชันนารีเป็นตัวช่วย โดยที่ดิกชันนารีนี้มีรูปแบบเป็นฟังก์ชัน $\mathrm {dict} (\cdot )\,$ ซึ่งสำหรับสตริง $w\,$ ใดๆ แล้ว $\mathrm {dict} (w)=1\,$ ถ้า $w\,$ เป็นคำในดิกชันนารีและ $\mathrm {dict} (w)=0\,$ ไมใช่คำในดิกชันนารี

จงใช้ dynamic programming ออกแบบอัลกอริทึตรวจสอบว่าสตริง $s[\cdot ]\,$ เกิดจากการนำคำในดิกชันนารีมาเรียงกันหรือไม่ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n^{2})\,$ หากการเรียก $\mathrm {dict} (\cdot )\,$ ใช้เวลา $O(1)\,$
หากสตริงที่ให้มาเกิดจากการเอาคำในดิกชันนารีมาเรียงกันจริงๆ จงออกแบบอัลกอริทึมเพื่อหาลำดับของคำดังกล่าวด้วย

เฉลย

ข้อ 5

[Dasgupta, Papadimitriou, Vazirani 6.6] พิจารณาตารางสูตรคูณของสัญลักษณ์ $a,b,c\,$ ดังต่อไปนี้

	$a\,$	$b\,$	$c\,$
$a\,$	$b\,$	$b\,$	$c\,$
$b\,$	$c\,$	$b\,$	$a\,$
$c\,$	$a\,$	$c\,$	$c\,$

ภายใต้กฏการคูณข้างบนนี้ เราจะได้ว่า $ab=b\,$ และ $ba=c\,$ เป็นต้น

จงออกแบบอัลกอริ่ทึมที่ตรวจสอบว่าสตริงของตัวอักษรทั้งสามตัวข้างบนนี้ ยกตัวอย่างเช่น $bbbbac\,$ สามารถถูกจัดวงเล็บให้เมื่อทำการคูณออกมาแล้วได้ผลลัพธ์เป็น $a\,$ ยกตัวเช่น ถ้าอัลกอริทึมของคุณได้รับข้อมูลเข้าเป็น $bbbbac\,$ อัลกอริทึมของคุณควรจะตอบว่า "ใช่" เนื่องจาก $((b(bb))(ba))c=a\,$

เฉลย

ข้อ 6

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

A, C, G, T, G, T, C, A, A, A, A, T, C, G

มีำลำดับย่อยที่เป็นพาลินโดรมอยู่หลายลำดับ เช่น A, C, G, C, A และ A, A, A, A (ในทางกลับกัน A, C, T ไม่ใช่พาลินโีดรม)

จงออกแบบอัลกอริทึมที่ เมื่อให้ลำดับมา หาความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุด อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n^{2})\,$

เฉลย

ข้อ 7

กำหนดสตริง $x=x_{1}x_{2}\dotsb x_{n}\,$ และ $y=y_{1}y_{2}\dotsb y_{m}\,$ เราต้องการหาความยาวของลำดับร่วมที่มีความยาวมากที่สุด (longest common subsequence) กล่าวคือ จำนวนเต็ม $k\,$ ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี $i_{1}<i_{2}<\dotsb <i_{k}\,$ และ $j_{1}<j_{2}<\dotsb <j_{k}\,$ ที่ทำให้ $x_{i_{1}}=y_{j_{1}},x_{i_{2}}=y_{j_{2}},x_{i_{3}}=y_{j_{3}},\ldots ,x_{i_{k}}=y_{j_{k}}\,$ จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(mn)\,$

เฉลย

ข้อ 8

สมมติว่าคุณเหรียญที่มีค่า $x_{1},x_{2},x_{3},\ldots ,x_{n}\,$ บาท อยู่ชนิืดละเป็นจำนวนมากมายนับไม่ถ้วน คุณต้องการทอนเงินจำนวน $v\,$ บาท กล่าวคือ คุณต้องการหาเซตของเหรียญกลุ่มหนึี่งที่มีผลรวมเท่ากับ $v\,$ พอดี การทอนเงินนี้อาจเป็นไปไม่ได้ ยกตัวอย่างเช่น ถ้าคุณมีแค่เหรียญ 5 บาทกับ 10 บาท คุณสามารถทอนเงิน 15 บาทได้ แต่ไม่สามารถทอนเงิน 12 บาทได้ เป็นต้น จงออกแบบอัลกอริทึมที่ใช้เวลาการทำงาน $O(nv)\,$ ที่ใช้แก้ปัญหาทางการคำนวณต่อไปนี้

ข้อมูลนำเข้า: $x_{1},x_{2},\ldots ,x_{n},v\,$
ข้อมูลส่งออก: "ใช่" ถ้าคุณสามารถทอนเงิน $v\,$ บาทได้โดยใชเหรียญ $x_{1},\ldots ,x_{n}\,$ โดยใช้เหรียญชนิดละกี่เหรียญก็ได้ มิเช่นนี้ให้ตอบ "ไม่ใช่"

เฉลย

@@ แถว 6: / แถว 6: @@
 : '''ข้อมูลออก:''' ลำดับย่อยที่ติดกันทีมีผลบวกรวมของตัวเลขที่อยู่ในลำดับย่อยนั้นมากที่สุด (ลำดับที่มีความยาว 0 มีผลบวกรวมเท่ากับ 0)
 สำหรับตัวอย่างข้างบน คำตอบคือ 10, -5, 40, 10 ซึ่งมีผลบวกรวมเท่ากับ 55
+อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 1|เฉลย]]
+== ข้อ 2 ==
+[Dasgupta, Papadimitriou, Vazirani 6.2] คุณกำลังจะเดินทางไกลบนถนนยาวเส้ันหนึ่ง คุณเริ่มต้นเดิน ณ หลักกิโลเมตรที่ 0 ริมถนนมีโรงแรมอยู่ <math>n \,</math> โรงแรม ตั้งอยู่ที่ตำแหน่ง <math>a_1, a_2, \ldots, a_n \,</math> โดยที่ค่า <math>a_i \,</math> แต่ละค่านั้นจะเริ่มวัดจากแหล่งกิโลเมตรที่ 0 คุณสามารถหยุดพักการเดินทางได้โรงแรม <math>n \,</math>
+โรงแรมนี้เท่านั้น แต่คุณสามารถเลือกได้ว่าจะหยุดพักที่โรงแรมไหน และคุณจะสิ้นสุดการเดินทางที่โรงแรมสุดท้าย ซึ่งตั้งอยู่ที่ตำแหน่ง <math>a_n \,</math>
+คุณต้องการที่จะเดินทางเป็นระยะทาง 200 กิโลเมตรต่อวัน แต่มันอาจจะเป็นไปไม่ได้ เนื่องจากโรงแรมอาจจะไม่อยู่ห่างกันเท่ากับ 200 กิโลเมตรพอดี ถ้าคุณเดินทางเป็นระยะทางเท่ากับ <math>x \,</math> กิโลเมตรในวันหนึ่ง คุณจะได้รับ penalty เท่ากับ <math>(200 - x)^2 \,</math> คุณต้องการที่จะวางแผนการเดินทางของคุณให้ได้รับ penalty รวมน้อยที่สุดเท่าที่จะทำได้
+จงออกแบบอัลกอริทึมที่มีประสิทธิภาพสำหรับแก้ปัญหา
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 2|เฉลย]]
+== ข้อ 3 ==
+[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขาใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ <math>n \,</math> คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ <math>m_1, m_2, \ldots, m_n \,</math> ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้
+* ที่ตำแหน่งทีเ่ป็นไปได้ตำแหน่งหนึ่งๆ ยัคโดนัลด์สามารถตั้งสาขาได้อยากมากเพียงสาขาเดียวเท่านั้น โดยหากตั้งสาขาที่ตำแหน่ง <math>m_i \,</math> แล้วยัคโดนัลด์จะได้กำไรโดยเฉลี่ยต่อวันเท่ากับ  <math>p_i \,</math> โดยที่ <math>p_i > 0 \,</math> สำหรับ <math>i = 1, 2, \ldots, n \,</math>
+* สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย <math>k \,</math> กิโลเมตร โดยที่ <math>k \,</math> เป็นจำนวนเต็มบวก
+จงออกแบบอัลกอริทึมเพื่อคำนวณหาำกำไรเฉลี่ยต่อวันสูงสุดที่ยัคโดนัลด์จะได้จากการตั้งสาขา ณ ตำแหน่งต่างๆ ตามเงื่อนไขข้างบน
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 3|เฉลย]]
+== ข้อ 4 ==
+[Dasgupta, Papadimitriou, Vazirani 6.4] คุณได้รับสตริงความยาว <math>n \,</math> <math>s[1 \ldots n] \,</math> ซึ่งคุณคิดว่าเป็นข้อความที่ถูกตัดเครื่องหมายวรรคตอนทิ้งไปทั้งหมด (ยกตัวอย่างเช่น "iwasthebestoftime") คุณต้องการสร้างข้อความเดิมขึ้นมาโดยใช้ดิกชันนารีเป็นตัวช่วย โดยที่ดิกชันนารีนี้มีรูปแบบเป็นฟังก์ชัน <math>\mathrm{dict}(\cdot) \,</math> ซึ่งสำหรับสตริง <math>w \,</math> ใดๆ แล้ว <math>\mathrm{dict}(w) = 1 \,</math> ถ้า <math>w \,</math> เป็นคำในดิกชันนารีและ <math>\mathrm{dict}(w) = 0 \,</math> ไมใช่คำในดิกชันนารี
+# จงใช้ dynamic programming ออกแบบอัลกอริทึตรวจสอบว่าสตริง <math>s[\cdot] \,</math> เกิดจากการนำคำในดิกชันนารีมาเรียงกันหรือไม่ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n^2) \,</math> หากการเรียก <math>\mathrm{dict}(\cdot) \,</math> ใช้เวลา <math>O(1) \,</math>
+# หากสตริงที่ให้มาเกิดจากการเอาคำในดิกชันนารีมาเรียงกันจริงๆ จงออกแบบอัลกอริทึมเพื่อหาลำดับของคำดังกล่าวด้วย
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 4|เฉลย]]
+== ข้อ 5==
+[Dasgupta, Papadimitriou, Vazirani 6.6] พิจารณาตารางสูตรคูณของสัญลักษณ์ <math>a, b, c \,</math> ดังต่อไปนี้
+<table border="1" cellpadding="5" cellspacing="0">
+    <tr>
+        <td bgcolor="#cccccc"></td>
+        <td bgcolor="#cccccc"><math>a \,</math></td>
+        <td bgcolor="#cccccc"><math>b \,</math></td>
+        <td bgcolor="#cccccc"><math>c \,</math></td>
+    </tr>
+    <tr>
+        <td bgcolor="#cccccc"><math>a \,</math></td>
+        <td><math>b \,</math></td>
+        <td><math>b \,</math></td>
+        <td><math>c \,</math></td>
+    </tr>
+    <tr>
+        <td bgcolor="#cccccc"><math>b \,</math></td>
+        <td><math>c \,</math></td>
+        <td><math>b \,</math></td>
+        <td><math>a \,</math></td>
+    </tr>
+    <tr>
+        <td bgcolor="#cccccc"><math>c \,</math></td>
+        <td><math>a \,</math></td>
+        <td><math>c \,</math></td>
+        <td><math>c \,</math></td>
+    </tr>
+</table>
+ภายใต้กฏการคูณข้างบนนี้ เราจะได้ว่า <math>ab = b \,</math> และ <math>ba = c \,</math> เป็นต้น
+จงออกแบบอัลกอริ่ทึมที่ตรวจสอบว่าสตริงของตัวอักษรทั้งสามตัวข้างบนนี้ ยกตัวอย่างเช่น <math>bbbbac \,</math> สามารถถูกจัดวงเล็บให้เมื่อทำการคูณออกมาแล้วได้ผลลัพธ์เป็น <math>a \,</math> ยกตัวเช่น ถ้าอัลกอริทึมของคุณได้รับข้อมูลเข้าเป็น <math>bbbbac \,</math> อัลกอริทึมของคุณควรจะตอบว่า "ใช่" เนื่องจาก <math>((b(bb))(ba))c = a \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 5|เฉลย]]
+== ข้อ 6 ==
+ลำดับย่อยของลำดับหนึ่งจะถูกเรียกว่าเป็น'''พาลินโดรม''' ถ้าหากเมื่อเราอ่านมันจากทางซ้ายไปทางขวาแล้วเหมือนกันกับอ่านจากทางขวากไปซ้าย ยกตัวอย่างเช่น ในลำดับ
+: A, C, G, T, G, T, C, A, A, A, A, T, C, G
+มีำลำดับย่อยที่เป็นพาลินโดรมอยู่หลายลำดับ เช่น A, C, G, C, A และ  A, A, A, A (ในทางกลับกัน A, C, T ไม่ใช่พาลินโีดรม)
+จงออกแบบอัลกอริทึมที่ เมื่อให้ลำดับมา หาความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุด อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n^2) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6|เฉลย]]
+== ข้อ 7 ==
+กำหนดสตริง <math>x = x_1x_2 \dotsb x_n \,</math> และ <math>y =y_1 y_2 \dotsb y_m \,</math> เราต้องการหาความยาวของลำดับร่วมที่มีความยาวมากที่สุด (longest common subsequence) กล่าวคือ จำนวนเต็ม <math>k  \,</math> ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี <math>i_1 < i_2 < \dotsb < i_k \,</math> และ <math>j_1 < j_2 < \dotsb < j_k \,</math> ที่ทำให้ <math>x_{i_1} = y_{j_1}, x_{i_2} = y_{j_2}, x_{i_3} = y_{j_3}, \ldots, x_{i_k} = y_{j_k} \,</math> จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(mn) \,</math>
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 7|เฉลย]]
+== ข้อ 8 ==
+สมมติว่าคุณเหรียญที่มีค่า <math>x_1, x_2, x_3, \ldots, x_n \,</math> บาท อยู่ชนิืดละเป็นจำนวนมากมายนับไม่ถ้วน คุณต้องการทอนเงินจำนวน <math>v \,</math> บาท กล่าวคือ คุณต้องการหาเซตของเหรียญกลุ่มหนึี่งที่มีผลรวมเท่ากับ <math>v \,</math> พอดี การทอนเงินนี้อาจเป็นไปไม่ได้ ยกตัวอย่างเช่น ถ้าคุณมีแค่เหรียญ 5 บาทกับ 10 บาท คุณสามารถทอนเงิน 15 บาทได้ แต่ไม่สามารถทอนเงิน 12 บาทได้ เป็นต้น จงออกแบบอัลกอริทึมที่ใช้เวลาการทำงาน <math>O(nv) \,</math> ที่ใช้แก้ปัญหาทางการคำนวณต่อไปนี้
+# ข้อมูลนำเข้า: <math>x_1, x_2, \ldots, x_n, v \,</math>
+# ข้อมูลส่งออก: "ใช่" ถ้าคุณสามารถทอนเงิน <math>v \,</math> บาทได้โดยใชเหรียญ <math>x_1, \ldots, x_n \,</math> โดยใช้เหรียญชนิดละกี่เหรียญก็ได้ มิเช่นนี้ให้ตอบ "ไม่ใช่"
+[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 8|เฉลย]]

ผลต่างระหว่างรุ่นของ "418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I"

รุ่นแก้ไขปัจจุบันเมื่อ 14:10, 22 ตุลาคม 2552

เนื้อหา

ข้อ 1

ข้อ 2

ข้อ 3

ข้อ 4

ข้อ 5

ข้อ 6

ข้อ 7

ข้อ 8

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ