ما هو عدد السلاسل الثنائية بدون 1 متتالية؟

دعونا نفكر في مثال لشرح مفهوم حساب السلاسل الثنائية بدون أرقام 1 متتالية.

مثال

لنفترض أننا نريد حساب عدد السلاسل الثنائية ذات الطول 3 والتي لا تحتوي على أرقام 1 متتالية. السلسلة الثنائية هي سلسلة تتكون من 0 و1 فقط.

السلاسل الثنائية المحتملة ذات الطول 3 هي: 000، 001، 010، 011، 100، 101، 110، و111.

ومع ذلك، نحتاج فقط إلى حساب تلك السلاسل الثنائية التي لا تحتوي على أرقام 1 متتالية. لذلك، نحن بحاجة إلى استبعاد السلاسل 011، 101، و111 من العد.

دعنا نحلل السلاسل الثنائية المتبقية:

• 000: هذه سلسلة صالحة لأنها لا تحتوي على أرقام 1 متتالية.

• 001: هذه سلسلة صالحة لأنها لا تحتوي على أرقام 1 متتالية.

• 010: هذه سلسلة صالحة لأنها لا تحتوي على أرقام 1 متتالية.

• 100: هذه سلسلة صالحة لأنها لا تحتوي على أرقام 1 متتالية.

• 110: هذه سلسلة غير صالحة لأنها تحتوي على أرقام 1 متتالية.

من التحليل أعلاه، يمكننا أن نرى أن هناك 4 سلاسل ثنائية صالحة بطول 3 بدون 1 متتالية.

برنامج PHP لحساب عدد السلاسل الثنائية بدون 1 متتالية

الطريقة الأولى- استخدام البرمجة الديناميكية

مثال

الإخراج

Number of binary strings without consecutive 1's: 13

شرح الكود

يحدد كود PHP هذا وظيفة تسمى countBinaryStrings التي تحسب عدد السلاسل الثنائية ذات الطول $n بدون أرقام 1 متتالية باستخدام البرمجة الديناميكية. يقوم بتهيئة مصفوفة $dp مع الحالات الأساسية $dp[0] = 1 و $dp[1] = 2، التي تمثل أعداد سلاسل الطول 0 و 1 على التوالي. ثم يستخدم حلقة لملء الأعداد المتبقية للأطوال من 2 إلى $n، عن طريق جمع أعداد الأطوال $i - 1 و $i - 2. وأخيرًا، يُرجع عدد الطول $n ويطبعه. في هذا المثال المحدد، يقوم الكود بحساب عدد السلاسل الثنائية بدون أرقام 1 متتالية بطول 5 ويعرض النتيجة.

الطريقة الثانية

الإخراج

Number of binary strings without consecutive 1's: 13

شرح الكود

يحسب كود PHP هذا عدد السلاسل الثنائية المميزة ذات الطول $n بدون رقمين متتاليين 1. وهو يحدد صفيفين، $a و$b، لتخزين الأعداد. يتم تعيين الحالات الأساسية كـ $a[0] = $b[0] = 1. ثم يتم استخدام حلقة لحساب أعداد الأطوال من 1 إلى $ ن-1. يتم الحصول على عدد الطول $i عن طريق جمع عدد الطول $i-1 من المصفوفة $a وعدد الطول $i-1 من المصفوفة $b. بالإضافة إلى ذلك، يتم الحصول على عدد الطول $i في المصفوفة $b من عدد الطول $i-1 في المصفوفة $ أ. أخيرًا، يُرجع الكود مجموع عدد الطول $n-1 من المصفوفة $a وعدد الطول $n-1 من المصفوفة $b، يمثل العدد الإجمالي للسلاسل الثنائية بدون أرقام 1 متتالية. في هذا المثال تحديدًا، يقوم الكود بحساب العدد لطول 5 ويعرض النتيجة.

خاتمة

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