الحد الأقصى لمشكلة المصفوفة الفرعية هو نفس مشكلة الحد الأقصى للشريحة. يناقش هذا البرنامج التعليمي مشكلة الترميز في C ++. السؤال هو: ما هو أقصى مجموع لأي تسلسل محتمل للأرقام المتتالية داخل المصفوفة؟ هذا يمكن أن يعني مجموعة كاملة. يشار إلى هذه المشكلة وحلها بأي لغة باسم مشكلة المصفوفة الفرعية القصوى. يمكن أن تحتوي المصفوفة على أرقام سالبة محتملة.
يجب أن يكون الحل فعالاً. يجب أن يكون لديه أسرع وقت معقد. اعتبارًا من الآن ، تُعرف أسرع خوارزمية للحل في المجتمع العلمي باسم خوارزمية Kadane. تشرح هذه المقالة خوارزمية Kadane باستخدام C ++.
أمثلة البيانات
ضع في اعتبارك المتجه (المصفوفة) التالي:
المتجه < int > أ = { 5 ، - 7 و 3 و 5 ، - اثنين و 4 ، - 1 } ؛
الشريحة (المصفوفة الفرعية) ذات الحد الأقصى للمجموع هي المتتالية ، {3 ، 5 ، -2 ، 4} ، والتي تعطي مجموع 10. لا يوجد تسلسل آخر محتمل ، حتى المصفوفة بأكملها ، سيعطي مجموعًا يصل إلى قيمة 10. المصفوفة بأكملها تعطي مجموع 7 ، وهو ليس الحد الأقصى للمبلغ.
ضع في اعتبارك المتجه التالي:
المتجه < int > ب = { - اثنين و 1 ، - 3 و 4 ، - 1 و اثنين و 1 ، - 5 و 4 } ؛
الشريحة (المصفوفة الفرعية) ذات الحد الأقصى للمجموع هي المتتالية ، {4، −1، 2، 1} والتي تعطي مجموع 6. لاحظ أنه يمكن أن يكون هناك أرقام سالبة داخل المصفوفة الفرعية للحصول على أقصى مجموع.
ضع في اعتبارك المتجه التالي:
المتجه < int > ج = { 3 و اثنين ، - 6 و 4 و 0 } ؛
الشريحة (المصفوفة الفرعية) ذات أقصى مجموع هي السلسلة ، {3 ، 2} والتي تعطي مجموع 5.
ضع في اعتبارك المتجه التالي:
المتجه < int > د = { 3 و اثنين و 6 ، - 1 و 4 و 5 ، - 1 و اثنين } ؛
المصفوفة الفرعية ذات الحد الأقصى للمجموع هي المتتالية ، {3 ، 2 ، 6 ، -1 ، 4 ، 5 ، -1 ، 2} والتي تعطي مجموع 20. إنها المصفوفة بأكملها.
ضع في اعتبارك المتجه التالي:
المتجه < int > ه = { 5 و 7 ، - 4 ، - 10 ، - 6 و 6 و 5 و 10 ، - 5 و خمسة عشر و 4 ، - 8 ، - خمسة عشر ، - 22 } ؛
هناك نوعان من المصفوفات الفرعية ذات المبالغ القصوى هنا. المجموع الأعلى هو الذي يعتبر حلاً (إجابة) لمشكلة المصفوفة الفرعية القصوى. المصفوفات الفرعية هي: {5 ، 7} بمجموع 12 ، و {6 ، 5 ، 10 ، -5 ، 15 ، 4} بمجموع 35. بالطبع ، الشريحة بمجموع 35 ، هي الاجابة.
ضع في اعتبارك المتجه التالي:
المتجه < int > F = { - 4 و 10 و خمسة عشر و 9 ، - 5 ، - عشرين ، - 3 ، - 12 ، - 3 و 4 و 6 و 3 و اثنين و 8 و 3 ، - 5 ، - اثنين } ؛
هناك نوعان من المصفوفات الفرعية ذات المبالغ القصوى. المجموع الأعلى هو الذي يعتبر حلاً لمشكلة المصفوفة الفرعية القصوى. المصفوفات الفرعية هي: {10 ، 15 ، 9} بمجموع 34 ، و {4 ، 6 ، 3 ، 2 ، 8 ، 3} بمجموع 26. بالطبع ، الشريحة بمجموع 34 هي الإجابة لأن المشكلة تكمن في البحث عن المصفوفة الفرعية ذات المجموع الأكبر وليس المصفوفة الفرعية ذات المجموع الأعلى.
تطوير خوارزمية كادان
المعلومات الواردة في هذا القسم من البرنامج التعليمي ليست العمل الأصلي من Kadane. إنها طريقة المؤلف الخاصة لتعليم خوارزمية Kadane. يوجد أحد المتجهات المذكورة أعلاه ، مع مجاميعه الجارية ، في هذا الجدول:
| بيانات | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | خمسة عشر | 4 | -8 | -خمسة عشر | -22 |
| مجموع تشغيل | 5 | 12 | 8 | -اثنين | -8 | -اثنين | 3 | 13 | 8 | 23 | 27 | واحد وعشرين | 16 | -6 |
| فهرس | 0 | 1 | اثنين | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | أحد عشر | 12 | 13 |
الإجمالي الجاري لفهرس هو مجموع كل القيم السابقة بما في ذلك تلك الخاصة بالفهرس. يوجد تسلسلين مع حد أقصى للمبالغ هنا. إنها {5 ، 7} ، والتي تعطي مجموع 12 ، و {6 ، 5 ، 10 ، -5 ، 15 ، 4} ، ما يعطي مجموع 35. التسلسل الذي يعطي مجموع 35 هو المطلوب .
لاحظ أنه بالنسبة للمجاميع الجارية ، هناك ذروتان هما القيمتان ، 12 و 27. تتوافق هذه القمم مع الفهارس الأخيرة للتسلسلتين.
لذا ، فإن فكرة خوارزمية Kadane هي القيام بالإجمالي الجاري مع مقارنة الحد الأقصى من المبالغ كما يتم مواجهتها ، والانتقال من اليسار إلى اليمين في المصفوفة المحددة.
يوجد متجه آخر من الأعلى ، بإجمالياته الجارية ، في هذا الجدول:
هناك نوعان من التسلسلات ذات المبالغ القصوى. إنها {10، 15، 9} ، ما يعطينا مجموع 34 ؛ و {4، 6، 3، 2، 8، 3} التي تعطي مجموع 26. التسلسل الذي يعطي مجموع 34 ، هو المطلوب.
لاحظ أنه بالنسبة للمجاميع الجارية ، هناك ذروتان هما القيمتان ، 30 و 13. تتوافق هذه القمم مع الفهارس الأخيرة للتسلسلتين.
مرة أخرى ، تتمثل فكرة خوارزمية Kadane في القيام بالإجمالي الجاري مع مقارنة الحد الأقصى من المبالغ كما يتم مواجهتها ، والانتقال من اليسار إلى اليمين في المصفوفة المحددة.
الترميز بواسطة خوارزمية Kadane في C ++
الكود الوارد في هذا القسم من المقالة ليس بالضرورة ما استخدمه كادان. ومع ذلك ، فمن خلال خوارزميته. سيبدأ البرنامج مثل العديد من برامج C ++ الأخرى بـ:
# تضمين# تضمين <ناقل>
استخدام اسم للمحطة؛
يوجد مكتبة iostream مسؤولة عن الإدخال والإخراج. يتم استخدام مساحة الاسم القياسية.
تتمثل فكرة خوارزمية Kadane في الحصول على الإجمالي الحالي أثناء مقارنة الحد الأقصى من المبالغ كما يتم مواجهتها ، والانتقال من اليسار إلى اليمين في المصفوفة المحددة. وظيفة الخوارزمية هي:
int maxSunArray ( المتجه < int > & أ ) {int N = حجم A. ( ) ؛
int maxSum = A [ 0 ] ؛
int runTotal = A [ 0 ] ؛
إلى عن على ( int أنا = 1 ؛ أنا < ن؛ أنا ++ ) {
int tempRunTotal = runTotal + A [ أنا ] ؛ // يمكن أن يكون أصغر من أ [ أنا ]
إذا ( أ [ أنا ] > tempRunTotal )
runTotal = أ [ أنا ] ؛ // في قضية أ [ أنا ] أكبر من إجمالي التشغيل
آخر
runTotal = tempRunTotal ،
إذا ( runTotal > maxAmount ) // مقارنة جميع المبالغ القصوى
maxSum = runTotal ،
}
إرجاع maxAmount.
}
يتم تحديد الحجم N للمصفوفة المحددة (المتجه). المتغير maxSum هو أحد أقصى المبالغ الممكنة. تحتوي المصفوفة على مجموع واحد على الأقل كحد أقصى. يمثل المتغير runTotal الإجمالي الجاري في كل فهرس. كلاهما مهيأ بالقيمة الأولى للمصفوفة. في هذه الخوارزمية ، إذا كانت القيمة التالية في المصفوفة أكبر من الإجمالي الجاري ، فإن القيمة التالية ستصبح إجمالي التشغيل الجديد.
هناك حلقة رئيسية واحدة. يبدأ المسح من 1 وليس الصفر بسبب تهيئة المتغيرات ، maxSum و runTotal إلى A [0] وهو العنصر الأول في المصفوفة المحددة.
في حلقة for-loop ، تحدد العبارة الأولى إجمالي تشغيل مؤقت عن طريق إضافة القيمة الحالية إلى المجموع التراكمي لجميع القيم السابقة.
بعد ذلك ، هناك بناء if / else. إذا كانت القيمة الحالية وحدها أكبر من الإجمالي الجاري حتى الآن ، فإن هذه القيمة الفردية تصبح الإجمالي الحالي. هذا مفيد خاصة إذا كانت جميع القيم الموجودة في المصفوفة سالبة. في هذه الحالة ، ستصبح أعلى قيمة سلبية وحدها هي القيمة القصوى (الإجابة). إذا لم تكن القيمة الحالية وحدها أكبر من إجمالي التشغيل المؤقت حتى الآن ، فسيصبح الإجمالي الجاري هو الإجمالي الحالي السابق بالإضافة إلى القيمة الحالية - وهذا الجزء الآخر من بناء if / else.
يختار الجزء الأخير من الكود في الحلقة for-loop بين أي حد أقصى سابق لمجموع تسلسل سابق (مصفوفة فرعية) وأي مجموع أقصى حالي للتسلسل الحالي. لذلك يتم اختيار القيمة الأعلى. يمكن أن يكون هناك أكثر من حد أقصى لمجموع مصفوفة فرعية. لاحظ أن إجمالي التشغيل سيرتفع وينخفض ، حيث يتم فحص الصفيف من اليسار إلى اليمين. إنه يقع عندما يجتمع مع القيم السلبية.
يتم إرجاع الحد الأقصى النهائي لمجموع المصفوفة الفرعية المختارة بعد الحلقة for-loop.
محتوى الوظيفة الرئيسية المناسبة لـ C ++ ، لوظيفة خوارزمية Kadane هو:
المتجه < int > أ = { 5 ، - 7 و 3 و 5 ، - اثنين و 4 ، - 1 } ؛ // { 3 و 5 ، - اثنين و 4 } - > 10int ret1 = maxSunArray ( أ ) ؛
كوت << ret1 << نهاية.
المتجه < int > ب = { - اثنين و 1 ، - 3 و 4 ، - 1 و اثنين و 1 ، - 5 و 4 } ؛ // { 4 ، - 1 و اثنين و 1 } - > 6
int ret2 = maxSunArray ( ب ) ؛
كوت << ret2 << نهاية.
المتجه < int > ج = { 3 و اثنين ، - 6 و 4 و 0 } ؛ // { 3 و اثنين } - > 5
int ret3 = maxSunArray ( ج ) ؛
كوت << ret3 << نهاية.
المتجه < int > د = { 3 و اثنين و 6 ، - 1 و 4 و 5 ، - 1 و اثنين } ؛ // { 3 و اثنين و 6 ، - 1 و 4 و 5 ، - 1 و اثنين } - > 5
int ret4 = maxSunArray ( د ) ؛
كوت << net4 << نهاية.
المتجه < int > ه = { 5 و 7 ، - 4 ، - 10 ، - 6 و 6 و 5 و 10 ، - 5 و خمسة عشر و 4 ، - 8 ، - خمسة عشر ، - 22 } ؛ // { 6 و 5 و 10 ، - 5 و خمسة عشر و 4 } - > 35
int ret5 = maxSunArray ( و ) ؛
كوت << ret5 << نهاية.
المتجه < int > F = { - 4 و 10 و خمسة عشر و 9 ، - 5 ، - عشرين ، - 3 ، - 12 ، - 3 و 4 و 6 و 3 و اثنين و 8 و 3 ، - 5 ، - اثنين } ؛ // { 10 و خمسة عشر و 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ؛
كوت << صحيح 6 << نهاية.
مع ذلك ، سيكون الناتج:
10
6
5
عشرين
35
3. 4
كل سطر يجيب هنا ، يتوافق مع مصفوفة معينة ، بالترتيب.
استنتاج
التعقيد الزمني لخوارزمية Kadane هو O (n) ، حيث n هو عدد العناصر في المصفوفة المحددة. هذا التعقيد الزمني هو الأسرع لأقصى مشكلة مصفوفة فرعية. هناك خوارزميات أخرى أبطأ. تتمثل فكرة خوارزمية كادان في إجراء الإجمالي الحالي ، مع مقارنة الحد الأقصى من المبالغ كما يتم مواجهتها ، والانتقال من اليسار إلى اليمين في المصفوفة المحددة. إذا كانت القيمة الحالية وحدها أكبر من الإجمالي الجاري حتى الآن ، فإن هذه القيمة الفردية تصبح الإجمالي الجاري الجديد. بخلاف ذلك ، يكون إجمالي التشغيل الجديد هو إجمالي التشغيل السابق بالإضافة إلى العنصر الحالي ، كما هو متوقع ، حيث يتم فحص المصفوفة المحددة.
يمكن أن يكون هناك أكثر من مجموع واحد كحد أقصى ، لمختلف المصفوفات الفرعية الممكنة. يتم اختيار أعلى مبلغ أقصى لكل المصفوفات الفرعية الممكنة.
ما هي الفهارس المحددة لنطاق الحد الأقصى للمبلغ المختار؟ - هذا نقاش لبعض الوقت!
كريس