ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 4"

รุ่นแก้ไขปัจจุบันเมื่อ 09:30, 4 กันยายน 2552

ข้อย่อย 1

อินพุต: เซตของจำนวนเต็ม $A\,$ ซึ่งมีสมาชิกอยู่ $n\,$ ตัว และจำนวนเต็ม $x\,$

เอาพุต: มีคู่ของจำนวนเต็ม $a,b\in A\,$ ที่ $a<b,a+b=x\,$ อยู่กี่คู่

แนวคิด จากโจทย์ เราต้องการหาคู่ของจำนวนเต็ม $a,b\in A\,$ ที่ $a<b,a+b=x\,$ ซึ่งในห้องเรียนเราได้รู้วิธีการหา combination มาแล้ว ซึ่งข้อนี้ก็คือการหาซับเซตของ $A\,$ ที่มีขนาด 2 ที่ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x ว่ามีทั้งหมดกี่คู่นั่นเอง จากแนวคิดข้างต้น เราจะได้ว่าวัตถุที่เราสนใจคือ combination ของ $A\,$ ที่มีขนาด 2 และเงื่อนไขคือ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x นั่นเอง

จากแนวคิดข้างต้น เมื่อเขียนเป็น pseudocode จะได้ดังนี้

ตัวแปรทุกอย่างขออ้างอิงจากในห้องเรียน โดยที่ข้อนี้ให้ l = 2

<geshi lang="c"> COUNT(c,x) {

   count <-- 0
   if(c[0]+c[1]= x)
         count <-- count + 1
   return(count)

} </geshi>

<geshi lang="c"> GENERARTE(m,l) {

   if l = 0
        return(COUNT(c,x))
   else{
        for c[l-1]=l to m
            GENERATE(c[l-1]-1,l-1)
   }

} </geshi>

ข้อย่อย 2

อินพุต เอาพุตยังเหมือนข้อย่อย 1

แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ $a+b=x\,$ นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม $a\in A\,$ ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม $b\,$ ซึ่งเท่ากับ $x-a\,$ นั้นมีอยู่ในเซต $A\,$ หรือไม่ ได้ในเวลา $O(f(n))\,$ เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราทำงานได้ในเวลา $O(n.f(n))\,$ ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม $b\,$ มีอยู่ในเซต $A\,$ หรือไม่ และใช้เวลาทำงานเป็น $O(f(n))\,$

<geshi lang="c"> GENERATE(A,x,n) {

    count <-- 0
    for i=0 to n-1
    { 
        if (EXIST(x-A[i]))
             count <-- count + 1
    }
    return (count)

} </geshi>

ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 4"

รุ่นแก้ไขปัจจุบันเมื่อ 09:30, 4 กันยายน 2552

ข้อย่อย 1

ข้อย่อย 2

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 10: / แถว 10: @@
 ตัวแปรทุกอย่างขออ้างอิงจากในห้องเรียน โดยที่ข้อนี้ให้ l = 2
+<geshi lang="c">
 COUNT(c,x)
+{
+    count <-- 0
+    if(c[0]+c[1]= x)
+          count <-- count + 1
+    return(count)
+}
+</geshi>
-: count <-- 0
-:if(c[0]+c[1]= x)
+<geshi lang="c">
+GENERARTE(m,l)
-:: count <-- count + 1
+{
+    if l = 0
-:return(count)
+         return(COUNT(c,x))
+    else{
-GENERARTE(m,x)
+         for c[l-1]=l to m
+             GENERATE(c[l-1]-1,l-1)
-: if l = 0
+    }
+}
-:: return(COUNT(c,x))
+</geshi>
-: else
-:: for c[l-1]=0 to c[l-1] = 2
-::: GENERATE(c[l-1]-1,l-1)
 == ข้อย่อย 2 ==
 อินพุต เอาพุตยังเหมือนข้อย่อย 1
-แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ <math>a + b =x \,</math> นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม  <math>x \,</math> ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม <math>b \,</math> ซึ่งเท่ากับ <math>x-a \,</math> นั้นมีอยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา<math>O(f(n)) \,</math>
+แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ <math>a + b =x \,</math> นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม  <math>a \in A \,</math> ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม <math>b \,</math> ซึ่งเท่ากับ <math>x-a \,</math> นั้นมีอยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา<math>O(f(n)) \,</math>
-เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราก็จะทำงานได้ในเวลา <math>O(n.f(n)) \,</math> ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม <math> b \,</math> มีอยู่ในเซต <math> A \, </math> หรือไม่ และใช้เวลาทำงานเป็น  <math>O(f(n)) \,</math>
+เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราทำงานได้ในเวลา <math>O(n.f(n)) \,</math> ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม <math> b \,</math> มีอยู่ในเซต <math> A \, </math> หรือไม่ และใช้เวลาทำงานเป็น  <math>O(f(n)) \,</math>
+<geshi lang="c">
 GENERATE(A,x,n)
-:count <-- 0
+{
-: for i=0 to n-1
+     count <-- 0
-:: if (EXIST(x-A[i]))
+     for i=0 to n-1
-::: count <-- count + 1
+     {
-: return (count)
+         if (EXIST(x-A[i]))
+              count <-- count + 1
+     }
+     return (count)
+}
+</geshi>