بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 20

»    مسأله‌ی Encrypted SMS

»    ویدئوهای آموزشی کلاس Programming Challenges  

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی حداکثر مجموع - الگوریتمستان
الگوریتمستان
614.335.00
  »  

       

بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی

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

مسأله

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

    ماتریس مربعی با ابعاد $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(R 1 , C 1 , R 2 , C 2 مجموع عناصر زیرماتریسی است که در سطرهای R 1 تا R 2 و ستون‌های C 1 تا C 2 قرار دارد. به عنوان مثال (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  به جمع زدن عنصر سطر R 2 و ستون C 2 با شش محاسبه‌ی بازگشتی از خود تابع Sum  تبدیل می‌شود. ویژگی اصلی این شش تابع در این است که دو پارامتر اول آنها همواره صفر هستند. یعنی در کل به صورت (Sum(0, 0, a, b  هستند که مجموع عناصر ماتریس از ابتدای آن تا سطر a  و ستون b  خواهد بود. محاسبه‌ی چنین عباراتی با دو حلقه‌ی تکرار تو در تو با مرتبه‌ی اجرایی $ O(N^2)$  میسر است. نتایج این محاسبات برای استفاده در مرحله‌ی بعدی در محل جداگانه‌ای ذخیره می‌شود.

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

      

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

      

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

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


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.

این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
پیوندها برای مطالعه‌ی بیشتر
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        متن فارسی مسأله‌ی Encrypted SMS  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
        متن فارسی مسأله‌ی Gholam's Simple Game  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010 ‌ منطقه‌ای سایت تهران
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016  سایت تهران
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers)  یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسأله‌ی شماره‌ی 343  از UVa Online Judge ، ار سوالات تمرینی کتاب Art of Programming Contest
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels) ، از سوالات مسابقات برنامه‌نویسی بیان
        ویدئوهای آموزشی کلاس Programming Challenges  شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        معرفی کتاب Introduction to Algorithms: A Creative Approach  
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

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

 


» Aysa

جمعه، ۲۲ آذر ماه ۱۳۹۲، ساعت ۱۰:۵۵
با سلام
میشه زمان های حذف و اضافه رو هم در درخت heap  تحلیل کنید؟؟؟؟؟؟
ممنون میشم!01