تمرین ۱
ددلاین تحویل: ۱۸ اردیبهشت ۲۳:۵۹
بخش اول: سوالات مقدماتی — Greedy
سوال ۱ — قابهای تو در تو
تعدادی قاب عکس داده شده است که قاب \(i\)ام ابعاد \(a_i \times b_i\) دارد. میخواهیم بررسی کنیم آیا میتوان ترتیبی از این قابها پیدا کرد به طوری که هر قاب داخل قاب بعدی قرار بگیرد یا نه. چرخش \(90^\circ\) برای هر قاب مجاز است. الگوریتمی با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
پاسخ
شرط اولیه برای قرار گرفتن قاب \(i\) درون قاب \(j\)
میتونیم ابتدا قابها را بر حسب محیط یا مساحت در \(O(n\log n)\) سورت کنیم. سپس برای هر دو قاب متوالی در ترتیب، شرط بالا رو چک کنیم.
برای هر قاب تعریف میکنیم: \(x_i=\min(a_i,b_i)\) و \(y_i=\max(a_i,b_i)\).
میتوان نشان داد شرط قبلی معادلاست با: \(x_i<x_j \land y_i<y_j\).
اگر قاب در حالت چرخیده جا شود، \(x_i<y_j \land y_i<x_j \Rightarrow x_i<x_j \land y_i<y_j\).
حالا قابها را بر اساس \(x_i\) صعودی مرتب میکنیم و قابهای متوالی را با شرط بالا چک میکنیم.
اگر همهی شرطها برقرار بود، جواب مثبت است. زمان اجرا \(O(n\log n)\) است.
سوال ۲ — بیشینهی بازههای سازگار
تعدادی بازهی زمانی به صورت \((s_i,f_i)\) داده شدهاند. میخواهیم بیشترین تعداد بازهی سازگار (non-overlapping intervals) را انتخاب کنیم؛ یعنی هیچ دو بازهی انتخابشده همپوشانی نداشته باشند. یک الگوریتم حریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
سوال ۳ — پوشش بازهها با نقطه
تعدادی بازه روی خط داده شده است. میخواهیم کمترین تعداد نقطه انتخاب کنیم به طوری که هر بازه شامل حداقل یک نقطهی انتخابشده باشد. یک الگوریتم حریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید. ثابت کنید جواب این سوال با جواب سوال قبلی برابر است.
پاسخ - زهرا امیربیگی
سوال ۴ — سکههای فوقفزاینده
سکههایی با مقادیر
در اختیار داریم، به طوری که برای هر \(i \ge 2\) مقدار \(c_i\) از مجموع همهی سکههای قبلی بیشتر است.
از هر نوع سکه دقیقاً یک عدد داریم.
برای یک مقدار هدف \(V\)، میخواهیم مشخص کنیم آیا میتوان زیرمجموعهای از این سکهها را انتخاب کرد که مجموع مقادیرشان دقیقاً برابر \(V\) شود یا نه.
یک الگوریتم حریصانه با مرتبه زمانی \(O(n)\) ارائه دهید.
پاسخ
از اونجا که ارزش هر سکه از تمام سکههای قبلی بیشتره، اگه \(V\) حداقل به اندازهی \(c_n\) باشه حتما باید سکهی \(n\) رو برداریم. چون بقیه سکهها کفافشو نمیدن. اگر کمتر باشه هم که کلا نباید برداریم. پس تکلیف سکهی آخر مشخص میشه. و همینطوری ادامه میدیم از آخر به اول رو سکهها for میزنیم.
سوال ۵ — حذف \(k\) رقم
یک عدد به صورت رشتهای از ارقام به طول \(n\) داده شده است و هیچ رقمی صفر نیست. میخواهیم دقیقاً \(k\) رقم را حذف کنیم تا مقدار عدد حاصل بیشینه شود. الگوریتمی با مرتبه زمانی \(O(n)\) ارائه دهید.
راهنماییها
ابتدا برای k = 1 حل میکنیم.
به جای اینکه عددی بهش نگاه کنیم میتونیم lexicographically بهش نگاه کنیم. میخوایم به بیشترین lexicographically برسیم.
چه زمانی از حذف یک رقم از لحاظ lexicographically سود میکنیم؟
وقتی که رقم بعدیش ازش بزرگتر باشه. حالتی که رفم بعدیش مساویه رو خودتون بررسی کنید.
کدوم بیشترین سود رو داره؟
هر چقدر این افزایش به اول رشته نزدیکتر باشه بیشتر سود میکنیم.
پس ...
پس باید چپترین رقمی که از رقم بعدیش کوچیکتره رو حذف کنیم. اگر چنین رقمی نبود آخرین رفم رو حذف میکنیم.
سوال ۶ — کولهپشتی کسری
تعدادی شیء داریم. شیء \(i\)ام وزن \(w_i\) و ارزش \(v_i\) دارد. یک کولهپشتی با ظرفیت \(W\) داریم و میتوان از هر شیء کسری برداشت (Fractional Knapsack). هدف این است که ارزش کل بیشینه شود. الگوریتمی حریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید و آن را روی ورودی زیر اجرا کنید:
راهنماییها
اگر میشد اشیا رو به ترتیبی مرتب کرد...
تبدیل کیلویی به دونهای
دقت کنید وقتی که میتونیم کسری از اشیا رو برداریم، پس عملا هر شی با وزن \(w_i\) و قیمت \(v_i\) میتونه به \(w_i\) عدد شی یک کیلویی با قیمت \(\frac{v_i}{w_i}\) تبدیل بشه.
این مساله جدید رو چطوری حل کنیم؟
دراصل میخوایم \(W\) عدد شی برداریم، پس کافیه این اشیاء رو بر اساس قیمت مرتب کنیم و \(W\) تای بزرگتر رو برداریم.
حالا چطوری مساله اصلی رو حل کنیم؟
برای هرکدوم از اشیاء، یک ارزش خالص تعریف میکنیم: \(value_i = \frac{v_i}{w_i}\). حالا میدونیم از شئای که ارزش خالص بیشتری داره هرچه بیشتر برداریم بهتره.
سوال ۷ — ساخت مثلث
\(n\) پارهخط با طولهای مثبت \(a_1, a_2, \dots, a_n\) داده شده است. الگوریتمی با مرتبه زمانی \(O(n\log n)\) ارائه دهید که تشخیص دهد آیا میتوان سه پارهخط متمایز از میان آنها انتخاب کرد که تشکیل مثلثی با مساحت مثبت دهند یا نه. در صورت وجود، یکی از سهتاییهای معتبر را خروجی دهید؛ در غیر این صورت اعلام کنید که چنین سهتاییای وجود ندارد.
پاسخ - نگار یاراحمدی
سوال ۸ — ادغام اعداد روی تخته
تعدادی عدد روی یک تخته نوشته شده است. در هر مرحله میتوانید دو عدد \(x\) و \(y\) را از روی تخته پاک کنید و به جای آن عدد \(x+y\) را بنویسید. هزینهی این مرحله برابر \(x+y\) است. میخواهیم پس از انجام \(n-1\) عملیات، فقط یک عدد روی تخته باقی بماند و مجموع هزینهها کمینه شود. الگوریتمی حریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید و آن را روی ورودی زیر اجرا کنید:
سوال ۹ — کدگذاری بدون پیشوند
میخواهیم برای مجموعهای از کاراکترها یک الگوریتم compression طراحی کنیم. برای این کار، میخواهیم به هر کاراکتر یک رشتهی دودویی نسبت دهیم، به طوری که:
- هیچ کد، پیشوند کد دیگر نباشد (prefix-free code) تا متن بهطور یکتا قابل بازخوانی باشد،
- با توجه به اینکه فراوانی وقوع کاراکترها معلوم است، مجموع تعداد بیتهای لازم برای ذخیرهی متن کمینه شود.
به بیان دقیقتر، اگر فراوانی کاراکتر \(i\)ام برابر \(f_i\) و طول کد اختصاصیافته به آن برابر \(\ell_i\) باشد، میخواهیم مقدار \(\sum_i f_i \ell_i\) کمینه شود.
راهنمایی: این مسئله معادل سوال قبلی است.
یک الگوریتم حریصانه با مرتبه زمانی \(O(n\log n)\) برای ساخت این کدها ارائه دهید.
سوال ۱۰ — زمانبندی با مهلت
\(n\) کار داریم. کار \(i\)ام دقیقاً یک واحد زمان طول میکشد، سود آن \(p_i\) است و باید حداکثر تا زمان \(d_i\) تمام شده باشد (Job Sequencing with Deadlines). میخواهیم زیرمجموعهای از کارها را طوری زمانبندی کنیم که مجموع سود بیشینه شود. یک الگوریتم حریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
پاسخ - مائده حیدری
سوال ۱۱ — جایگشت بهینهی \(\sum a_i b_i\)
دو دنباله \(A\) و \(B\) به طول \(n\) داده شدهاند. میخواهیم دنباله \(A\) را جایگشت دهیم.
- (الف) دنباله \(A\) را طوری جایگشت دهید که مقدار \(\sum_{i=1}^{n} a_i b_i\) کمینه شود.
- (ب) دنباله \(A\) را طوری جایگشت دهید که مقدار \(\sum_{i=1}^{n} a_i b_i\) بیشینه شود.
برای هر دو بخش الگوریتم \(O(nlog)\) دهید.
راهنماییها
برای سادگی فرض کنید آرایهی \(B\) سورت شده و فقط میخوایم ترتیب \(A\) رو تغییر بدیم.
جابهجا کردن $a_i$ و $a_j$ چه تاثیری روی تابع هزینه میذاره؟
فرض کنیم \(i > j\) آنگاه \(b_i \geq b_j\)
این جابهجایی در چه شرایطی سود یا ضرر دارد؟
سوال ۱۲ — تخصیص دو تیم
\(n\) نفر داریم که توانایی ورزشی نفر \(i\)ام برابر \(a_i\) و توانایی درسی او برابر \(b_i\) است. میخواهیم دقیقاً \(k\) نفر را برای تیم ورزش و \(n-k\) نفر را برای تیم درس انتخاب کنیم، به طوری که مجموع توانایی افراد در رشتهای که به آن تخصیص داده میشوند بیشینه شود.
پاسخ - Mahdi Mansouri
سوال ۱۳ — مستقل یا مچینگ
یک گراف با \(n\) رأس و \(m\) یال داده شده است. الگوریتمی با مرتبه زمانی \(O(n+m)\) ارائه دهید که یکی از دو مورد زیر را پیدا کند:
- یک مجموعهی مستقل (independent set) با حداقل \(\frac{n}{3}\) رأس،
- یا یک مچینگ (matching) با حداقل \(\frac{n}{3}\) یال.
تضمین میشود که همواره حداقل یکی از این دو وجود دارد.
پاسخ - ایلیا یزدانی ورزی
بخش اول: سوالات مقدماتی — Divide and Conquer
سوال ۱۴ — بازگشت پارامتری
با استفاده از درخت بازگشتی، یک کران تنگ (tight bound) برای رابطهی بازگشتی زیر به دست آورید:
که در آن \(\alpha \in (0,1)\) و \(c>0\) ثابتاند. در پاسخ خود وابستگی کران به \(\alpha\) را به صراحت بررسی کنید.
سوال ۱۵ — زیرآرایهی بدون عضو یکتا (تحلیل)
آرایهی \(A[1 \dots n]\) داده شده است. میخواهیم تشخیص دهیم آیا زیرآرایهای متوالی و ناتهی وجود دارد که در آن هیچ عضو یکتایی نباشد؛ یعنی هر عددی که در زیرآرایه ظاهر میشود، حداقل دو بار در همان زیرآرایه آمده باشد. الگوریتم زیر برای حل این مسئله پیشنهاد شده است:
برای بازهی \(A[l \dots r]\)، در زمانی خطی نسبت به طول بازه بررسی میکنیم آیا عضوی در این بازه دقیقاً یک بار ظاهر شده است یا نه. اگر چنین عضوی وجود نداشت، خود بازه پاسخ مسئله است. در غیر این صورت، فرض کنید \(A[i]\) در \(A[l \dots r]\) تنها یک بار آمده باشد؛ آنگاه هیچ زیرآرایهی معتبری نمیتواند شامل اندیس \(i\) باشد، پس مسئله را به طور بازگشتی روی \(A[l \dots i-1]\) و \(A[i+1 \dots r]\) حل میکنیم. پاسخ بازهی فعلی «بله» است اگر و تنها اگر حداقل یکی از دو فراخوانی پاسخ «بله» برگرداند.
- (الف) درستی الگوریتم را ثابت کنید.
- (ب) مرتبهی زمانی الگوریتم را در بدترین حالت تحلیل کنید.
- (پ) خانوادهای از ورودیها ارائه دهید که نشان دهد تحلیل بخش (b) تنگ است.
سوال ۱۶ — اجتماع، اشتراک، تفاضل
دو آرایهی صعودی \(A[1 \dots n]\) و \(B[1 \dots m]\) داده شدهاند. الگوریتمی با مرتبه زمانی \(O(n+m)\) ارائه دهید که هر یک از مجموعههای زیر را به صورت صعودی محاسبه کند، به طوری که هر مقدار در خروجی فقط یک بار ظاهر شود:
سوال ۱۷ — بزرگترین و دومین بزرگترین
یک آرایه شامل \(n\) عدد متمایز داده شده است. الگوریتمی ارائه دهید که بزرگترین و دومین بزرگترین عنصر آرایه را با حداکثر
مقایسه پیدا کند.
پاسخ - یاسمن کاویانپور
سوال ۱۸ — عنصر \(k\)اُم در دو آرایهی مرتب
دو آرایهی مرتب
داده شدهاند. میخواهیم عنصر \(k\)ام در اجتماع مرتب این دو آرایه را پیدا کنیم، بدون آنکه کل آرایهی نهایی را بسازیم.
- (الف) یک الگوریتم Divide and Conquer با مرتبه زمانی \(O(\log(n+m))\) ارائه دهید.
- (ب) الگوریتم خود را روی ورودی زیر اجرا کنید:
پاسخ - علی الماسی
سوال ۱۹ — بیشینهجمع زیرآرایه
آرایهای از اعداد صحیح داده شده است. میخواهیم بیشترین مجموع یک زیرآرایهی متوالی را پیدا کنیم. یک الگوریتم Divide and Conquer با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
سوال ۲۰ — کمینه و بیشینه
یک آرایه داده شده است. میخواهیم کمینه و بیشینهی آن را با کمترین تعداد مقایسه پیدا کنیم. یک الگوریتم Divide and Conquer ارائه دهید و تعداد مقایسههای آن را به دست آورید و با الگوریتم عادی مقایسه کنید.
پاسخ - صبا خانمحمدی ابهری
سوال ۲۱ — شمارش وارونگیها
یک دنباله از اعداد \(A[1 \dots n]\) داده شده است. میخواهیم تعداد inversionهای آن را محاسبه کنیم.
به هر زوج اندیس \((i,j)\) با
یک inversion گفته میشود.
الگوریتمی با مرتبه زمانی \(O(n\log n)\) برای محاسبهی تعداد inversionها ارائه دهید.
سوال ۲۲ — کاربردهای وارونگی
هر یک از مسائل زیر را به محاسبهی تعداد inversionها تقلیل دهید.
- (الف) تعدادی نقطه در صفحه داده شدهاند. تعداد جفت نقطههایی را بشمارید که یکی در بالا-چپ دیگری باشد؛ یعنی
- (ب) تعدادی بازهی \([l_i,r_i]\) داده شده است. تعداد جفت بازههایی را بشمارید که یکی کاملاً داخل دیگری باشد؛ یعنی
- (پ) یک دنباله شامل اعداد مثبت و منفی داده شده است. تعداد بازههای متوالی را بشمارید که مجموع عناصر آنها منفی است.
پاسخ - سبحان بهزادیپور
سوال ۲۳ — مرتبسازی با جابهجایی مجاور
یک دنبالهی نامرتب از اعداد داده شده است. میخواهیم آن را تنها با استفاده از جابهجاییهای مجاور (adjacent swaps) مرتب کنیم. این مسئله را به محاسبهی تعداد inversionها تقلیل دهید و در نتیجه کمینهی تعداد جابهجاییهای مجاور لازم را به دست آورید.
پاسخ - پارسا عدل پرور
سوال ۲۴ — سکهی تقلبی
\(n\) سکهی به ظاهر یکسان داده شده است که دقیقاً یکی از آنها تقلبی و سبکتر از بقیه است. یک ترازوی کفهای در اختیار داریم که نتیجهی هر وزنکشی یکی از سه حالت «سبکتر بودن کفهی چپ»، «سبکتر بودن کفهی راست»، یا «تساوی» است. کران بهینهی تعداد وزنکشیهای لازم در بدترین حالت را بر حسب \(n\) پیدا کنید، الگوریتمی ارائه دهید که به این کران برسد، و بهینگی کران را ثابت کنید (یعنی نشان دهید هیچ الگوریتمی نمیتواند در بدترین حالت با وزنکشی کمتر به جواب برسد).
پاسخ - سیدمحمدیاسین حاجیخلیلی
سوال ۲۵ — دو تخممرغ
ساختمانی با \(n\) طبقه و دقیقاً \(2\) تخممرغ در اختیار داریم. آستانهی ناشناختهی \(k\) وجود دارد به طوری که تخممرغ رهاشده از طبقهی \(k\) یا پایینتر نمیشکند و رهاشده از بالاتر از آن میشکند. بهطور دقیقتر میدانیم اگر تخممرغ از طبقهی همکف رها شود نمیشکند و اگر از پشتبام (طبقهی \(n + 1\)) رها شود حتما میشکند. تخممرغ شکسته دیگر قابل استفاده نیست. میخواهیم با کمترین تعداد رهاسازی در بدترین حالت، مقدار \(k\) را تعیین کنیم. کران بهینهی تعداد رهاسازیهای لازم در بدترین حالت را بر حسب \(n\) پیدا کنید، استراتژیای ارائه دهید که به این کران برسد، و بهینگی کران را ثابت کنید (یعنی نشان دهید هیچ استراتژیای نمیتواند در بدترین حالت با رهاسازی کمتر به جواب برسد).
پاسخ - نیکی رشیدیان
بخش دوم: سوالات پیشرفته — Greedy
سوال ۲۶ — جستوجو در ماتریس مرتب
یک ماتریس \(n\times n\) داده شده است که سطرها و ستونهایش هر دو صعودیاند. الگوریتمی حریصانه با مرتبه زمانی \(O(n)\) ارائه دهید که بررسی کند آیا عدد \(x\) در ماتریس وجود دارد یا نه. سپس الگوریتم خود را روی ورودی نمونهی زیر اجرا کنید:
سوال ۲۷ — زمانبندی با مدت، مهلت و ارزش
\(n\) کار داریم. کار \(i\)ام مدت زمان \(d_i\)، مهلت \(t_i\) و ارزش \(u_i\) دارد. میخواهیم زیرمجموعهای از کارها را طوری انتخاب و زمانبندی کنیم که همه قبل از مهلت خود تمام شوند و مجموع ارزشها بیشینه شود. الگوریتمی حریصانه یا شبهحریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
سوال ۲۸ — ماتریس دودویی با شمارش سطر و ستون
یک ماتریس دودویی \(n\times n\) میخواهیم بسازیم که در سطر \(i\) دقیقاً \(R[i]\) تا یک و در ستون \(j\) دقیقاً \(C[j]\) تا یک داشته باشد. اگر ساختن چنین ماتریسی ممکن نیست، باید این را اعلام کنیم. الگورتمی از مرتبه زمانی \(O(n^2)\) پیدا کنید.
پاسخ - Amir Mohammad Hamidi
سوال ۲۹ — شاهها روی قطر اصلی
یک صفحه شطرنج \(n \times n\) داریم که در آن \(n\) مهره شاه در خانه های متمایز قرار دارند. در هر حرکت میتوان یک شاه را به یک خانه خالی مجاز منتقل کرد. کمترین تعداد حرکت برای پر کردن قطر اصلی صفحه را با الگوریتمی از مرتبه \(O(nlog)\) بیابید.
پاسخ - پارسا بشری
سوال ۳۰ — برج جعبهها
تعداد \(n\) جعبه داریم که جعبه \(i\)ام وزن \(a_i\) و آستانه تحمل \(b_i\) را دارد. میخواهیم تعیین کنیم آیا میتوان یک برج شامل این \(n\) جعبه ساخت به طوری که به ازای هر جعبه، جمع وزن جعبه های بالاییاش از آستانه تحملش بیشتر نشود. ترتیب جعبه ها را شما باید تعیین کنید. الگوریتمی از مرتبه زمانی \(O(nlog)\) پیدا کنید.
سوال ۳۱ — پرانتزگذاری بهینه
یک دنباله از اعداد به طول \(2n\) داریم. میخواهیم یک رشته پرانتز گزاری معتبر به همین طول انتخاب کنیم، و سپس اعدادی از دنباله را که متناظر با پرانتز باز هستند را انتخاب کنیم. هدف این است جمع اعداد انتخابی بیشینه شود. الگوریتمی از مرتبه زمانی \(O(nlog)\) پیدا کنید تا این مقدار بیشینه را محاسبه کند.
سوال ۳۲ — افراز بازهها
مجموعهای از بازههای زمانی داده شده است. میخواهیم این بازهها را به کمترین تعداد دسته افراز کنیم، به طوری که در هر دسته، هیچ دو بازهای همپوشانی نداشته باشند. الگوریتمی حریصانه با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
سوال ۳۳ — توقف در جایگاه سوخت
روی یک مسیر مستقیم، جایگاههای سوخت در فاصلههای \(x_1 < x_2 < \dots < x_n\) از مبدا قرار دارند و مقصد در فاصله \(D\) است. خودرویی از مبدا حرکت میکند و با هر باک پر حداکثر \(L\) واحد مسیر را میتواند طی کند. فرض کنید در مبدا باک خودرو پر است و در هر جایگاه، در صورت توقف، باک دوباره کاملاً پر میشود. الگوریتمی حریصانه با مرتبه زمانی \(O(n)\) ارائه دهید که کمترین تعداد توقف لازم برای رسیدن به مقصد را پیدا کند، یا اعلام کند که رسیدن به مقصد ممکن نیست.
سوال ۳۴ — بازی حذف مجاور
یک دنباله به طول \(n\) داده شده است. در هر مرحله میتوان دو عدد مجاور را انتخاب کرد، هر دو را از دنباله حذف کرد، و به اندازهی قدرمطلق اختلاف آنها یعنی \(|x-y|\) امتیاز گرفت. میخواهیم با انجام تعداد دلخواهی عملیات، مجموع امتیازها را بیشینه کنیم. الگوریتمی با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
- (الف) حالت \(n\) زوج
- (ب) حالت \(n\) فرد
بخش دوم: سوالات پیشرفته — Divide and Conquer
سوال ۳۵ — یافتن مدین
یک آرایه \(A[1 \dots n]\) داده شده است. مدین را عنصری تعریف میکنیم که در آرایهی مرتبشده، در جایگاه میانی قرار بگیرد؛ یعنی اگر \(n\) فرد باشد، عنصر شمارهی \(\frac{n+1}{2}\)ام، و اگر \(n\) زوج باشد، عنصر شمارهی \(\frac{n}{2}\)ام را مدین در نظر میگیریم. الگوریتمی با مرتبه زمانی \(O(n)\) ارائه دهید که مدین آرایه را پیدا کند.
پاسخ - فاطمه پرویزی
سوال ۳۶ — بزرگترین بلوک یکنواخت
یک ماتریس دودویی \(M\) به ابعاد \(n \times n\) داده شده است. یک solid block زیرماتریسی از فرم \(M[i \dots i'][j \dots j']\) است که همهی درایههای آن برابر باشند. الگوریتمی از جنس Divide and Conquer با مرتبه زمانی \(O(n^2 \log n)\) ارائه دهید که مساحت بزرگترین solid block در \(M\) را پیدا کند.
سوال ۳۷ — نزدیکترین جفت نقطه
به شما \(n\) نقطه روی صفحه داده شده است. میخواهیم فاصلهی نزدیکترین دو نقطه (Closest Pair of Points) را پیدا کنیم. یک الگوریتم Divide and Conquer با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
پاسخ - سبحان آرام
سوال ۳۸ — زیرآرایهی بیشینه با طول محدود
آرایهای از اعداد صحیح، که میتوانند مثبت، منفی یا صفر باشند، و یک عدد \(L\) داده شده است. میخواهیم بیشترین مجموع یک زیرآرایهی متوالی را پیدا کنیم، با این قید که طول زیرآرایه حداکثر \(L\) باشد. یک الگوریتم از جنس Divide and Conquer برای حل این مسئله ارائه دهید.
سوال ۳۹ — زیرآرایهی بدون عضو یکتا
یک آرایه داده شده است. مشخص کنید آیا زیرآرایهای متوالی وجود دارد که هیچ عضوی در آن یکتا نباشد؛ یعنی هر عددی که در این زیرآرایه ظاهر میشود، حداقل دو بار در همان زیرآرایه آمده باشد. الگوریتمی با مرتبه زمانی \(O(n\log n)\) ارائه دهید.
سوال ۴۰ — پوشش با کاشی L-شکل
یک جدول \(2^n \times 2^n\) داده شده است که دقیقاً یکی از خانههای آن بلوکه شده است. میخواهیم بقیهی خانهها را با کاشیهای L-شکل بپوشانیم، به طوری که هر کاشی دقیقاً ۳ خانه را بپوشاند و هیچ دو کاشی روی هم نیفتند. تضمین میشود که این کار همیشه ممکن است. الگوریتمی ارائه دهید که چنین پوششی را بسازد.
پاسخ - پرنیا دباغ
سوال ۴۱ — جایگشت بدون میانگین
یک جایگشت از اعداد \(1\) تا \(n\) بسازید به طوری که برای هر دو اندیس \(i<j\)، میانگین دو عدد \(A_i\) و \(A_j\) در بین عناصر \(A_i,A_{i+1},\dots,A_j\) ظاهر نشود.
سوال ۴۲ — خانهی بزرگتر از همسایگان
یک ماتریس \(n\times m\) داده شده است که همهی درایههای آن با هم متفاوتاند. میخواهیم خانهای پیدا کنیم که مقدار آن از هر یک از همسایههای ضلعیاش بزرگتر باشد. الگوریتمی با مرتبه زمانی \(O(n\log m)\) ارائه دهید.