الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مسئله‌ی حداکثر مجموع - الگوریتمستان
الگوریتمستان
  »  

مسئله‌ی حداکثر مجموع

        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی حداکثر مجموع
       »  مسئله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسئله

مسئله

  [بازگشت به فهرست]

ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است.

به عنوان مثال، برای ماتریس زیر:

  

\[ \begin{matrix} 0 & -2 & -7 & 0 \\ 9 & 2 & -6 & 2 \\ -4 & 1 & -4 & 1 \\ -1 & 8 & 0 & -2 \end{matrix} \]

  

زیرماتریس بیشینه به این ترتیب خواهد بود:

  

\[ \begin{matrix} 9 & 2 \\ -4 & 1 \\ -1 & 8 \end{matrix} \]

  

برنامه‌ای بنویسید که مجموع عناصر زیرماتریس بیشینه را چاپ کند.

  

ورودی برنامه

  [بازگشت به فهرست]

اولین سطر ورودی شامل عدد $N$ (نابیشتر از 100) است. در سطرهای بعدی تعداد $N^2$ عدد صحیح قرار دارند که عناصر ماتریس مفروض را با نمایش سطری مشخص می‌کنند. یعنی $N$ عدد اول مربوط به سطر اول ماتریس است و الی آخر.

  

4

0   -2   -7   0   9   2   -6   2

-4   1   -4   1   -1

8   0   -2

  

خروجی برنامه

  [بازگشت به فهرست]

خروجی شامل مجموع عناصر زیرماتریس بیشینه خواهد بود.

  

15

  

منبع: وب‌سایت UVa Online Judge - مسئله‌ی Maximum Sum

  

حل مسئله

  [بازگشت به فهرست]

فرض کنید منظور از (Sum(R1, C1, R2, C2 مجموع عناصر زیرماتریسی است که در سطرهای R1 تا R2 و ستون‌های C1 تا C2 قرار دارد. به عنوان مثال (Sum(0, 0, N - 1, N - 1 مجموع تمام عناصر از سطر اول تا آخر و ستون اول تا آخر است که همان مجموع کل عناصر ماتریس می‌شود. با این تعریف، هدف یافتن مقدار خروجی بیشینه برای تابع Sum با توجه به ورودی‌های مختلف آن است.

ساده‌ترین راه برای حل این مسئله بررسی تمام زیرماتریس‌ها و محاسبه‌ی مجموع عناصر آنها است:

  

int main()
{
    int n, i, j, k, l, a, b, s, maxSum, matrix[100][100];
    cin >> n;
    for(i = 0 ; i < n ; i++){
        for(j = 0 ; j < n ; j++){
            cin >> matrix[i][j];
        }
    }
10     maxSum = matrix[0][0];
11     for(i = 0 ; i < n ; i++){
12         for(j = 0 ; j < n ; j++){
13             for(k = i ; k < n ; k++){
14                 for(l = j ; l < n ; l++){
15                     s = 0;
16                     for(a = i ; a <= k ; a++){
17                         for(b = j ; b <= l ; b++){
18                             s += matrix[a][b];
19                         }
20                     }
21                     if(s > maxSum){
22                         maxSum = s;
23                     }
24                 }
25             }
26         }
27     }
28     cout << maxSum << endl;
29     return 0;
30 }

  

این روش محاسبه‌ی مستقیم با توجه به شش حلقه‌ی تکرار تو در تو از مرتبه‌ی اجرای $ O(N^6)$ است که برای Nهای بزرگ کارایی نداشته و با خطای Time limit exceeded مواجه خواهد شد.

علت این مشکل در محاسبات تکراری موجود در این روش نهفته است. به عنوان مثال، برای محاسبه‌ی (Sum(2, 3, 5, 7 قطعه کد فوق تمام عناصر بین سطرهای 2 و 5 و ستون‌های 3 و 7 را جمع می‌زند. در مرحله‌ی بعد (Sum(2, 3, 5, 8 محاسبه می‌شود که تمامی عناصر بین سطرهای 2 تا 5 و ستون‌های 3 تا 8 جمع زده می‌شوند؛ یعنی محاسبه‌ی تابع با این ورودی‌ها یکبار دیگر به طور کامل محاسبه‌ی تابع قبلی را انجام داده و تنها عناصر سطرهای 2 تا 5 مربوط به ستون 8 را اضافه می‌کند. این محاسبات تکراری برای $N$-های بزرگی مانند 100 سربار زمانی بسیار زیادی تولید می‌کند.

کلید حل معما در این است که بدانیم:

  

Sum(R1, C1, R2, C2) = Matrix[R2][C2] + Sum(0, 0, R2 - 1, C2) + Sum(0, 0, R2, C2 - 1) - Sum(0, 0, R2 - 1, C2 - 1) - Sum(0, 0, R1 - 1, C1) - Sum( 0, 0, R1, C1 - 1) + Sum(0, 0, R1 - 1, C1 - 1)

  

اثبات این رابطه به عنوان یک تمرین خوب به خواننده واگذار می‌شود. در این رابطه محاسبه‌ی تابع Sum به جمع زدن عنصر سطر R2 و ستون C2 با شش محاسبه‌ی بازگشتی از خود تابع Sum تبدیل می‌شود. ویژگی اصلی این شش تابع در این است که دو پارامتر اول آنها همواره صفر هستند. یعنی در کل به صورت (Sum(0, 0, a, b هستند که مجموع عناصر ماتریس از ابتدای آن تا سطر a و ستون b خواهد بود. محاسبه‌ی چنین عباراتی با دو حلقه‌ی تکرار تو در تو با مرتبه‌ی اجرایی $ O(N^2)$ میسر است. نتایج این محاسبات برای استفاده در مرحله‌ی بعدی در محل جداگانه‌ای ذخیره می‌شود.

به همین ترتیب می‌توان از رابطه‌ی زیر نیز استفاده کرد که عملیات کمتری نیاز دارد:

  

Sum(R1, C1, R2, C2) = Sum(0, 0, R2, C2) - Sum(0, 0, R2, C1 - 1) - Sum(0, 0, R1 - 1, C2) + Sum(0, 0, R1 - 1, C1 - 1 )

  

پس از اتمام محاسبات مرحله‌ی اول، به سراغ محاسبه‌ی تمامی حالات (Sum(R1, R2, C1, C2 می‌رویم تا مقدار آن به ازای زیرماتریس بیشینه به دست بیاید. تولید مختصات هر زیرماتریس با چهار حلقه‌ی تو در تو امکان‌پذیر است که سطرهای ابتدا و انتها و ستون‌های ابتدا و انتها را مشخص می‌کنند. در داخل این حلقه‌ها مقدار (Sum(R1, R2, C1, C2 بر اساس رابطه‌ی فوق و مقادیر ذخیره شده در حافظه محاسبه شده و در نهایت بیشترین آنها به عنوان زیرماتریس بیشینه مشخص می‌شود.

چنین الگوریتمی با توجه به چهار حلقه‌ی تکرار تو در تو از مرتبه $O( N^4)$ است که در مقایسه با مرتبه‌ی $O( N^6)$ بهبود چشم‌گیری دارد. البته می‌توان الگوریتم را طوری پیاده‌سازی کرد که عملیات ذخیره‌ی مقادیر (Sum(0, 0, a, b و محاسبات نهایی به صورت همزمان انجام شود. در این حالت سربار $ O( N^2 )$ نیز از ابتدای الگوریتم حذف می‌شود.

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
پیوندها برای مطالعه‌ی بیشتر
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

01 02 03 04 05 06 07 08 09 10 11 12 13 14

 


• Aysa
جمعه، ۲۲ آذر ماه ۱۳۹۲، ساعت ۱۰:۵۵

با سلام

میشه زمان های حذف و اضافه رو هم در درخت heap تحلیل کنید؟؟؟؟؟؟

ممنون میشم!01


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۲۳۸۷ روز
تعداد بازدید:  ۱۰۹۷۷ بازدید
تعداد امتیاز:  ۷ امتیاز
میانگین امتیاز:  ۴.۴۳  از  ۵.۰۰
»  کتاب مقدمه‌ای بر مسابقات برنامه‌نویسی
        معرفی کتاب فارسی «مقدمه‌ای بر مسابقات برنامه‌نویسی» برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود نسخه‌ی الکترونیکی
»  سوالات تمرینی مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018 (سری دوم)
        سری دوم سوالات تمرینی برای شرکت کنندگان مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018
»  سوالات تمرینی مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018 (سری اول)
        سری اول سوالات تمرینی برای شرکت کنندگان مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018
»  مسئله‌ی Column Addition
        بررسی مسئله‌ی Column Addition، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی آتش‌سوزی در برره
        بررسی مسئله‌ی آتش در برره، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  کتاب راهنمای برنامه‌نویسان رقابتی
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
»  مسئله‌ی Turn the Lights Off
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
»  مسئله‌ی Jolly Jumpers
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
»  مسئله‌ی The Trip
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی 3n+1 Problem
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی Encrypted SMS
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
»  مسئله‌ی Gholam's Simple Game
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران