بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 20: مرتب‌سازی و مقایسه Sorting and Comparing

مرتب کردن با جابه‌جاییِ همسایه‌ها و «جفت‌های نامرتب»، پیدا کردنِ بزرگ‌ترین با کمترین مقایسه، جدولِ حذفی، و برگرداندنِ پنکیک‌ها.

در این جلسه یاد می‌گیری

درس

عددها را با جابه‌جا کردنِ دو همسایه مرتب کن. بعد «از اول» را بزن و سعی کن با جابه‌جایی‌های کمتری انجامش دهی. کمترین تعداد چند است؟

جفتِ نامرتب: دو عدد که عددِ بزرگ‌تر جلوتر از کوچک‌تر آمده. در ۳، ۱، ۴، ۵، ۲ جفت‌های نامرتب: (۳،۱)، (۳،۲)، (۴،۲)، (۵،۲): ۴ تا. هر جابه‌جاییِ دو همسایه دقیقاً یک جفت را عوض می‌کند: اگر نامرتب بودند مرتب می‌شوند (یکی کم) و برعکس. پس کمترین تعداد جابه‌جایی = تعداد جفت‌های نامرتب. بیشترینِ آن برای n عدد وقتی است که کاملاً برعکس باشند: C(n، ۲).

پیدا کردنِ بزرگ‌ترین: با هر مقایسه یکی «می‌بازد». هر عددی جز بزرگ‌ترین باید دست‌کم یک بار ببازد (وگرنه ممکن است بزرگ‌ترین باشد). پس دست‌کم ⁦n − ۱⁩ مقایسه لازم است، و ⁦n − ۱⁩ هم کافی است (قهرمانِ فعلی را با بعدی مقایسه کن).
جدول حذفی: هر بازی دقیقاً یک تیم را حذف می‌کند و همه جز قهرمان باید حذف شوند: n تیم ← ⁦n − ۱⁩ بازی.

دومین بهترین: در جدول حذفیِ ۱۶ نفره، دومی حتماً فقط به قهرمان باخته. قهرمان ۴ بار بازی کرده، پس ۴ نفر نامزدِ دومی‌اند و ۳ بازیِ دیگر بینشان کافی است: ⁦۱۵ + ۳ = ۱۸⁩ مقایسه.
پنکیک: دسته‌ای پنکیک با اندازه‌های مختلف؛ تنها کار مجاز این است که چند تای بالا را با کفگیر برگردانی. برای مرتب کردنِ هر دسته‌ی ۴تایی، ۴ برگرداندن همیشه کافی است.

چالش‌ها

  1. A Knockout Cup (آسان)
  2. Count the Swaps (آسان)
  3. The Worst Row (متوسط)
  4. The Heaviest Box (متوسط)
  5. The Runner-Up (سخت)
  6. Flipping Pancakes (سخت)

← جلسه‌ی 19: ترازو و وزن کردن جلسه‌ی 21: آزمونک بازی و الگوریتم →