أقل عدد من العمليات
درس 3 من 11
3أقل عدد من العمليات
مسألة «انسخ الكل وألصق» التي تتحوّل، بعد سطرين من التفكير، إلى تحليل عدد إلى عوامله الأولية.
ماذا تشاهد في الرسم: نسخ ثم لصق يضاعف H، ونسخ ثم لصقتان يجعلها ثلاثة أضعاف، فعدد العمليات هو مجموع العوامل الأولية: 2 + 3 = 5.
خارطة هذا الجزء
المفاهيم بالترتيب، اضغط أيًّا منها للقفز إليه:
طريقان إلى نفس الفكرة
عندك محرّر نصوص فيه حرف واحد، ولا تملك إلا زرّين: «انسخ الكل» و«ألصق». كم ضغطة أقل تحتاج لتصل إلى عدد معيّن من الحروف؟ تبدو مسألة عن الأزرار، لكن بعد قليل من التفكير تكتشف أنها عن تقسيم العدد إلى أرقام أصغر تضرب في بعضها.
الجواب مجموع العوامل الأولية للعدد n: كل عامل p يكلّف نسخة واحدة وp - 1 لصقة. تحسبه بالقسمة المتكررة من 2 حتى sqrt(n) في زمن O(sqrt n)، وتعيد 0 حين يكون n <= 1.
المتطلبات قبل البداية
باقي القسمة والقسمة الصحيحة
n % f يسأل «هل يقسم؟» وn // f يقسم ويحذف الكسر. العمليتان هما كل أدوات هذا الحل.
العدد الأولي والعوامل
العدد الأولي ما يقبل القسمة إلا على نفسه وعلى 1. و«تحليل إلى عوامل أولية» يعني كتابة العدد كضرب أعداد أولية: 12 = 2 × 2 × 3.
حلقة داخل حلقة بشرطين
الخارجية تمشي على العوامل المحتملة، والداخلية تستخرج نفس العامل مرارًا ما دام يقسم. فهم هذا التعشيش هو الحل.
مهارة إعادة الصياغة
أهم ما في هذا الجزء ليس الكود، بل الانتقال من «انسخ وألصق» إلى «حلّل إلى عوامل». خذ وقتك مع قسم المفاهيم قبل أن تكتب سطرًا.
المفاهيم الأساسية
المسألة: في ملف نصّي حرف واحد H. محرّرك يعرف عمليتين فقط: Copy All (انسخ كل الملف) وPaste (ألصق). المطلوب: أقل عدد عمليات للوصول إلى n حرفًا بالضبط.
1الملاحظة الأولى: الضرب لا الجمع
اللصق يضيف ما نسخته آخر مرة، لا حرفًا واحدًا. فلو كان عندك 3 أحرف ونسختها، فكل لصقة تضيف 3. يعني أنت لا تجمع، بل تضرب.
بالتحديد: لو كان في الملف x حرفًا ونسخت ثم ألصقت k - 1 مرة، صار عندك x · k حرفًا، وكلّفك ذلك k عملية (نسخة واحدة + k - 1 لصقات).
k يكلّف k عملية بالضبط. لا أقل ولا أكثر. من هذه الجملة الواحدة تنبني كل بقية الحل.2الملاحظة الثانية: المسألة صارت تحليلًا إلى عوامل
بما أننا نبدأ من 1 ونضرب كل مرة، فالوصول إلى n يعني تجزئته إلى عوامل: n = k₁ × k₂ × … × kₘ. والتكلفة هي مجموع هذه العوامل: k₁ + k₂ + … + kₘ.
فالسؤال صار: أي تجزئة لـ n تعطي أصغر مجموع؟
3الملاحظة الثالثة: الأولية دائمًا أفضل
لنفترض أن أحد عواملك مركّب، أي c = a × b حيث a وb كلاهما ≥ 2. أيهما أرخص: ضربة واحدة بـ a·b، أم ضربتان بـ a ثم b؟
| المقارنة | التكلفة |
|---|---|
ضربة واحدة في a × b | a · b |
ضربتان: في a ثم في b | a + b |
| الفرق | a·b − (a+b) = (a−1)(b−1) − 1 ≥ 0 عند a, b ≥ 2 |
فالتجزئة لا تكون أسوأ أبدًا، وتكون أفضل فعلًا عند a, b ≥ 3. استمر في التجزئة إلى أن تصل أعدادًا أولية لا تتجزّأ. النتيجة: الجواب هو مجموع العوامل الأولية لـ n بتكرارها.
4تحقّق سريع على أمثلة
n | التحليل | المجموع = الجواب | الطريق |
|---|---|---|---|
2 | 2 | 2 | انسخ، ألصق |
4 | 2 × 2 | 4 | ×2 ثم ×2 |
9 | 3 × 3 | 6 | ×3 ثم ×3 |
12 | 2 × 2 × 3 | 7 | ×2 ثم ×2 ثم ×3 |
13 | 13 | 13 | أولي، ما فيه اختصار |
16 | 2⁴ | 8 | أربع ضربات في 2 |
100 | 2 × 2 × 5 × 5 | 14 | ، |
5الحالات الحدّية و«المستحيل»
| المدخل | المخرج | لماذا |
|---|---|---|
n = 1 | 0 | الحرف موجود أصلًا، صفر عمليات |
n = 0 أو سالب | 0 | مستحيل الوصول، والنص يطلب 0 |
n أولي | n | ما فيه تجزئة، تنسخ مرة وتلصق n-1 مرة |
O(n log n) أو أسوأ، بينما التحليل إلى عوامل O(√n). لما تلاحظ أن المسألة رياضية، لا تحلها بالقوة الغاشمة.كيف يعمل؟
ثلاثة أشكال: مسار الكود، ثم الطريق الفعلي لـ n = 9 داخل المحرّر، ثم مقارنة الطرق المختلفة لـ n = 12.
شكل 6، مسار الكود: حلقة خارجية على العوامل المحتملة، وحلقة داخلية تستخلص نفس العامل ما دام يقسم.
شكل 7، الوصول إلى 9 حرفًا: نسخة + لصقتان (×3) ثم نسخة + لصقتان (×3) = 6 عمليات، وهو 3 + 3 بالضبط.
شكل 8، طرق مختلفة للوصول إلى 12 وتكلفة كل منها: التجزئة إلى أعداد أولية هي الأرخص، والضربة الواحدة الكبيرة هي الأغلى.
الحل خطوة بخطوة
الكود قصير، والفكرة هي الصعبة. كل مخرج تحت من تشغيل حقيقي.
الخطوة 1، الحل
#!/usr/bin/python3
"""0-minoperations"""
def minOperations(n):
"""Return the fewest Copy All / Paste operations needed to reach n H's."""
if not isinstance(n, int) or n <= 1:
return 0
operations = 0
factor = 2
while n > 1:
while n % factor == 0:
operations += factor
n //= factor
factor += 1
return operationsالخطوة 2، التشغيل
$ cat 0-main.py
#!/usr/bin/python3
minOperations = __import__('0-minoperations').minOperations
n = 4
print("Min # of operations to reach {} char: {}".format(n, minOperations(n)))
n = 12
print("Min # of operations to reach {} char: {}".format(n, minOperations(n)))
$ ./0-main.py
Min # of operations to reach 4 char: 4
Min # of operations to reach 12 char: 7الخطوة 3، جدول قيم كامل
>>> for n in [1, 2, 3, 4, 9, 12, 13, 16, 100, 625, 0, -4]: ... print(n, minOperations(n)) 1 0 2 2 3 3 4 4 9 6 12 7 13 13 16 8 100 14 625 20 0 0 -4 0
الخطوة 4، تتبّع n = 100 بالتفصيل
التحليل إلى عوامل، عاملًا بعامل
n = 100. نبدأ بـ operations = 0 وfactor = 2.
100 يقسم على 2؟ نعم. operations = 2 وn = 50.
يقسم مرة ثانية؟ نعم. operations = 4 وn = 25. يقسم ثالثة؟ 25 % 2 = 1، لا.
factor = 3. يقسم 25 على 3؟ لا. factor = 4.
يقسم 25 على 4؟ لا. factor = 5.
(ملاحظة: ما نحتاج نتأكد إن العامل أولي. العوامل المركّبة لن تقسم أبدًا، لأن عواملها الأولية أُزيلت قبلها.)
يقسم 25 على 5؟ نعم. operations = 9 وn = 5. مرة ثانية؟ نعم. operations = 14 وn = 1.
n = 1 فالحلقة تنتهي. الجواب 14 ✓
f فكل العوامل الأصغر أُزيلت تمامًا، فأي عدد مركّب (مثل 4 أو 6) لن يقسم n أبدًا، عوامله الأولية اختفت قبله. هذه نقطة أنيقة توفّر عليك دالة كاملة.factor * factor <= n، ثم لو بقي n > 1 في النهاية فهو عامل أولي تضيفه. هذا ينزّل التعقيد إلى O(√n). الحل أعلاه O(n) في أسوأ الحالات (عدد أولي كبير)، وهو مقبول لنطاق المشروع.اعتقاد شائع × الحقيقة
| الاعتقاد | الحقيقة |
|---|---|
| «هذه مسألة بحث، فأحتاج تجربة كل المسارات.» | هي مسألة رياضية بجواب مغلق: مجموع العوامل الأولية. البحث يعطي نفس الجواب بتكلفة أعلى بكثير. |
| «اللصق يضيف حرفًا واحدًا.» | اللصق يضيف كل ما نُسخ آخر مرة. هذه الملاحظة الواحدة هي بوابة الحل كله. |
«ضرب العدد في k يكلّف k - 1 عملية.» | يكلّف k: نسخة واحدة + k - 1 لصقة. نسيان النسخة هو أكثر خطأ حسابي في هذه المسألة. |
| «يجب أن أختار أكبر عامل أولًا لكي أقلّل الخطوات.» | عدد الخطوات ليس المطلوب، مجموع العوامل هو المطلوب. ترتيب العوامل لا يغيّر مجموعها. |
«n = 1 مستحيل فأرجع 0.» | ترجع 0 فعلًا، لكن ليس لأنه مستحيل: الحرف موجود أصلًا فما تحتاج أي عملية. فرق في الفهم لا في الكود. |
«أحتاج دالة is_prime.» | لا تحتاجها. المرور على العوامل بترتيب تصاعدي يضمن أن ما يقسم هو أولي دائمًا. |
أين نستخدمه فعليًا؟
التشفير
صعوبة تحليل عدد كبير إلى عوامله الأولية هي أساس RSA. نفس الحلقة التي كتبتها هنا لكن لعدد من 600 خانة هي المسألة التي يعتمد عليها نصف الإنترنت.
تقليل كلفة العمليات
نفس المنطق: لو كانت عملية مركّبة أغلى من عمليتين أصغر تؤدي نفس الشي، فجزّئها. هذه فكرة عامة في تحسين الأداء، لا في هذه المسألة وحدها.
تبسيط الكسور والنسب
القاسم المشترك الأكبر وتبسيط الكسور يقومان على نفس التحليل الذي كتبته.
إعادة صياغة المسائل
الدرس المنقول: قبل أن تكتب كودًا، اسأل «هل لهذي المسألة صيغة رياضية مغلقة؟» جواب نعم يختصر عليك ساعات.
جرّب بنفسك
وش minOperations(8) ولماذا؟
التحليل الأولي لـ 8 هو 2 × 2 × 2 والمجموع 6. الخيار الثالث يعطي نفس الرقم 6 لكن بتحليل غير أولي، صحيح بالمصادفة هنا (4+2 = 6)، لكن المنطق الصحيح هو الأولي دائمًا. الطريق فعلًا: ×2 ثم ×2 ثم ×2، أي ثلاث نسخات وثلاث لصقات.
بطاقات مراجعة سريعة
k؟k عملية بالضبط: نسخة واحدة وk - 1 لصقة.n بتكرارها.a + b <= a × b عند a, b >= 2، فالتجزئة لا تكون أسوأ أبدًا.minOperations(12) = ؟7، لأن 12 = 2×2×3 و2+2+3 = 7.n <= 1؟0، إمّا لأن الحرف موجود أصلًا (n=1) أو لأن الوصول مستحيل.is_prime؟تحقّق من فهمك
1. اشرح بجملة واحدة لماذا minOperations(9) == 6 وليس 9.
لأن 9 = 3×3، فنضرب في 3 مرتين بتكلفة 3+3 = 6، بدل ضربة واحدة في 9 بتكلفة 9. التجزئة توفّر 3 عمليات.
2. أحدهم كتب operations += factor - 1. أين الخطأ؟
نسي النسخة. ضرب العدد في factor يحتاج نسخة واحدة وfactor-1 لصقة، فالمجموع factor لا factor-1. هذا الخطأ يعطي جوابًا أقل بمقدار عدد العوامل.
3. (اكتشف الخطأ) الحل يعمل لكن يعلّق عند n أولي كبير مثل 999983. ما السبب؟
الحلقة الخارجية تزيد factor من 2 إلى n نفسه، أي حوالي مليون دورة. الإصلاح: حدّها بـ factor * factor <= n ثم أضف n المتبقي إن كان أكبر من 1، فيصير O(√n).
4. هل ترتيب الضرب يغيّر التكلفة؟ (×3 ثم ×2) أم (×2 ثم ×3) لـ n = 6؟
لا يغيّر: 3+2 = 2+3 = 5. الجمع تبديلي، فالتكلفة تعتمد على مجموعة العوامل لا على ترتيبها. لكن محتوى الملف في المنتصف يختلف (3 أحرف أو 2).
5. (قرار) لو كان المحرّر يعرف عملية ثالثة «Paste ×2» بتكلفة عملية واحدة. هل يتغيّر الحل؟
نعم جوهريًا، ولم تبقَ المسألة تحليلًا إلى عوامل. صارت كل ضربة في k تكلّف أقل، فالموازنة تتغيّر وتحتاج برمجة ديناميكية أو تحليلًا جديدًا. الدرس: الحل المغلق مشروط بقواعد المسألة بالحرف، وتغيير قاعدة واحدة قد يهدمه.
مصادر هذا الدرس
مرتّبة بالنوع. ابدأ بالتوثيق الرسمي إذا تبي المرجع الدقيق، وبالمقال أو الفيديو إذا تبي الشرح أولًا.
مقالات2
خلّصت الدرس؟
سجّل الدخول ليُحفظ تقدّمك.