ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 8"
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน <math>n \,</math> ตัว เอาพ…') |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 5: | แถว 5: | ||
แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า <math>g[i]=1 \,</math> หมายความว่า <math>x_i \,</math> เป็นสมาชิกของซับเซต แต่ถ้า<math>g[i]=2 \,</math> หมายความว่า <math>x_i \,</math> ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า <math>x_i \,</math> เป็นสมาชิกของซับเซตให้ ตัวแปร <math>x_i \,</math> มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์) | แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า <math>g[i]=1 \,</math> หมายความว่า <math>x_i \,</math> เป็นสมาชิกของซับเซต แต่ถ้า<math>g[i]=2 \,</math> หมายความว่า <math>x_i \,</math> ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า <math>x_i \,</math> เป็นสมาชิกของซับเซตให้ ตัวแปร <math>x_i \,</math> มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์) | ||
| + | เมื่อนำแนวคิดข้างต้นมาเขียนเป็น pseudocode จะได้ดังนี้ | ||
| + | |||
| + | GENERATE(X,k) | ||
| + | :if k=0 | ||
| + | :: return(VERIFY(g)) // ทำการเรียก VERIFY โดยส่งอะเรย์ g ไปให้ซึ่งค่าแต่ละช่องของ g เก็บ 1 หรือ 2 ซึ่งใน VERIFY จะทำการตรวจสอบเองว่าถ้าเท่ากับ 1 คือจริง 2 คือเท็จ | ||
| + | :else | ||
| + | :: for g[k-1] = 1 to g[k-1] <= 2 | ||
| + | ::: GENERATE(k-1) | ||
เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ<math> 2^n \,</math> และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(2^n.M)\,</math> | เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ<math> 2^n \,</math> และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(2^n.M)\,</math> | ||
รุ่นแก้ไขเมื่อ 09:02, 19 สิงหาคม 2552
อินพตุ:ประพจน์ที่มีตัวแปรไม่เกิน ตัว
เอาพุต:มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่
แนวคิด ตัวแปรแต่ละตัวมีค่าได้สองค่า คือไม่จริงก็เท็จ การที่จะตรวจสอบว่า มีวิธีการกำหนดค่าตัวแปรให้ประพจน์เป็นจริงหรือไม่ต้องทำการลองกำหนดทุก ๆ แบบของตัวแปรที่เป็นไปได้ แต่ในห้องเรียน เราได้มีวิธีการสร้างซับเซตมาแล้ว และถ้าเราตีความใหม่ คือ ถ้า หมายความว่า เป็นสมาชิกของซับเซต แต่ถ้า หมายความว่า ไม่เป็นสมาชิกของซับเซต ดังนั้นเมื่อสร้างซับเซตได้แล้ว เราก็ทำการกำหนดว่า ถ้า เป็นสมาชิกของซับเซตให้ ตัวแปร มีค่าความจริงเป็นจริง ไม่เช่นนั้นให้มีค่าความจริงเป็นเท็จ หลังจากนั้นก็เอาวิธีการกำหนดค่าตัวแปรต่าง ๆ เหล่านี้ เรียกถาม subroutine (สมมติว่าชื่อ VERIFY เพื่อคำนวณหาค่าความจริงของประพจน์)
![{\displaystyle g[i]=1\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8da7eb7ef8fc94fcc1c9fcec18d7c7d2b346860c)
![{\displaystyle g[i]=2\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71a135ae953262740ca2606d9be5ae3f08e0c58c)
เมื่อนำแนวคิดข้างต้นมาเขียนเป็น pseudocode จะได้ดังนี้
GENERATE(X,k)
- if k=0
- return(VERIFY(g)) // ทำการเรียก VERIFY โดยส่งอะเรย์ g ไปให้ซึ่งค่าแต่ละช่องของ g เก็บ 1 หรือ 2 ซึ่งใน VERIFY จะทำการตรวจสอบเองว่าถ้าเท่ากับ 1 คือจริง 2 คือเท็จ
- else
- for g[k-1] = 1 to g[k-1] <= 2
- GENERATE(k-1)
- for g[k-1] = 1 to g[k-1] <= 2
เวลาการทำงานของอัลกอริทึมข้างต้นก็จะเท่ากับเวลาการสร้างซับเซตทั้งหมด ซึ่งคือ และแต่ละซับเซตต้องเรียก VERIFY ซึ่งโจทย์กำหนดให้มีเวลาการทำงานเป็น M ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมคือ
