عدد المصفوفات الفرعية التي يساوي مجموعها عددا معينا: حلول فعالة

يعد حل مشكلة العثور على عدد المصفوفات الفرعية ، وهو مجموع العناصر التي تساوي عددا معينا ، إحدى المهام العاجلة في مجال تطوير الخوارزمية. غالبا ما توجد مثل هذه المهام في مجالات مختلفة ، بما في ذلك تحليل البيانات ورؤية الكمبيوتر. يساعد حل هذه المشكلة على تحسين الحسابات ويزيد من كفاءة الخوارزمية.

في هذه المقالة ، سننظر في عدة طرق فعالة لحل المشكلة. نهج واحد للحل هو استخدام خوارزمية مؤشرين. تسمح لك هذه الخوارزمية بالعثور على جميع المصفوفات الفرعية التي يساوي مجموع عناصرها رقما معينا في الوقت الخطي ، أي في الوقت المناسب ا (ن) ، أين ن هو حجم المصفوفة.

تعتمد طريقة أخرى لحل المشكلة على استخدام جدول التجزئة. تسمح لك جداول التجزئة بكتابة البيانات وقراءتها في وقت ثابت في الحالة المتوسطة. عند استخدام جدول تجزئة ، يمكننا كتابة مجاميع العناصر الفرعية في الجدول ، ثم التحقق مما إذا كان هناك زوج أرقام محدد في الجدول. إذا كانت الإجابة بنعم ، فإننا نزيد العداد. تعمل هذه الطريقة أيضا في الوقت الخطي ، ولكن لها وقت تشغيل كبير ثابت بسبب استخدام جدول التجزئة.

كل من هذه الخوارزميات لها مزاياها وعيوبها ، واختيار طريقة لحل المشكلة يعتمد على الوضع المحدد. في هذه المقالة ، نظرنا في طريقتين فقط ، ولكن هناك طرق أخرى لحل المشكلة. يمكنك التعرف على القائمة الكاملة للطرق الفعالة في الأدبيات المتخصصة أو باستخدام موارد الإنترنت.

1. ما هو عدد المصفوفات الفرعية التي يساوي مجموعها عددا معينا?
2. حل المشكلة باستخدام القوة الغاشمة
3. حل المشكلة باستخدام مبالغ البادئة
4. حل المشكلة باستخدام مؤشرين
5. حل المشكلة باستخدام جدول التجزئة
6. حل المشكلة باستخدام البرمجة الديناميكية
7. مقارنة فعالية النهج المختلفة
8. سؤال وجواب
9. ما هي الطرق الفعالة لحل مشكلة إيجاد عدد المصفوفات الفرعية بمجموع يساوي عددا معينا?
10. كيف خوارزمية باستخدام جدول تجزئة العمل على حل مشكلة العثور على عدد من المصفوفات الفرعية مع مبلغ يساوي عدد معين?

ما هو عدد المصفوفات الفرعية التي يساوي مجموعها عددا معينا?

عدد المصفوفات الفرعية التي يساوي مجموعها رقما معينا هي مهمة تتمثل في إيجاد جميع المصفوفات الفرعية الممكنة داخل مصفوفة معينة يكون مجموع عناصرها مساويا لعدد معين.

في مشكلة الصف الفرعي ، والمعروفة أيضا باسم مجموع الأعداد الفرعية ، يتم إعطاؤك مصفوفة من الأعداد الصحيحة وتحتاج إلى إيجاد عدد المصفوفات الفرعية التي يساوي مجموع عناصرها عددا معينا. يمكن أن تتكون المصفوفات الفرعية من عنصر واحد أو أكثر ويمكن أن تكون بأحجام مختلفة. المهمة هي تحديد عدد هذه المصفوفات الفرعية.

هذه المهمة ذات أهمية عملية كبيرة ويمكن تطبيقها في مجالات مختلفة مثل تحليل البيانات والتمويل والخوارزميات. يمكن أن يساعد عدد المصفوفات الفرعية التي يساوي مجموعها عددا معينا في حل المشكلات المختلفة ، على سبيل المثال ، تحديد الحد الأقصى للمصفوفات الفرعية بمبلغ معين أو العثور على جميع المجموعات الممكنة من المصفوفات الفرعية.

يمكن استخدام خوارزميات وأساليب مختلفة لحل هذه المشكلة ، مثل التكرار من خلال جميع المصفوفات الفرعية ، والبرمجة الديناميكية ، واستخدام جداول التجزئة أو مجاميع البادئة. كل من هذه الأساليب لها مزاياها ويمكن أن تكون فعالة اعتمادا على المهمة المحددة وحجم بيانات الإدخال.

يوجد أدناه جدول يحتوي على مثال صفيف ورقم معين لفهم جوهر المهمة بشكل أفضل:

في هذا المثال ، تتمثل المهمة في العثور على جميع المصفوفات الفرعية التي يبلغ مجموعها 6. في هذه الحالة ، هناك نوعان من المصفوفات الفرعية التي تشكل عناصرها مجموع 6: [1 ، 2 ، 3] و [2 ، 4]. لذلك ، فإن عدد المصفوفات الفرعية التي يبلغ مجموعها 6 في هذا المثال هو 2.

حل المشكلة باستخدام القوة الغاشمة

إحدى الطرق الممكنة لحل مشكلة عدد المصفوفات الفرعية بكمية معينة هي استخدام القوة الغاشمة. تسمح لك هذه الطريقة بالنظر في جميع المجموعات الممكنة من العناصر والعثور على العناصر التي يساوي مجموعها رقما معينا.

خطوات لحل المشكلة باستخدام القوة الغاشمة:

1. نحصل على بيانات الإدخال: مجموعة من الأرقام ورقم يجب العثور على مجموعها.
2. تهيئة متغير لحساب عدد المصفوفات الفرعية بمبلغ معين.
3. نذهب من خلال جميع الفئات الفرعية الممكنة. نبدأ بالعنصر الأول ونضيف عناصر لاحقة حتى يصبح مجموع الصف الفرعي مساويا للرقم المحدد أو حتى نصل إلى نهاية المصفوفة.
4. إذا كان مجموع الصف الفرعي يساوي الرقم المحدد ، فقم بزيادة العداد بمقدار واحد.
5. Повторяем шаги 3 и 4 для всех других возможных подмассивов.
6. Возвращаем количество подмассивов с заданной суммой.

Пример решения задачи с использованием перебора:

function countSubarrays(array, target) {

let count = 0;

for (let i = 0; i < array.length; i++) {

let sum = 0;

for (let j = i; j < array.length; j++) {

sum += array[j];

if (sum === target) {

count++;

}

}

}

return count;

}

const array = [1, 2, 3, 4, -2, 5];

const target = 7;

نتيجة كونست = كونتسوبرايس (صفيف ، الهدف);

وحدة التحكم.سجل (نتيجة) ؛ / / الإخراج: 3

.

ومع ذلك ، تجدر الإشارة إلى أن حل المشكلة باستخدام التكرار قد يعمل بشكل غير فعال مع عدد كبير من العناصر في المصفوفة. في مثل هذه الحالات ، يوصى باستخدام طرق أخرى لحل المشكلة ، والتي تسمح لك بتحسين وقت تنفيذ البرنامج.

حل المشكلة باستخدام مبالغ البادئة

تتمثل إحدى الطرق الفعالة لحل مشكلة عدد المصفوفات الفرعية بمبلغ يساوي رقما معينا في استخدام مبالغ البادئة. مجاميع البادئة هي مصفوفة يكون فيها كل عنصر مساويا لمجموع جميع العناصر السابقة والعنصر الحالي للمصفوفة الأصلية.

لحل المشكلة باستخدام مبالغ البادئة ، يجب تنفيذ الخطوات التالية:

1. قم بإنشاء مصفوفة بادئة بإضافة كل عنصر من عناصر المصفوفة الأصلية بمجموع العناصر السابقة.
2. كرر من خلال جميع المصفوفات الفرعية الممكنة وحساب مجموعها لكل مصفوفات فرعية.
3. إذا كان مجموع المصفوفات الفرعية يطابق الرقم المحدد ، فقم بزيادة العداد لعدد المصفوفات الفرعية.

هذا النهج يجعل من الممكن تسريع حل المشكلة ، لأنه يقلل من تعقيد الخوارزمية إلى س(ن) ، أين ن هو حجم المصفوفة الأصلية.

مثال:

في هذا المثال ، عدد المصفوفات الفرعية التي يساوي مجموعها 6 هو 2 (المصفوفات الفرعية [1 ، 2 ، 3] و [2 ، 4]).

حل المشكلة باستخدام مؤشرين

إحدى الطرق الفعالة لحل مشكلة إيجاد عدد المصفوفات الفرعية التي يساوي مجموعها رقما معينا هي استخدام مؤشرين.

يعتمد نهج المؤشرين على فرز المصفوفات الفرعية. الفكرة هي أننا ننقل مؤشرين-يشير مؤشر واحد إلى بداية الصف الفرعي ، ويشير المؤشر الثاني إلى نهاية الصف الفرعي. ثم نلخص قيم العناصر بين المؤشرات ومقارنتها برقم معين.

إذا كان مجموع العناصر يساوي الرقم المحدد ، فإننا نزيد العداد ونحرك مؤشر بداية الصف الفرعي إلى اليمين. إذا كان مجموع العناصر أكبر من الرقم المحدد ، فإننا نحرك مؤشر نهاية الصف الفرعي إلى اليسار. إذا كان مجموع العناصر أقل من الرقم المحدد ، فإننا نحرك مؤشر بداية الصف الفرعي إلى اليمين. تتكرر هذه العملية حتى يصل أحد المؤشرات إلى نهاية المصفوفة.

ميزة هذا النهج هو لها ا (ن) تعقيد الوقت ، أين ن هو حجم المصفوفة. باستخدام مؤشرين ، نقوم بتقليل عدد التكرارات في الحلقة وتقليل وقت تنفيذ الخوارزمية.

Пример кода, реализующего данный подход:

وظيفة كونتسوبرايس (أر ، تارجيتسوم) {

ترك اليسار = 0;

دع اليمين = 0;

دعونا مجموع = 0;

دعونا العد = 0;

في حين (حق < آر.الطول) {

مجموع + = آر [حق];

بينما (مجموع > الهدف) {

مجموع - = آر [يسار];

غادر++;

}

إذا (مجموع === الهدف) {

count++;

}

صحيح++;

}

عد العودة;

}

. بعد ذلك ، في حلقة ، نجمع قيم العناصر بين المؤشرات ، ونقوم بتحديث المؤشرات اعتمادا على المجموع ، ونزيد العداد إذا كان المجموع يساوي رقما معينا. في النهاية ، تقوم الدالة بإرجاع عدد المصفوفات الفرعية بالمبلغ المحدد.

يتيح لك استخدام مؤشرين حل مشكلة العثور على عدد المصفوفات الفرعية التي يساوي مجموعها عددا معينا بشكل فعال. تعقيد الوقت من خوارزمية س (ن) يجعلها فعالة جدا لمجموعات البيانات الكبيرة.

حل المشكلة باستخدام جدول التجزئة

تتمثل إحدى الطرق الفعالة لحل مشكلة عدد المصفوفات الفرعية بكمية معينة في استخدام جدول التجزئة. يسمح لك جدول التجزئة بتخزين أزواج القيمة الرئيسية ويوفر وصولا سريعا إلى البيانات.

الخوارزمية لحل المشكلة باستخدام جدول التجزئة هي كما يلي:

1. إنشاء جدول تجزئة فارغ.
2. أعلن عن مجموع المتغير وقم بتعيينه القيمة 0.
3. أعلن عن متغير الكمية وقم بتعيين القيمة 0.
4. تذهب من خلال مجموعة من الأرقام في نفس الوقت جمع العناصر.
5. في كل خطوة ، تحقق مما إذا كان هناك عنصر في جدول التجزئة بمفتاح يساوي المبلغ الحالي مطروحا منه الرقم المحدد.
6. إذا كان هناك مثل هذا العنصر ، فقم بزيادة قيمة متغير الكمية بقيمة عنصر جدول التجزئة باستخدام هذا المفتاح.
7. أضف عنصرا بمفتاح يساوي المقدار الحالي إلى جدول تجزئة بقيمة 1 أو قم بزيادة قيمة عنصر في جدول التجزئة باستخدام هذا المفتاح بمقدار 1 إذا كان هناك عنصر به مثل هذا المفتاح موجودا بالفعل.
8. في نهاية الحلقة ، قم بإخراج قيمة متغير الكمية.

ميزة استخدام جدول التجزئة هي القدرة على حل المشكلة في الوقت الخطي س(ن) ، أين ن هو عدد عناصر المصفوفة. يتم إنشاء جدول التجزئة والبحث عن العناصر فيه في وقت ثابت س (1).

Пример кода на языке Python, реализующего решение задачи с использованием хэш-таблицы:

def countSubarrays(arr, target):

count = 0

sum_map = {}

curr_sum = 0

for num in arr:

curr_sum += num

if curr_sum == target:

count += 1

if curr_sum - target in sum_map:

count += sum_map[curr_sum - target]

if curr_sum in sum_map:

sum_map[curr_sum] += 1

else:

sum_map[curr_sum] = 1

return count

В данном примере функция countSubarrays получает на вход массив arr и целевое число target. يقوم بإرجاع عدد المصفوفات الفرعية بمبلغ يساوي الهدف.

حل المشكلة باستخدام البرمجة الديناميكية

البرمجة الديناميكية هي طريقة لحل المشكلات تعتمد على تقسيم المشكلة الأصلية إلى مهام فرعية أبسط ، يتم حفظ حلها واستخدامه لحل المشكلة الأصلية. في حالة وجود مشكلة في المصفوفات الفرعية التي يساوي مجموعها رقما معينا ، تتيح لك البرمجة الديناميكية العثور على عدد هذه المصفوفات الفرعية بطريقة فعالة.

لحل هذه المشكلة باستخدام البرمجة الديناميكية ، يمكن تطبيق الخوارزمية التالية:

1. إنشاء مجموعة موانئ دبي ثنائية الأبعاد من حجم (ن+1) س (مجموع + 1) ، حيث ن هو حجم الصفيف الأصلي ، المبلغ هو الرقم المحدد
2. تهيئة الصف الأول من صفيف موانئ دبي بالقيمة 0 ، باستثناء عنصر موانئ دبي [0] [0] ، الذي تمت تهيئته بالقيمة 1
3. تكرارية ملء مجموعة موانئ دبي مع الحلقة التالية:

إلى عن على أنا = 1 إلى ن:

لكل ي = 0 لمجموع:

إذا ي < آر [ط-1]:

تعيين موانئ دبي [أنا] [ي] يساوي موانئ دبي [أنا-1] [ي]

خلاف ذلك:

تعيين موانئ دبي [أنا] [ي] يساوي مجموع موانئ دبي [أنا-1] [ي] وموانئ دبي [أنا-1] [ي-آر [أنا-1]]

بعد الانتهاء من الحلقة ، القيمة موانئ دبي [ن] [مجموع] سيمثل عدد المصفوفات الفرعية التي يساوي مجموعها الرقم المحدد.

مثال على تنفيذ الخوارزمية في بايثون:

مواطنه الكونت_الصباريات (آر آر ، سوم):

ن = لين (آر)

موانئ دبي = [[0] * (مجموع + 1) لـ _ في النطاق (ن + 1)]

موانئ دبي [0] [0] = 1

لأني في النطاق (1 ، ن+1):

إلى عن على ي في النطاق (مجموع + 1):

إذا ي < آر [ط-1]:

موانئ دبي [ط] [ي] = موانئ دبي [ط-1] [ي]

آخر:

موانئ دبي [ط] [ي] = موانئ دبي [ط-1] [ي] + موانئ دبي [ط-1] [ي-آر [ط-1]]

عودة موانئ دبي [ن] [مجموع]

آر = [1, 2, 3, 4, 5]

المجموع = 7

النتيجة = العد_الصبار(آر ، سوم)

طباعة (النتيجة) # الإخراج: 2

في هذا المثال ، الصفيف الأصلي آر هو [1, 2, 3, 4, 5], ومجموع العدد المحدد هو 7. ستكون نتيجة تنفيذ دالة الكونتسوبرايس هي الرقم 2 ، نظرا لوجود مصفوفين فرعيين في المصفوفة الأصلية مجموعهما 7 ([2 ، 5] و [3 ، 4]).

مقارنة فعالية النهج المختلفة

عند حل مشكلة العثور على عدد المصفوفات الفرعية بكمية معينة ، هناك عدة طرق مختلفة ، لكل منها فعاليته الخاصة.

1. القوة الغاشمة: أبسط حل ، والذي يتمثل في المرور بجميع المصفوفات الفرعية وحساب مجموع كل منها. هذا النهج لديه أسوأ كفاءة مع التعقيد ا (ن^3) ، أين ن هو عدد العناصر في المصفوفة.

2. مجاميع البادئة: يعتمد هذا الأسلوب على استخدام مجاميع البادئة ، والتي تتيح لك العثور بسرعة على مجموع أي تصنيف فرعي. للقيام بذلك ، تحتاج أولا إلى حساب جميع مجاميع البادئة ثم ، باستخدامها ، ابحث عن مجموع المصفوفات الفرعية في ا(1) عملية. هذا النهج له تعقيد ا (ن^2) ، لأنه يتطلب تلخيص جميع المصفوفات الفرعية.

3. جداول التجزئة: حل فعال آخر هو استخدام جداول التجزئة لتخزين النتائج الوسيطة. عند المرور عبر المصفوفة ، يتم حساب المقدار الحالي للمصفوفة الفرعية ويتم التحقق مما إذا كانت هناك قيمة في جدول التجزئة تساوي الفرق بين المقدار الحالي والرقم المحدد. في حالة حدوث مثل هذه القيمة ، يتم زيادة عداد الصف الفرعي. هذا النهج لديه تعقيد س (ن) وهو الأكثر فعالية.

وبالتالي ، عند حل مشكلة العثور على عدد المصفوفات الفرعية بكمية معينة ، فإن النهج الأكثر فعالية والموصى به هو استخدام جداول التجزئة ، نظرا لأنه يحتوي على أقل تعقيد مقارنة بالنهج الأخرى.

سؤال وجواب

ما هي الطرق الفعالة لحل مشكلة إيجاد عدد المصفوفات الفرعية بمجموع يساوي عددا معينا?

في مشكلة العثور على عدد المصفوفات الفرعية بمجموع يساوي رقما معينا ، يمكن استخدام خوارزميات مختلفة. واحد منهم هو خوارزمية باستخدام جدول التجزئة ، والذي يسمح لك بحل المشكلة في الوقت الخطي. طريقة أخرى هي استخدام مؤشرين يتحركان من بداية ونهاية المصفوفة. كما يسمح لك بحل المشكلة في الوقت الخطي. حل فعال آخر هو خوارزمية تستخدم مجاميع البادئة ، والتي تسمح لك بحل المشكلة في الوقت التربيعي.

كيف خوارزمية باستخدام جدول تجزئة العمل على حل مشكلة العثور على عدد من المصفوفات الفرعية مع مبلغ يساوي عدد معين?

تعمل الخوارزمية التي تستخدم جدول تجزئة لحل مشكلة العثور على عدد المصفوفات الفرعية بمبلغ يساوي رقما معينا على النحو التالي. أولا ، يتم إنشاء جدول تجزئة فارغ. ثم يتم عرض المصفوفة باستخدام حلقة ، يتم من خلالها حساب المجموع الحالي للمصفوفة الفرعية. لكل مبلغ تم العثور عليه ، يتم التحقق من وجود مفتاح في جدول التجزئة يساوي الفرق بين الرقم المحدد والمبلغ الحالي. إذا كان هناك مثل هذا المفتاح ، فهذا يعني أنه تم العثور على صف فرعي بالمبلغ المطلوب ، ويتم زيادة العداد. بعد ذلك ، يتم إضافة المبلغ الحالي وموقعه في المصفوفة إلى جدول التجزئة. وبالتالي ، فإن الخوارزمية تجعل من الممكن العثور بكفاءة على عدد المصفوفات الفرعية بمجموع يساوي رقما معينا.