من المسألة إلى الخوارزمية

ملخص

لا يحتوي هذا الدرس على شيفرة، وليس ذلك سهوًا: فالخوارزمية تسبق البرنامج، ومن لا يعرف أن يصف بدقة ما ينبغي فعله لن يعرف أن يقوله بلغة C++ أيضًا. نتعلّم أولًا تحديد مواصفات مسألة، أي التصريح بالبيانات التي تتلقّاها، وبالنتيجة التي يجب أن تُخرجها، وبالعلاقة التي تربط بينهما، ونبيّن أن الصياغة الواحدة تقبل مواصفات مختلفة. ثم تُعرَّف الخوارزمية بأنها إجراء محدود ودقيق وعامّ، وتُكتب في خطوات مرقّمة خوارزمية القسمة بالطرح المتتالي. ونتعلّم تتبّع خوارزمية يدويًّا بجدول التتبع، الذي سيكون طوال الدورة الأداة الأولى للفهم وللتنقيح. وتُعرض الطرق الثلاث لضمّ الخطوات (التسلسل والقرار والتكرار)، التي تُكتب بها كل خوارزمية، ونتعلّم أن نبرهن على أن التكرار يتوقف بكمية تتناقص في كل جولة ولا يمكن أن تنخفض بلا نهاية.

أهداف التعلم

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

ما المسألة الحاسوبية

المسألة الحاسوبية علاقة بين صنفين من البيانات: ما يُتلقّى، ويُسمّى المدخلات، وما يجب أن يُسلَّم، ويُسمّى المخرجات. وحلّها لا يعني الحصول على جواب لحالة واحدة، بل امتلاك طريقة تُنتج، لكل مدخلات مقبولة، مخرجات تحقق العلاقة. «كم يساوي 17 مقسومًا على 5؟» سؤال؛ أما «بمعلومية عددين صحيحين، أوجد خارج قسمتهما وباقيها» فمسألة، لأنها تتحدث عن جميع أزواج الأعداد الصحيحة دفعة واحدة.

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

مثالأكبر ثلاثة أعداد

الصياغة الجارية: «أوجد أكبر ثلاثة أعداد». المواصفات:

المدخلات: ثلاثة أعداد $x$ ، $y$ ، $z$ (صحيحة أو عشرية، بلا شرط آخر).
المخرجات: عدد $m$ .
العلاقة: $m$ أحد المعطيات الثلاثة، ولا أحد منها أكبر من $m$ ؛ أي $m \geq x$ و $m \geq y$ و $m \geq z$ .

لا تقول العلاقة «أكبر الثلاثة»، وهو بالضبط ما أردنا تدقيقه، بل تضع شرطين قابلين للتحقق. يشترط الأول أن يكون $m$ أحد المعطيات (ولولاه لحقق العدد 1000 الشرط الثاني لكل مدخلات تقريبًا)؛ ويشترط الثاني ألا يتجاوزه أيّ منها. وتحسم المواصفات عرضًا شكًّا تركته الصياغة مفتوحًا: إذا تساوى معطيان في القيمة العظمى، كما في $(4, 9, 9)$ ، فالمخرجات $9$ ، ولا خطأ في ذلك.

تقبل الصياغة الواحدة مواصفات مختلفة، والاختيار بينها قرار لا سهو. وأكثر الحالات تعليمًا حالة القسمة الصحيحة. فللعددين الصحيحين $a \geq 0$ و $b > 0$ يتفق الجميع: خارج القسمة $q$ والباقي $r$ هما العددان الصحيحان الوحيدان اللذان يحققان

a = b \cdot q + r, \quad 0 \leq r < b

وهكذا، لـ $a = 17$ و $b = 5$ يكون $q = 3$ و $r = 2$ ، لأن $17 = 5 \cdot 3 + 2$ . لكن الصياغة «اقسم عددين صحيحين» لا تقول ما العمل إذا كان $a$ سالبًا، والسؤال ليس عبثًا: فلـ $a = -7$ و $b = 2$ جوابان معقولان.

مثالمواصفتان للقسمة على مقسوم سالب

المواصفات الأولى: الباقي ليس سالبًا أبدًا، $0 \leq r < b$ . عندئذ $-7 = 2 \cdot (-4) + 1$ ، والمخرجات $q = -4$ ، $r = 1$ . وهي التي تُدرس في الرياضيات، في درس «قابلية القسمة والقسمة مع الباقي» من دورة الجبر والهندسة 1.

المواصفات الثانية: خارج القسمة هو ناتج القسمة بالأعداد العشرية بعد إسقاط جزئه العشري، أي مقرّبًا نحو الصفر؛ والباقي هو ما ينقص، وإشارته إشارة المقسوم. عندئذ يُبتر $-7 / 2 = -3{,}5$ إلى $-3$ ، و $-7 = 2 \cdot (-3) + (-1)$ : والمخرجات $q = -3$ ، $r = -1$ .

كلتاهما تحقق $a = b \cdot q + r$ ؛ وتختلفان في الشرط المفروض على الباقي. ليست أيّ منهما خطأ، لكن برنامجًا يستعمل إحداهما ظانًّا أنه يستعمل الأخرى سيعطي نتائج خاطئة مع الأعداد السالبة. ولنستبق معلومة: تعتمد C++ الثانية، كما سنرى في درس العمليات الحسابية؛ ومن ينتظر الأولى ستفاجئه.

وثمة خيار ثالث، هو الأكثر شيوعًا في الممارسة: استبعاد الحالة بالشرط المسبق. فإذا اشترطت المواصفات $a \geq 0$ ، اختفت مشكلة الأعداد السالبة، لا لأنها حُلّت، بل لأن من يستعمل الحلّ التزم بألا يطرحها. أما ما لا يجوز فهو ترك المسألة دون حسم. وللسبب نفسه تشترط المواصفات $b > 0$ : فمع $b = 0$ لا يوجد $q$ و $r$ يحققان العلاقة، ويجب أن ينصّ العقد على ذلك.

ومن الأخطاء الشائعة تحديد المواصفات بمثال: «مخرجات 17 و5 هي 3 و2». المثال يوضّح لكنه لا يحدّد المواصفات، لأنه لا يقول ما يحدث مع سائر المدخلات؛ فعدد لا نهائي من العلاقات المختلفة يتطابق في حالة واحدة. تُكتب المواصفات شرطًا عامًّا، وتصلح الأمثلة بعد ذلك للتحقق منها.

الخوارزميات

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

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

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

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

تُكتب خوارزميات هذه الدورة أولًا في خطوات مرقّمة، بالعربية، مع بعض الاصطلاحات. البيانات التي تتغير أثناء الخوارزمية تُسمّى بحروف أو كلمات، مثل $q$ أو $r$ ، وتُدعى المتغيرات. ونكتب « $r$ يأخذ القيمة $r - b$ » لنقول إن $r - b$ تُحسب بالقيمة الحالية لـ $r$ وإن الناتج يصير القيمة الجديدة لـ $r$ ؛ وتضيع القيمة السابقة. وفي الكتابة المختصرة، المستعملة عند تدوين الملاحظات، تُكتب التعليمة نفسها بسهم نحو اليسار، وهو على لوحة المفاتيح r <- r - b. وتُنفَّذ التعليمات بترتيب أرقامها، ما لم تنصّ إحداها على غير ذلك.

مثالالقسمة بالطرح المتتالي

المسألة هي التي حُدّدت مواصفاتها في القسم السابق: المدخلات، عددان صحيحان $a \geq 0$ و $b > 0$ ؛ والمخرجات، عددان صحيحان $q$ و $r$ بحيث $a = b \cdot q + r$ و $0 \leq r < b$ . والفكرة فكرة التوزيع: تُطرح من $a$ مجموعات من $b$ ما دام ذلك ممكنًا، وتُعدّ المجموعات المطروحة، وما يتبقّى هو الباقي.

$q$ يأخذ القيمة $0$ ، و $r$ يأخذ القيمة $a$ .
ما دام $r \geq b$ متحققًا، كرّر الخطوتين 3 و4؛ وحين يكفّ عن التحقق، تابع في الخطوة 5.
$r$ يأخذ القيمة $r - b$ .
$q$ يأخذ القيمة $q + 1$ ؛ عُد إلى الخطوة 2.
أخرج $q$ و $r$ ، وتوقّف.

الخطوة 2 سؤال يُطرح في كل مرة: قبل الجولة الأولى وبعد كل جولة. والخطوتان 3 و4 تشكّلان جسم التكرار، أي ما يتكرر. ولا شيء متروك لتقدير المنفّذ: في كل لحظة توجد تعليمة لاحقة واحدة.

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

ويحسن، أخيرًا، أن نفصل الخوارزمية عن كتابتها. فخوارزمية القسمة بالطرح هي نفسها سواء كُتبت بالعربية، أم في مخطط، أم بلغة C++ أم بأيّ لغة برمجة أخرى: ما يعرّفها هو متتالية العمليات، لا الكلمات. والبرنامج كتابة خوارزمية بلغة تستطيع آلة أن تنفّذها، وسيشرح درس البرامج والمترجمات ولغة C++ كيف يجري هذا التنفيذ. وإذا كان الأمر كذلك، فقد يكون البرنامج خاطئًا على وجهين مختلفين تمامًا: لأن الخوارزمية غير صحيحة، وعندئذ لا تنقذها أيّ لغة، أو لأن الخوارزمية صحيحة لكنها كُتبت خطأً. والتمييز بين الحالتين نصف عمل التنقيح، ولذلك تكتب الدورة الخوارزمية أولًا دائمًا.

تتبّع خوارزمية يدويًّا

لا تكفي قراءة خوارزمية لمعرفة ما تفعله؛ بل يجب تنفيذها. وتتبّعها يدويًّا، كما تفعل الآلة، دون تخطّي خطوات ولا تخمين نتائج، هو أنفع مهارات المبرمج: به تُختبر الخوارزمية قبل كتابتها، ويُتنبأ بمخرجات برنامج قبل تشغيله، ويُعثر على الخطأ في برنامج يخفق.

الأداة هي جدول التتبع: عمود لرقم الخطوة المنفَّذة، وعمود لكل متغير، وإن لزم عمود للشروط التي تُحسب قيمتها؛ وصفّ لكل خطوة منفَّذة. في كل صفّ تُدوَّن القيمة الجديدة للمتغير الذي تغيّر في تلك الخطوة ويُترك فارغًا ما لم يتغير، بحيث تكون القيمة الحالية لمتغير هي آخر قيمة مكتوبة في عموده. وتُدوَّن الشروط مع نتيجتها.

مثالتتبّع قسمة 17 على 5

نتتبّع القسمة بالطرح المتتالي مع $a = 17$ و $b = 5$ . يشير سهم الشكل إلى الخطوة التي نُفّذت للتوّ؛ ويذكّر الخط المنقّط بأن الخطوة 4 تعود إلى الخطوة 2.

البرهان

$(q, r) = (0, 17)$
الخطوة 1: تُعطى القيم الابتدائية. المدخلات تحقق الشرط المسبق، لأن $17 \geq 0$ و $5 > 0$ .
$(q, r) = (1, 12)$
الجولة الأولى. في الخطوة 2 يُتحقق من أن $17 \geq 5$ ، فيُنفَّذ الجسم: تطرح الخطوة 3 مجموعة من خمسة وتعدّها الخطوة 4.
$(q, r) = (2, 7)$
الجولة الثانية: $12 \geq 5$ ، ويُنفَّذ الجسم مرة أخرى.
$(q, r) = (3, 2)$
الجولة الثالثة: $7 \geq 5$ ، ويُنفَّذ الجسم مرة أخرى.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
في الخطوة 2 يخفق الشرط، لأن $2 < 5$ : تتابع الخوارزمية في الخطوة 5 وتُخرج $q = 3$ و $r = 2$ . والمخرجات تحقق الشرط اللاحق.

للجدول الكامل اثنا عشر صفًّا: الخطوة 1، وثلاث جولات في كل منها ثلاثة صفوف (الخطوات 2 و3 و4)، والتحقق الذي يخفق، والإخراج.

ملاحظتان على الجدول. الأولى: عدد الجولات يساوي خارج القسمة، $3$ ، والخطوة 2 نُفّذت مرة أكثر من الجسم، $4$ مرات؛ ويحدث ذلك دائمًا في تكرار من هذا الشكل، لأن التحقق الأخير هو الذي يخفق. الثانية: يُظهر التتبع شيئًا لا يقوله نصّ الخوارزمية من النظرة الأولى؛ فإذا كان $a < b$ ، مثلًا $a = 3$ و $b = 5$ ، يخفق الشرط من المرة الأولى، ولا يُنفَّذ الجسم ولا مرة، والمخرجات $q = 0$ ، $r = 3$ ، وهي صحيحة، لأن $3 = 5 \cdot 0 + 3$ . ونسيان الحالة التي لا يُنفَّذ فيها التكرار من أكثر الأخطاء شيوعًا في تصميم الخوارزميات، والتتبع بمدخلات صغيرة يكشفه.

تتبّع حالة واحدة لا يبرهن على أن الخوارزمية صحيحة: إنه يختبر حالة واحدة. لكن تتبّعًا حسن الاختيار (حالة عادية، وحالة حدّية، والحالة التي لا يُنفَّذ فيها التكرار) يكشف معظم الأخطاء، والتتبّع الذي يخفق يدلّ على موضعها. وسيعلّم درس تصميم حلقات صحيحة الانتقال من الحالات إلى البرهان.

التسلسل والقرار والتكرار

إذا نظرنا عن قرب، وجدنا الخوارزميات تُبنى من قطع قليلة جدًّا. فهناك تعليمات أوّلية (إعطاء قيمة لمتغير، إخراج نتيجة) وثلاث طرق لضمّها.

التسلسل: تعليمة بعد أخرى، بالترتيب. الخطوتان 3 و4 من القسمة تسلسل: أولًا يُطرح، ثم يُعدّ.
القرار: بحسب تحقق شرط أو عدم تحققه، يُنفَّذ جزء أو آخر (أو جزء أو لا شيء). «إذا كان $y > m$ ، يأخذ $m$ القيمة $y$ » قرار.
التكرار: ما دام شرط متحققًا، يُنفَّذ جزء مرة بعد مرة. الخطوة 2 من القسمة، مع جسمها، تكرار.

لكل شكل مدخل واحد ومخرج واحد، ويمكن أن يكون باطنه بدوره أيًّا من الثلاثة: فجسم التكرار قد يحوي قرارات، وفرع القرار قد يحوي تكرارًا، وهلمّ جرًّا. وإذا كان الأمر كذلك، فبالأشكال الثلاثة تُبنى خوارزميات من أيّ درجة تعقيد، كما يُبنى أيّ صرح بقطع قليلة يتداخل بعضها في بعض. أما أنها تكفي للتعبير عن كل خوارزمية فنتيجة معروفة في نظرية البرمجة (برهنها كورادو بوم وجوزيبي ياكوبيني سنة 1966)؛ ولا نبرهنها هنا، لكن الدورة كلها تؤكدها: فالبرامج التي ستُكتب فيها، مهما طالت، لن تستعمل غير هذه الأشكال الثلاثة، مكتوبة بلغة C++ على هيئة if للقرار وwhile أو for للتكرار، في درسَي القرارات والحلقات.

ومن الترميزات المفيدة لرؤية شكل خوارزمية المخطط الانسيابي: كل تعليمة مستطيل، وكل شرط معيّن له مخرجان (متحقق، ويرمز له الشكل بـ $1$ ، وغير متحقق، $0$ )، والأسهم تبيّن أيّ خطوة هي اللاحقة. إنه ترميز لا غاية: يصلح للإحاطة بخوارزمية صغيرة بنظرة واحدة، لكنه لا يتّسع، ولا أحد يكتب برنامجًا كبيرًا برسمه.

مثالثلاثة أشكال وتركيبها

يرسم الشكل الأشكال الثلاثة بتعليمتين عامّتين $A$ و $B$ وشرط $c$ ، ثم يركّبها في مخطط القسمة بالطرح المتتالي.

البرهان

$A ; B$
التسلسل: تُنفَّذ $A$ ثم $B$ ؛ وهناك مدخل واحد ومخرج واحد.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
القرار: إذا تحقق $c$ ، تُنفَّذ $A$ ؛ وإلا، $B$ . ويلتقي الفرعان في مخرج واحد.
$c, A, c, A, \ldots, c$
التكرار: يُحسب $c$ ؛ فإن تحقق، تُنفَّذ $A$ ويُحسب $c$ من جديد؛ وإلا، يُخرج من التكرار. ويُحسب الشرط مرة أكثر من الجسم.
$a = b \cdot q + r, \quad 0 \leq r < b$
التركيب: القسمة بالطرح المتتالي تسلسل (القيم الابتدائية، التكرار، الإخراج) جسمُ تكراره تسلسلٌ آخر (اطرح، عُدّ).

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

هل يتوقف؟

المحدودية جزء من تعريف الخوارزمية، والتكرار هو الموضع الوحيد الذي يمكن أن تضيع فيه: فالتسلسل المؤلف من خمس خطوات ينفّذ خمس خطوات، والقرار ينفّذ أحد فرعيه؛ أما التكرار فينفّذ جسمه بعدد مرات تحقق الشرط، ولا شيء يضمن مسبقًا أن يكفّ عن التحقق.

للبرهنة على أن تكرارًا يتوقف، يُبحث عن كمية، محسوبة من المتغيرات، تحقق شرطين: أن تكون عددًا طبيعيًّا (صحيحًا غير سالب) ما دام التكرار مستمرًّا، وأن تتناقص تناقصًا تامًّا في كل جولة. وإذا كان الأمر كذلك، توقّف التكرار: فالمتتالية المتناقصة تناقصًا تامًّا من الأعداد الطبيعية لا يمكن أن تكون لانهائية، لأن كل جولة تُنقصها بواحد على الأقل، ومن عدد طبيعي $n$ لا يوجد أكثر من $n$ درجة حتى الصفر. وتُسمّى هذه الكمية المتغاير أو دالة الحدّ، وسيستعملها درس تصميم حلقات صحيحة استعمالًا منهجيًّا.

مثالمتغاير القسمة بالطرح

في القسمة بالطرح المتتالي، المتغاير هو $r$ . ما دام التكرار مستمرًّا، فإن $r \geq b > 0$ ، فيكون $r$ عددًا طبيعيًّا. وفي كل جولة يأخذ $r$ القيمة $r - b$ ، ولأن $b > 0$ (الشرط المسبق)، فالقيمة الجديدة أصغر تمامًا. إذن يتوقف التكرار، ويفعل ذلك بعد $a$ جولة على الأكثر (بل بعد $q$ جولة بالضبط، أي خارج القسمة).

لاحظ أين استُعمل الشرط المسبق $b > 0$ . إذا نُفّذت الخوارزمية مع $b = 0$ ، تُبقي الخطوة 3 $r$ على حاله، ويتحقق الشرط $r \geq 0$ دائمًا ولا يتوقف التكرار أبدًا: ليست الخوارزمية خاطئة، بل أُعطيت مدخلات كان العقد يستبعدها. ولو كان $b$ سالبًا، لازداد $r$ في كل جولة. الشرط المسبق ليس زينة: إنه بالضبط ما يلزم ليصحّ الاستدلال.

شرطا المتغاير ضروريان، ومن السهل الخطأ في أيّ منهما. لنتأمل هذا الإجراء، الذي يُراد به تقرير ما إذا كان عدد طبيعي $n$ زوجيًّا: «ما دام $n \neq 0$ ، يأخذ $n$ القيمة $n - 2$ ؛ فإن بُلغ الصفر، كان $n$ زوجيًّا». الكمية $n$ تتناقص في كل جولة، ومع ذلك لا يتوقف الإجراء إذا كان $n$ فرديًّا: فمع $n = 5$ يمرّ بـ $3$ ، $1$ ، $-1$ ، $-3$ ، والشرط $n \neq 0$ لا يخفق أبدًا. ما لا يتحقق هو الشرط الآخر: $n$ يكفّ عن أن يكون طبيعيًّا، لأن شرط التكرار لا يمنعه من النزول تحت الصفر. ويقوم التصحيح على التكرار ما دام $n \geq 2$ والتقرير في النهاية بحسب القيمة الباقية، $0$ أو $1$ ؛ فالآن $n$ طبيعي في كل جولة، لأن الطرح لا يجري إلا حين $n \geq 2$ ، وهو يتناقص: فيتوقف الإجراء.

ليس تقرير ما إذا كان تكرار يتوقف سهلًا دائمًا. مثال شهير: انطلاقًا من عدد طبيعي $n \geq 1$ ، ما دام $n \neq 1$ ، إذا كان $n$ زوجيًّا يُقسم على اثنين، وإذا كان فرديًّا يُستبدل به $3n + 1$ . مع $n = 6$ تكون المتتالية $6, 3, 10, 5, 16, 8, 4, 2, 1$ ، وتتوقف. لم يجد أحد $n$ لا تتوقف عنده، وقد تُحقِّق من ذلك بالحواسيب لكميات هائلة من القيم؛ لكن أحدًا لم يتمكن من البرهنة على أنها تتوقف دائمًا: إنها حدسية كولاتز، وهي مسألة مفتوحة في الرياضيات. ولا تُعرف أيّ كمية تتناقص في كل جولة. والعبرة لمن يبرمج متواضعة وثابتة: الخوارزمية التي لا نعرف كيف نبرهن على توقفها لم تكتمل.

أخطاء شائعة

خطوات ملتبسة. «كرّر مرات عدة»، «حتى يصير جيدًا»، «خذ عددًا مناسبًا». يجب أن تكون كل خطوة قابلة للتنفيذ دون فهم المسألة؛ وإلا فهي مكتوبة كتابة سيئة.
نسيان الحالة التي لا يُنفَّذ فيها التكرار. كل تكرار شرطه في بدايته قد ينفّذ جسمه صفر مرة. ويجب أن نسأل دائمًا ماذا تُخرج الخوارزمية في هذه الحالة، والتتبع بمدخلات دنيا يجيب عن ذلك.
تحديد المواصفات بمثال. «لـ 17 و5 تعطي 3 و2» ليست مواصفات؛ فالعلاقة تُكتب شرطًا عامًّا، والمثال يوضّحها.
الخلط بين الخوارزمية وبرنامجها. البرنامج الذي يخفق قد تكون خوارزميته خاطئة أو كتابتها خاطئة. ومن لم يكتب الخوارزمية أولًا لا يعرف أيّ الأمرين يبحث عنه.
افتراض التوقف دون برهان. لا يكفي أن تتناقص كمية: بل يجب أيضًا أن تكون طبيعية ما دام التكرار مستمرًّا.

مسائل محلولة

مسألة محلولة 1أكبر ثلاثة أعداد، مع التساوي

اكتب خوارزمية تحقق مواصفات أكبر ثلاثة أعداد من القسم الأول، وتتبّعها يدويًّا للمدخلات $(7, 2, 5)$ و $(4, 9, 9)$ .

الحل

$m = x$
الفكرة: تُجتاز المدخلات مع حفظ أكبر ما رُئي حتى الآن في متغير $m$ . الخطوة الأولى: $m$ يأخذ القيمة $x$ . وبعدها يكون $m$ أكبر المعطيات المرئية، وهي $x$ وحده.
$m = \max(x, y, z)$
الخطوة الثانية: إذا كان $y > m$ ، يأخذ $m$ القيمة $y$ . الخطوة الثالثة: إذا كان $z > m$ ، يأخذ $m$ القيمة $z$ . الخطوة الرابعة: أخرج $m$ . هي ثلاث تعليمات في تسلسل، اثنتان منها قراران بلا فرع بديل.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
التتبّع لـ $(7, 2, 5)$ : بعد الخطوة الأولى $m = 7$ ؛ وفي الثانية، $2 > 7$ خاطئة ولا يتغير $m$ ؛ وفي الثالثة، $5 > 7$ خاطئة ولا يتغير $m$ . ويُخرج $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
التتبّع لـ $(4, 9, 9)$ : بعد الخطوة الأولى $m = 4$ ؛ وفي الثانية، $9 > 4$ فيصير $m$ مساويًا لـ $9$ ؛ وفي الثالثة، $9 > 9$ خاطئة ولا يتغير $m$ . ويُخرج $9$ ، وهو صحيح: فالتساوي لا يحتاج إلى معالجة خاصة.
$m \geq x, \quad m \geq y, \quad m \geq z$
التبرير: بعد كل خطوة، $m$ أحد المعطيات المرئية ولا يتجاوزه أيّ منها. وهذا صحيح بعد الخطوة الأولى، وكل قرار يحفظه: إذا كان المعطى الجديد أكبر، صار هو $m$ ؛ وإلا فهو لا يتجاوز $m$ . وفي النهاية رُئيت الثلاثة كلها، و $m$ يحقق الشرط اللاحق.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
لو كُتب $y \geq m$ بدل $y > m$ ، لكانت النتيجة نفسها، لأنه في حالة التساوي تُسند قيمة مساوية. ويكون للاختيار بين $>$ و $\geq$ أهمية لو طُلب أيضًا موضع القيمة العظمى: مع $>$ يُخرج أول المواضع المتساوية، ومع $\geq$ آخرها، الذي تسمّيه الصيغة $p$ .

مسألة محلولة 2السنة الكبيسة، مصحَّحة بمثال مضاد

في التقويم الغريغوري، تكون السنة كبيسة إذا قبلت القسمة على $4$ ، باستثناء ما يقبل القسمة على $100$ ، فهو لا يكون كبيسًا إلا إذا قبل القسمة أيضًا على $400$ . يقترح طالب الخوارزمية «إذا قبلت السنة القسمة على $4$ ، أخرج نعم؛ وإلا أخرج لا». أوجد سنة تخفق فيها، واكتب خوارزمية صحيحة مع مواصفاتها.

الحل

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
المواصفات. المدخلات: عدد صحيح $n \geq 1583$ (يسري التقويم الغريغوري منذ أكتوبر 1582). المخرجات: نعم أو لا. العلاقة: تكون المخرجات نعم بالضبط عندما يقبل $n$ القسمة على $4$ ولا يقبلها على $100$ ، أو يقبل القسمة على $400$ .
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
تصيب الخوارزمية المقترحة في أغلب السنين، ولذلك تبدو صحيحة. ولدحضها تكفي سنة تقبل القسمة على $100$ ولا تقبلها على $400$ : $1900$ يقبل القسمة على $4$ ، والخوارزمية تقول نعم؛ لكن $1900$ لم تكن كبيسة.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
الخوارزمية المصحَّحة، في ثلاثة قرارات متسلسلة. الخطوة 1: إذا قبل $n$ القسمة على $400$ ، أخرج نعم وتوقّف. الخطوة 2: إذا قبل $n$ القسمة على $100$ ، أخرج لا وتوقّف. الخطوة 3: إذا قبل $n$ القسمة على $4$ ، أخرج نعم؛ وإلا أخرج لا.
$2000, \quad 1900, \quad 2024, \quad 2023$
ترتيب الأسئلة جوهري: فهي تسير من القاعدة الأخصّ إلى الأعمّ. ولو سُئل أولًا عن $4$ ، لنالت السنة $1900$ نعم قبل بلوغ الاستثناء. التتبّع لأربع سنوات، واحدة من كل حالة: $2000$ (الخطوة 1: نعم)، $1900$ (الخطوة 2: لا)، $2024$ (الخطوة 3: نعم)، $2023$ (الخطوة 3: لا).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
ليس الدرس المستفاد خاصًّا بالتقاويم: فالخوارزمية تُدحض بمثال مضاد واحد، والأمثلة المضادة تُطلب عند حدود القواعد، لا في الحالات العادية. وما كانت التجربة على $2024$ و $2020$ و $2016$ لتكشف شيئًا.

مسألة محلولة 3كم جولة تقوم بها القسمة بالطرح

تتبّع يدويًّا القسمة بالطرح المتتالي مع $a = 20$ و $b = 5$ ، ومع $a = 0$ و $b = 7$ . ثم برهن على أن الخوارزمية تتوقف، لكل مدخلات مقبولة، بعد $q$ جولة بالضبط وأن مخرجاتها تحقق الشرط اللاحق.

الحل

$20 = 5 \cdot 4 + 0$
التتبّع مع $a = 20$ ، $b = 5$ : يمرّ $r$ بـ $20$ ، $15$ ، $10$ ، $5$ ، $0$ ، ويمرّ $q$ بـ $0$ ، $1$ ، $2$ ، $3$ ، $4$ . التحقق الخامس، $0 \geq 5$ ، يخفق. المخرجات: $q = 4$ ، $r = 0$ . والحالة الحدّية هنا القسمة التامة: تجري الجولة الرابعة لأن $5 \geq 5$ ، ولذلك يجب أن يكون الشرط $\geq$ لا $>$ .
$0 = 7 \cdot 0 + 0$
التتبّع مع $a = 0$ ، $b = 7$ : التحقق الأول، $0 \geq 7$ ، يخفق؛ ولا يُنفَّذ الجسم ولا مرة. المخرجات: $q = 0$ ، $r = 0$ ، وهي صحيحة.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
علاقة تبقى محفوظة. قبل الجولة الأولى، $b \cdot q + r = b \cdot 0 + a = a$ . وفي كل جولة ينقص $r$ بمقدار $b$ ويزيد $q$ بمقدار $1$ ، فلا تتغير $b \cdot q + r$ . إذن تصحّ المساواة بعد كل جولة.
$r_0 > r_1 > r_2 > \cdots \geq 0$
التوقف. ما دام التكرار مستمرًّا، $r \geq b > 0$ ، و $r$ عدد طبيعي؛ وفي كل جولة ينقص بمقدار $b \geq 1$ . والمتتالية المتناقصة تناقصًا تامًّا من الأعداد الطبيعية منتهية: فيتوقف التكرار.
$a = b \cdot q + r, \quad 0 \leq r < b$
عند التوقف، أخفق الشرط: $r < b$ . وفوق ذلك $r \geq 0$ ، لأن $b$ لا يُطرح إلا حين $r \geq b$ . ومع العلاقة المحفوظة، تحقق المخرجات الشرط اللاحق؛ ولأن $q$ يعدّ الجولات، فعدد الجولات هو خارج القسمة.

تمارين على الشبكة

تمرين 1عدّ الجولات

تتبّع يدويًّا الخوارزمية الآتية واكتب في الخانة القيمة التي تُخرجها، الرقم وحده.

$n$ يأخذ القيمة $29$ ، و $k$ يأخذ القيمة $0$ .
ما دام $n > 1$ متحققًا، كرّر الخطوتين 3 و4؛ وحين يكفّ عن التحقق، تابع في الخطوة 5.
إذا كان $n$ زوجيًّا، يأخذ $n$ القيمة $n / 2$ ؛ وإذا كان فرديًّا، يأخذ $n$ القيمة $n + 1$ .
$k$ يأخذ القيمة $k + 1$ ؛ عُد إلى الخطوة 2.
أخرج $k$ .

يفحص المتصفح إجابتك فورًا، دون تقييمها.

اكتب إجابتك هنا

تلميح

ارسم الجدول: يمرّ $n$ من $29$ إلى $30$ في الجولة الأولى. احسب جولة لكل تغيّر في $n$ ، حتى تصير قيمة $n$ هي $1$ .

تمرين 2الشرط الناقص

الخوارزمية الآتية، المكتوبة بالصيغة المختصرة، يجب أن تحسب خارج القسمة والباقي بالطرح المتتالي، لكن ينقصها شرط التكرار. استبدل بسطر الشرطات السفلية الشرط الصحيح، دون تغيير أيّ شيء آخر.

يفحص المتصفح إجابتك فورًا، دون تقييمها.

اكتب إجابتك هنا

تلميح

تتبّع الخوارزمية يدويًّا مع $a = 10$ و $b = 5$ : يجب أن تجري الجولة الثانية ولو كان الباقي يساوي $5$ بالضبط.

مسائل مقترحة

لكل مسألة تلميح يحسن ألا يُفتح إلا بعد المحاولة، وجواب يظهر بعد فتح التلميح.

مسألة مقترحة 1مواصفات ترتيب ثلاثة أعداد

اكتب مواصفات المسألة «رتّب ثلاثة أعداد» (المدخلات والمخرجات والعلاقة) وبيّن القرارات التي تُلزم باتخاذها ولم تكن الصياغة تتخذها. ثم تحقق من أن المواصفات ترفض هذين المخرجين للمدخلات $(5, 2, 5)$ : $(2, 5, 6)$ و $(2, 5, 5, 5)$ ، وأنها تقبل $(2, 5, 5)$ .

تلميح

قد لا يكون لمخرجات «مرتّبة» أيّ صلة بالمدخلات. ما الشرط الذي يربط أعداد المخرجات بأعداد المدخلات، بما فيها المكرّرة؟ تصاعديًّا أم تنازليًّا؟ ترتيبًا تامًّا أم لا؟

الإجابة

المدخلات: ثلاثة أعداد $x$ ، $y$ ، $z$ . المخرجات: ثلاثة أعداد $u$ ، $v$ ، $w$ . العلاقة: $u \leq v \leq w$ ، و $(u, v, w)$ إعادة ترتيب لـ $(x, y, z)$ ، أي تحتوي القيم نفسها بالتكرارات نفسها. قرارات لم تكن الصياغة تتخذها: الاتجاه (هنا، من الأصغر إلى الأكبر)؛ وأن الترتيب ليس تامًّا ( $\leq$ لا $<$ ، لأن الترتيب التام مستحيل مع القيم المكرّرة)؛ وأن المخرجات يجب أن تكون إعادة ترتيب. $(2, 5, 6)$ مرتّبة لكنها تحتوي $6$ لم يكن موجودًا؛ و $(2, 5, 5, 5)$ فيها أربع قيم؛ و $(2, 5, 5)$ تحقق الشرطين كليهما. ولولا شرط إعادة الترتيب، لكانت $(0, 0, 0)$ مخرجات صحيحة لأيّ مدخلات.

مسألة مقترحة 2أرقام عدد، من اليمين إلى اليسار

اكتب خوارزمية في خطوات مرقّمة تتلقّى عددًا طبيعيًّا $n$ وتُخرج أرقامه من الأخير إلى الأول (لـ $4072$ تُخرج $2$ ، $7$ ، $0$ ، $4$ )، مستعملةً خارج القسمة على $10$ وباقيها فقط. تتبّعها يدويًّا لـ $4072$ ولـ $0$ ، وبرهن على أنها تتوقف لكل $n$ .

تلميح

باقي القسمة على $10$ هو الرقم الأخير، وخارج القسمة هو العدد من دونه. قرّر هل يُسأل عن الشرط قبل إخراج رقم أم بعده، وانظر ما يحدث مع $n = 0$ ، الذي له رقم واحد.

الإجابة

خوارزمية صحيحة: (1) أخرج باقي قسمة $n$ على $10$ ؛ (2) يأخذ $n$ قيمة خارج قسمة $n$ على $10$ ؛ (3) إذا كان $n > 0$ ، عُد إلى الخطوة 1؛ وإلا فتوقّف. يأتي السؤال بعد الجسم، فيُنفَّذ الجسم مرة واحدة على الأقل: لـ $n = 0$ تُخرج $0$ ، وهو رقمه الوحيد. ولو سُئل في البداية («ما دام $n > 0$ »)، لما أُخرج شيء لـ $n = 0$ ؛ وهذا خطأ نسيان الحالة التي لا يُنفَّذ فيها التكرار. التتبّع لـ $4072$ : تُخرج $2$ ، $7$ ، $0$ ، $4$ ، ويمرّ $n$ بـ $407$ ، $40$ ، $4$ ، $0$ . التوقف: المتغاير هو $n$ ، وهو عدد طبيعي؛ فإن عُدنا إلى الخطوة 1 فلأن $n > 0$ ، ولـ $n \geq 1$ يكون خارج القسمة على $10$ أصغر تمامًا من $n$ ، فيتناقص $n$ تناقصًا تامًّا في كل جولة.

مسألة مقترحة 3الفكّة بالقطع النقدية

لدينا قطع نقدية من فئات $50$ و $10$ و $1$ وحدات، بكمية غير محدودة. المواصفات: المدخلات، عدد طبيعي $m$ ؛ والمخرجات، ثلاثة أعداد طبيعية $c_{50}$ ، $c_{10}$ ، $c_1$ بحيث $50 c_{50} + 10 c_{10} + c_1 = m$ وبأقل عدد ممكن من القطع، $c_{50} + c_{10} + c_1$ . يقترح شخص الخوارزمية الآتية. أوجد مدخلات تخفق فيها، واشرح كل عيب وصحّحه.

$c_{50}$ و $c_{10}$ و $c_1$ تأخذ القيمة $0$ .
إذا كان $m \geq 50$ ، يأخذ $c_{50}$ القيمة $c_{50} + 1$ ويأخذ $m$ القيمة $m - 50$ .
ما دام $m > 10$ : يأخذ $c_{10}$ القيمة $c_{10} + 1$ ويأخذ $m$ القيمة $m - 10$ .
ما دام $m > 0$ : يأخذ $c_1$ القيمة $c_1 + 1$ ويأخذ $m$ القيمة $m - 1$ .
أخرج $c_{50}$ و $c_{10}$ و $c_1$ .

تلميح

مجموع القطع يساوي دائمًا $m$ ؛ وما قد يخفق هو عددها. جرّب مضاعفًا تامًّا لـ $10$ ومبلغًا يزيد على $100$ ، واسأل نفسك أيّ طريقة لضمّ الخطوات تستعملها الخطوة 2 وأيّها كان ينبغي أن تستعمل.

الإجابة

في الخوارزمية عيبان. الأول: الخطوة 3 تستعمل $m > 10$ : فمع $m = 10$ لا تُخرج أيّ قطعة من فئة $10$ وتُخرج عشر قطع من فئة $1$ ، بدل قطعة واحدة. الثاني: الخطوة 2 قرار حيث يلزم تكرار: فمع $m = 120$ تُخرج الخوارزمية كما هي مكتوبة قطعة من فئة $50$ ، وستًّا من فئة $10$ ، وعشرًا من فئة $1$ (سبع عشرة قطعة)، وحتى بعد تصحيح الخطوة 3 كانت ستُخرج قطعة من فئة $50$ وسبعًا من فئة $10$ (ثماني قطع)، بدل قطعتين من فئة $50$ وقطعتين من فئة $10$ (أربع قطع). والمدخلات $m = 100$ تُظهر العيبين معًا: تُخرج الخوارزمية قطعة من فئة $50$ ، وأربعًا من فئة $10$ ، وعشرًا من فئة $1$ ، أي خمس عشرة قطعة، بدل قطعتين. التصحيح: الخطوة 2، «ما دام $m \geq 50$ ، …»؛ الخطوة 3، «ما دام $m \geq 10$ ، …». وبعد هذا التصحيح تأخذ الخوارزمية دائمًا أكبر قطعة تتّسع، ومع هذه الفئات الثلاث يعطي ذلك أقل عدد: فرقم آحاد $m$ لا يُدفع إلا بقطع من فئة $1$ ، وما يتبقّى يحسن دفعه بقطع من فئة $50$ قدر الإمكان، لأن خمس قطع من فئة $10$ تساوي قطعة من فئة $50$ . ومع فئات أخرى، مثلًا $1$ و $3$ و $4$ لـ $m = 6$ ، لم يعد أخذ الأكبر دائمًا يعطي الحدّ الأدنى ( $4 + 1 + 1$ مقابل $3 + 3$ ).