เนื้อหา

1 อัลกอริทึม
2 ความถูกต้อง
- 2.1 ข้อความที่ 1
- 2.2 ข้อความที่ 2
3 ประสิทธิภาพ

อัลกอริทึม

เราออกแบบอัลกอริทึมที่ใช้แก้ปัญหาโจทย์ข้อนี้ด้วยเทคนิค divide and conquer ในขั้นแรก เราจะสมมติว่าเรามีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้อยู่แล้ว และเราจะเรียกชื่อมันว่า โดยมันจะรับบัตร ATM เป็นอินพุต และจะส่งข้อมูลออกตามเงื่อนไขดังต่อไปนี้

ถ้าหากในกลุ่มของบัตร ATM ที่ให้ไม่มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})=\mathrm {NONE} \,$ โดยที่ เป็นค่าพิเศษค่าหนึ่งที่ไม่ตรงกับบัตร ATM ใดๆ เลย
ถ้าหากในกลุ่มของบัตร ATM ที่ให้มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า แล้ว เมื่อ เป็นบัตร ATM บัตรหนึ่งในกลุ่มของบัตรนั้น

เมื่อได้สมมติเช่นนั้นแล้ว รายละเอียดของ จะเป็นดังต่อไปนี้

DIVIDE: แบ่งบัตร ATM ที่ได้รับมาออกเป็นสองกลุ่ม ได้แก่ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 926140603 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Sun, 15 Feb 2026 21:28:19 GMT Sensitive client information IP address: 158.108.32.49$ และ เมื่อ
พึงระลึกว่า เราจะไม่สามารถแบ่งปัญหาออกเป็นปัญหาย่อยเช่นนี้ได้ถ้า ในกรณีนี้เราจะืคืนค่า กลับไป กล่าวคืือ

CONQUER: เรียก และสมมติให้ผลลัพธ์ของมันเป็น หลังจากนั้นเรียก และสมมติให้ผลลัพธ์เป็น $x_{2}\,$

COMBINE: ตรวจสอบว่าระหว่าง $x_{1}\,$ กับ ตัวใดกันแน่ที่เป็นมีกลุ่มบัตร ATM ที่สมมูลกับมันมากกว่า ใบ ซึ่งการตรวจสอบสามารถทำได้โดยการนำเอา ไปตรวจเช็คความสมมูลกับบัตร ATM อื่นๆ ทุกบัตร แล้วนับว่ามีบัตรที่สมมูลกับมันกี่บัตร แล้วจึงทำเช่นเดียวกันกับ หลังจากนั้นเราจึงคืนบัตรที่มีจำนวนบัตรที่สมมูลกับมันมากกว่า กลับไป (จะมีบัตรนี้ได้เพียงบัตรเดียวเท่านั้น)

อัลกอริืทึมที่อธิบายมาข้างบนสามารถเขียนเป็น pseudocode ได้ดังต่อไปนี้ <geshi lang="c"> Majority(c[1], c[2], ..., c[n]) {

   if n = 1 then
       return c[1]
   else
   {
       h = n/2
       x1 = Majority(c[1], c[2], ..., c[h])
       x2 = Majority(c[h+1], c[h+2], ..., c[n])
       
       x1count = 0
       if x1 != NONE then
       {            
           for i = 1 to n do
                if TEST_EQUIVALENCE(x1, c[i]) = true then
                    x1count = x1count + 1
       }

       x2count = 0
       if x2 != NONE then
       {
           for i = 1 to n do
                if TEST_EQUIVALANCE(x2, c[i]) = true then
                    x2count = x2count + 1
       }

       if x1count > n/2 then
           return x1
       else if x2count > n/2 then
           return x2
       else
           return NONE
   }

} </geshi> ใน pseudocode ข้างบนนี้ TEST_EQUIVALANCE คือการเช็คว่าบัตร ATM สองบัตรสมมูลกันหรือไม่

ความถูกต้อง

การพิูสูจน์ว่าอัลกอริทึมข้างบนทำงานได้ถูกต้อง เราจะต้องพิสูจน์ข้อความสองข้อความต่อไปนี้

ถ้าใน มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า แล้ว จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา
ถ้าใน ไม่มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนั้นมีขนาดมากกว่า แล้ว จะคืนค่า NONE

ข้อความที่ 1

ให้ เป็นประพจน์เปิด " มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า แล้ว จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา"

เราจะพิสูจน์ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

P(n)\,

ด้วย induction บน แต่ก่อนที่เราจะพิสูจน์เราจะพิสูจน์ lemma ต่อไปนี้

lemma: ให้บัตร เป็นบัตร ATM บัตรหนึ่งใน ที่มีบัตรสมมูลกับมันมากกว่า ใบ และให้ แล้วอย่างน้อยข้อความใดข้อความหนึ่งต่อไปนี้จะเป็นจริิง

มีบัตรสมมูลกับ ใน มากกว่า ใบ
มีบัตรสมมูลกับ ใน มากกว่า ใบ

พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่าข้อความทั้งสองเป็นเท็จ ดังนั้นเราจะได้ว่ามีบัตรที่สมมูลกับ ไม่เกิืน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

h/2+(n-h)/2=n/2\,

ใบ เกิดข้อขัดแย้งกับความจริงที่ว่ามีบัตรสมมูลกับ มากกว่า ฉะนั้นจะต้องมีอย่างน้อยข้อความหนึ่งที่เป็นจริง

พิสูจน์ $P(n)\,$ : (Base Case) ในกรณีนี้ ซึ่งเราทราบว่า และ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

c_{1}\,

เป็นบัตรที่มีบัตรสมมูลกับมัน 1 ใบ (ตัวมันเอง) ซึ่งจำนวนบัตรนี้มากกว่า

(Induction Case) สมมติให้ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

P(1),P(2),\ldots ,P(n-1)\,

เป็นจริงสำหรับจำนวนเต็ม บางตัว พิจารณาเซตของบัตร ATM และสมมติให้ เป็นบัตร ATM ที่มีบัตรสมมูลกับมัน (รวมตัวมันเองด้วย) มากกว่า ใบ จาก lemma เราจะได้ว่า

มีบัตรสมมูลกับ ใน มากกว่า ใบ หรือไม่ก็
มีบัตรสมมูลกับ ใน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 947987071 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Sun, 15 Feb 2026 21:28:55 GMT Sensitive client information IP address: 158.108.32.49$ มากกว่า ใบ

ฉะนั้นจะมีบัตรอย่างน้อยหนึ่งใบใน และ ที่สมมูลกับ

ดังนั้นเมื่อเรานำ และ ไปตรวจว่ามีบัตร ATM ที่สมมูลกับมันกี่ตัว จะมีบัตรหนึ่งทีมีบัตรสมมูลกับมันมากกว่า ใบ และ จะคืนบ้ัตรนั้นออกมา ฉะนั้นเราสรุปได้ว่า เป็นจริง

ดังนั้นเราสามารถสรุปว่า เป็นจริงสำหรับจำนวนเต็มบวก $n\,$ ทุกตัวด้วย (strong) induction

ข้อความที่ 2

พิสูจน์: พิจารณาการทำงานของ เราจะได้ว่าไม่ว่า และ จะมีค่าเป็นอะไรก็ตาม จะมีบัตร ATM ที่สมมูลกับมันไม่เกิน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

n/2\,

เสมอ ฉะนั้น จะตอบค่า NONE เท่านั้น

ประสิทธิภาพ

ให้ เป็นเวลาการทำงานของ แล้วเราจะได้ว่า

ฉะนั้นด้วย Master Theorem เราจะได้ว่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

T(n)=O(n\log n)\,

418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9

เนื้อหา

อัลกอริทึม

ความถูกต้อง

ข้อความที่ 1

Error

Error

Error

Error

ข้อความที่ 2

Error

ประสิทธิภาพ

Error

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ