مهمة
اكتب دالة من صفيف إدخال تعسفي ستحدد جميع مجموعات الأرقام التي يبلغ مجموعها 10.للوهلة الأولى ، المهمة بسيطة ، كل ما عليك فعله هو كتابة تكرارات وتصنيف جميع القيم.
أو يمكنك استخدام زيادة ثنائية ، ولكن من أجل التكرار على كل القيم لمتجه بأعداد الطول N ، يستغرق تكرارًا 2 ^ n.
أولاً ، نختار حالة خاصة ، لنفترض أن الصفيف يتكون من أرقام> 0. لاحقًا ، بناءً على هذا المثال ، سننفذ جميع الحالات.الخطوة 1
أ) النظر في واحدة من الحالات الخاصة - مجموع جميع عناصر الصفيف <10.
المنطق بسيط ، sum (V) <10 ، ثم sum (V) -V [i] <sum ، وهذا هو ، إذا كان مجموع المجموعات سيكون دائمًا أقل من 10.
ب) إذا كان مجموع (V) = 10 ، ثم مجموع المبلغ (V) -V [i] <sum. ستكون النتيجة واحدة فقط.
الخطوة 2
نزيل كل ما لا لزوم له من ناقل
على سبيل المثال ، خذ الصفيف [13 ، 10 ، 20 ، 13 ، 13 ، 18 ، 2 ، 9 ، 5 ، 8 ، 8 ، 9 ، 2 ، 1 ، 8 ، 16 ، 4 ، 15 ، 2 ، 2 ، 2 ، 1 ، 5 ، 5 ، 5].
يظهر على الفور أنه لا معنى للبحث عن المجموعات إذا كانت القيمة> 10 ، ولكن كل شيء سوف يصبح واضحًا على الفور. إذا قمنا بفرزها:
[1 ، 1 ، 2 ، 2 ، 2 ، 2 ، 2 ، 4 ، 5 ، 5 ، 5 ، 5 ، 8 ، 8 ، 8 ، 9 ، 9 ، 10 ، 13 ، 13 ، 13 ، 15 ، 16 ، 18 ، 20 ]
في هذه المرحلة ، يمكننا بالفعل أن نعرف بالتأكيد أننا بحاجة إلى حذف جميع العناصر أكبر من 10
ت => [1 ، 1 ، 2 ، 2 ، 2 ، 2 ، 2 ، 4 ، 5 ، 5 ، 5 ، 5 ، 5 ، 8 ، 8 ، 8 ، 9 ، 9 ، 10]
ولكن في الواقع ، كل شيء أكثر إثارة للاهتمام قليلا. نحن بحاجة إلى قصر المتجه على القيمة بحيث V [0] + V [i] <= 10 ؛ حيث أميل إلى N ؛ لكن إذا كانت V [i] = 10 ، فإننا نضيف 10 إلى النتيجة
ت => [1 ، 1 ، 2 ، 2 ، 2 ، 2 ، 2 ، 4 ، 5 ، 5 ، 5 ، 5 ، 5 ، 8 ، 8 ، 8 ، 9 ، 9]
الخطوة 3
هناك عناصر مكررة في صفيف تمت تصفيته بالفعل. إذا قمنا بتحليل المتجه إلى متجهات فرعية ، وحساب مجموعته ، فسنحصل على شيء من هذا القبيل
[1،1] => 2
[2 ، 2 ، 2 ، 2 ، 2] => 10
[4] => 4
[5 ، 5 ، 5 ، 5] => 20
[8 ، 8 ، 8] => 24
[9.9] => 18
يكمن جوهر أفكاري في أنه من غير المنطقي التفكير في مجموعات من الأرقام المكررة إذا كان عددها * القيمة> 10. وهذا يعني أننا نقطع المتجهات حتى يقل مجموعها عن 10 ، ونضيف تلك التي تكون 10 في النتيجة:
[1،1] => [1،1]
[2 ، 2 ، 2 ، 2 ، 2] => [2 ، 2 ، 2 ، 2]
[4] => [4]
[5 ، 5 ، 5 ، 5] => [5]
[8 ، 8 ، 8] => [8]
[9.9] => [9]
نتيجة للخطوة الثالثة ، سيكون متجهنا على النحو التالي
[1 ، 1 ، 2 ، 2 ، 2 ، 4 ، 5 ، 8 ، 9]
كما ترون ، انخفض حجم المتجه من 25 إلى 9 ، وهو أصغر كثيرًا (تذكر عدد التكرارات) ؛
مع الأرقام السالبة
هذا هو أكثر تعقيدا قليلا. سنفترض أننا قمنا بتنفيذ وظيفة العثور على مجموعات لمتجه فرز إيجابي بناءً على القيود السابقة.
مشط (arr ، مبلغ) ، حيث المبلغ هو المبلغ المطلوب ، arr هو ناقل مصنفة من أرقام موجبة
على سبيل المثال ، خذ المتجه:
[19 ، 15 ، -9 ، 3 ، -13 ، -8 ، -12 ، 11 ، -2 ، -10 ، 0 ، 7 ، 17 ، -17 ، -14 ، -15 ، -11 ، -6 ، -12 و -10 ، 9]
1. كسر ناقلاتأ = القيم الإيجابية فقط
ب = القيم السلبية فقط
وانظر أيضًا إذا كانت لدينا قيم = 0
2. فرزفرز المتجهات (تصاعدي موجب ، تنازلي سلبي)
تحقق من الحالة الخاصة لمعرفة الأرقام الإيجابية (الخطوة 1)
3. التحقق من الإيجابيةتحقق من وجود قيم إيجابية
مشط (ب ، 10)3. تحقق من وجود سلبيإنشاء مجموعات من جميع الأرقام السالبة ، ولكن مع التقييد:
(مجموع عناصر modulo) <(مجموع كل الموجب) + 10
نجد مجموعات للمبالغ المرجعية الجديدة (مجموع عناصر المعامل + 10)
4. المساواة 0إذا كان المتجه المصدر له قيمة 0 ، فإننا نضيف جميع المجموعات + 0 إلى النتيجة ؛
نتيجة لهذه القيود ، في المتوسط ، عند اختبار القيم بمجموعة مكونة من 28 و 1000 اختبار ، يكون كسب الوقت 42٪ تقريبًا
كن حذرا حتى لا تبدو عصبية. المؤلف ليست مسؤولة عن المعاناة الأخلاقية.function combine(arr, etalon = 10) {