يمكن حساب عدد تكرارات السلسلة الفرعية "12" في السلسلة باستخدام خوارزميات وطرق برمجة مختلفة.
طريقة واحدة لحساب عدد تكرارات السلسلة الفرعية " 12 " في سلسلة س هو استخدام حلقة وطريقة بحث سلسلة فرعية. يقوم البرنامج بمسح كل حرف من أحرف السلسلة بالتتابع ويتحقق مما إذا كانت الأحرف الحالية والتالية عبارة عن سلسلة فرعية من "12". إذا كان الأمر كذلك ، يتم زيادة العداد بمقدار واحد.
بالإضافة إلى ذلك ، هناك طرق أكثر كفاءة لحساب عدد تكرارات السلسلة الفرعية "12" في السلسلة س ، على سبيل المثال ، باستخدام التعبيرات العادية. يمكن للتعبير العادي تحديد النمط الذي يتم من خلاله البحث عن السلسلة الفرعية " 12 " في السلسلة س ، وحساب عدد التطابقات.
ومع ذلك ، من المهم أن تتذكر أن كل طريقة قد يكون لها خصائصها وفعاليتها الخاصة ، اعتمادا على الموقف المحدد والسلسلة س والنتيجة المرجوة لحساب عدد تكرارات السلسلة الفرعية "12".
- عدد تكرارات السلسلة الفرعية " 12 " في السلسلة س
- حل البرمجيات للمشكلة
- باستخدام وظيفة العد ()
- العد اليدوي للتكرارات من خلال حلقة
- البرمجة مع التعبيرات العادية
- خوارزمية بوير مور
- جدول التحولات
- مبدأ "الرمز السيئ"
- هو مثال على كيفية عمل الخوارزمية
- شروط استخدام مناهج مختلفة
- سؤال وجواب
- هل من الممكن استخدام التعبيرات العادية لحساب عدد مرات تكرار السلسلة الفرعية " 12 " في سلسلة س?
- هل يمكن للبرنامج أن يأخذ في الاعتبار حالة الأحرف عند حساب عدد تكرارات السلسلة الفرعية " 12 " في السلسلة س?
- كيف سيتعامل البرنامج مع الحالة عندما تكون السلسلة الفرعية" 12 " جزءا من سلسلة فرعية أخرى?
- كيف سيعمل البرنامج مع سلسلة فارغة?
عدد تكرارات السلسلة الفرعية " 12 " في السلسلة س
لحساب عدد مرات تكرار السلسلة الفرعية " 12 " في السلسلة س ، يمكنك استخدام الخوارزمية التالية:
- تهيئة عدد المتغيرات وتعيين القيمة 0. سيتم استخدام هذا المتغير لحساب عدد التكرارات.
- تذهب من خلال كل حرف من سلسلة الصورة ، بدءا من الحرف الأول.
- في كل خطوة ، تحقق مما إذا كان الحرف الحالي هو "1".
- إذا كان الحرف الحالي هو" 1 " ، فتحقق من الحرف التالي. إذا كان الحرف التالي هو " 2 " ، فقم بزيادة متغير العد بمقدار 1.
- بعد التحقق من جميع أحرف السلسلة س ، ستحتوي القيمة الناتجة لمتغير العد على عدد تكرارات السلسلة الفرعية " 12 " في سلسلة س.
مثال على تنفيذ الخوارزمية في بايثون:
عدد صف (سلاسل):
العد = 0
لأني في النطاق (لين (ق) - 1):
إذا الصورة [أنا] = = ' 1 ' و الصورة [أنا + 1] = ='2':
عدد + = 1
عد العودة
س = "123142152134125151245121521451221"
النتيجة = العد_الوتر(الأوتار)
طباعة ("عدد تكرارات السلسلة الفرعية \" 12\ "في سلسلة س:" ، النتيجة)
في هذا المثال ، تأخذ الدالة كونت سوبسترينغ سلسلة س وإرجاع عدد مرات تكرار السلسلة الفرعية" 12 " في هذه السلسلة. يتم عرض نتيجة الحساب.
وبالتالي ، لحساب عدد تكرارات السلسلة الفرعية "12" في سلسلة س ، تحتاج إلى تصفح جميع أحرف السلسلة والتحقق مما إذا كان هناك حرف تالي " 2 " بعد الحرف الحالي. بعد الانتهاء من جميع الشيكات ، يمكنك الحصول على عدد التكرارات.
حل البرمجيات للمشكلة
لحساب عدد تكرارات السلسلة الفرعية "12" في سلسلة ، يمكننا استخدام خوارزمية بسيطة:
- تهيئة عدد متغير العداد بالقيمة 0.
- كرر على كل حرف في السلسلة س.
- إذا كان الحرف الحالي والحرف التالي يشكلان سلسلة فرعية "12" ، فقم بزيادة العداد بمقدار 1.
- نرجع قيمة عداد العد نتيجة لذلك.
يمكن تنفيذ الخوارزمية أعلاه ، على سبيل المثال ، في لغة برمجة بايثون:
عدد صف (سلاسل):
العد = 0
لأني في النطاق (لين (ق) - 1):
إذا ق [أنا: أنا+2] = = "12":
عدد + = 1
عد العودة
# مثال الاستخدام:
س = "1123412"
النتيجة = العد_الوتر(الأوتار)
طباعة (النتيجة) # الإخراج: 2
في هذا المثال ، تأخذ وظيفة كونت سوبسترينغ السلسلة س وإرجاع عدد مرات تكرار السلسلة الفرعية" 12 " في هذه السلسلة. ثم نقوم بإنشاء متغير س واستدعاء وظيفة العد _ سلسلة السلسلة س. يتم عرض النتيجة على الشاشة.
وبالتالي ، باستخدام خوارزمية بسيطة والرمز المقابل ، يمكننا حل مشكلة حساب عدد تكرارات السلسلة الفرعية " 12 " في سلسلة.
باستخدام وظيفة العد ()
في بيثون ، يمكنك استخدام طريقة العد () لحساب عدد مرات تكرار سلسلة فرعية في سلسلة.
وظيفة بناء الجملة: وظيفة
| المعلمة | الوصف | |
|---|---|---|
عدد() | الفرعية | سلسلة (سلسلة فرعية) ، يجب حساب عدد مرات حدوثها |
مثال على استخدام الوظيفة:
س = "1212112121"العد = ق. العد ("12")
طباعة (العد) # الإخراج: 4
في هذا المثال ، سلسلة س يحتوي على العديد من تكرارات السلسلة الفرعية"12".
تقوم وظيفة العد() بإرجاع عدد هذه التكرارات ، والتي يتم عرضها بعد ذلك على الشاشة.
العد اليدوي للتكرارات من خلال حلقة
إذا لم يوفر البرنامج وظيفة مضمنة لحساب عدد مرات تكرار سلسلة فرعية في سلسلة ، فيمكنك استخدام حلقة للعد اليدوي.
في هذه الحالة ، نريد حساب عدد تكرارات السلسلة الفرعية "12" في السلسلة س.
قد تبدو الخوارزمية كما يلي:
- إنشاء متغير العد وتعيين القيمة 0.
- تذهب من خلال كل حرف من سلسلة الصورة.
- تحقق مما إذا كان الحرف الحالي والحرف التالي يشكلان سلسلة فرعية "12".
- إذا تم استيفاء الشرط ، قم بزيادة متغير العد بمقدار 1.
باستخدام هذه الخوارزمية ، سيقوم البرنامج بالتحقق بالتتابع من كل زوج من الأحرف في السلسلة س وزيادة العداد إذا كان هذا الزوج من الأحرف يشكل السلسلة الفرعية "12". في نهاية الحلقة ، سيحتوي متغير العد على العدد المطلوب من التكرارات.
مثال على كود بايثون:
س = "12121212"
العد = 0
لأني في النطاق (لين (ق) - 1):
إذا ق [أنا: أنا+2] = = "12":
عدد + = 1
طباعة ("عدد تكرارات السلسلة الفرعية" 12 "في السلسلة س:" ، عد)
سيؤدي تنفيذ هذا الرمز للسلسلة "12121212" إلى إخراج النتيجة التالية:
عدد تكرارات السلسلة الفرعية ' 12 ' في سلسلة س: 4
وبالتالي ، فإن استخدام حلقة يسمح لك بحساب عدد تكرارات السلسلة الفرعية "12" يدويا في السلسلة س.
البرمجة مع التعبيرات العادية
البرمجة باستخدام التعبيرات العادية يمكن أن تبسط إلى حد كبير عملية العمل مع البيانات النصية. تعد التعبيرات العادية أداة قوية للبحث عن السلاسل ومعالجتها وفقا لأنماط معينة.
عند العمل باستخدام التعبيرات العادية ، قد يكون من المفيد استخدام أحرف وتركيبات خاصة تسمح لك بوصف الأنماط المعقدة للبحث عن النص ومطابقته.
فيما يلي بعض الأمثلة على استخدام التعبيرات العادية:
- سيحدد ما إذا كانت السلسلة" س "تحتوي على السلسلة الفرعية"12".
- سيسمح لك بالعثور على جميع تكرارات السلسلة الفرعية "12" في السلسلة "س".
- سيحل محل جميع تكرارات السلسلة الفرعية "12" في السلسلة " س " بسلسلة أخرى.
- يسمح لك بتقسيم السلسلة " س " إلى سلاسل فرعية بواسطة أحرف المسافات البيضاء.
يمكن أن تكون التعبيرات العادية أداة قوية جدا عند العمل مع البيانات النصية. إنها تجعل من السهل العثور على السلاسل ومعالجتها واستبدالها وفقا لأنماط معينة ، مما يبسط إلى حد كبير تطوير كود البرنامج.
خوارزمية بوير مور
خوارزمية بوير مور هي واحدة من الخوارزميات الأكثر كفاءة للبحث عن سلسلة فرعية في سلسلة. تم تطويره في عام 1977 من قبل آر بوير وجي مور.
تعتمد هذه الخوارزمية على فكرتين رئيسيتين: استخدام جدول التحول ومبدأ "الرمز السيئ".
جدول التحولات
الفكرة الأساسية لخوارزمية بوير مور هي أنه يمكننا تخطي بعض الأحرف في كل مقارنة لتجنب المقارنات غير الفعالة. للقيام بذلك ، يتم تعيين قيمة لكل حرف في السلسلة الفرعية تحدد مقدار انتقال الحرف إلى اليمين في حالة عدم التطابق. يتم تخزين هذه القيم في جدول التحول.
يحتوي جدول التحول على معلومات حول الحد الأقصى للتحول لكل حرف في السلسلة الفرعية. في حالة عدم تطابق بين حرف في سلسلة وحرف في سلسلة فرعية ، نستخدم جدول التحول لتحديد الحد الأقصى للتحول. إذا لم يحدث الرمز في السلسلة الفرعية ، فيمكننا تحويل الطول الكامل للسلسلة الفرعية ، حيث لا يمكن أن يكون الرمز جزءا من السلسلة الفرعية.
مبدأ "الرمز السيئ"
في حالة عدم تطابق حرف في سلسلة مع حرف في سلسلة فرعية ، تستخدم خوارزمية بوير مور مبدأ "الحرف السيئ" لتحديد أقصى تحول ممكن. يقوم بتحريك السلسلة الفرعية بحيث يتطابق آخر ظهور للحرف مع الحرف في السلسلة. ثم يتم فحص الأحرف المتبقية من السلسلة الفرعية حتى يتم العثور على تطابق أو حتى تتم مقارنة السلسلة الفرعية تماما بالسلسلة الأصلية.
مثال على كيفية عمل الخوارزمية
لنفترض أن لدينا سلسلة " أبكاباكاب "ونحن نبحث عن سلسلة فرعية"الكابينة". أولا ، نبني جدول التحولات:
| الرمز | التحول |
|---|---|
| c | 2 |
| a | 1 |
| b | 3 |
تتم مقارنة السلسلة الأصلية "أبكاباكاب "مع سلسلة فرعية"الكابينة". بما أن الحرف الأول لا يتطابق، يتم تنفيذ التحول الصحيح من خلال 3 مواضع (الحد الأقصى للتحول للحرف "ج"). بعد ذلك ، يكون أول ظهور للحرف "ج" في السلسلة المصدر ويتم مقارنته بالحرف "ج" في السلسلة الفرعية. منذ تطابق الأحرف ، يستمر الفحص أكثر.
تستمر خوارزمية بوير مور في مقارنة الأحرف حتى يتم العثور على تطابق كامل للسلسلة الفرعية مع السلسلة الأصلية ، أو يتم التحقق من السلسلة الفرعية بالكامل.
خوارزمية بوير مور فعالة جدا للبحث عن سلسلة فرعية في سلسلة. يمكن أن يقلل بشكل كبير من عدد المقارنات ، لأنه قادر على تخطي عدة أحرف في كل مقارنة ، استنادا إلى جدول التحول المحسوب مسبقا. وبالتالي ، فإنه يسمح لك بحل مشكلة البحث عن سلسلة فرعية في سلسلة أسرع بكثير.
شروط استخدام مناهج مختلفة
لحساب عدد تكرارات السلسلة الفرعية " 12 " في السلسلة س ، هناك العديد من الأساليب التي يمكن استخدامها اعتمادا على ظروف المهمة:
- باستخدام حلقة:
- باستخدام طريقة العد ():
- استخدام التعبيرات العادية:
يمكنك حلقة من خلال سلسلة الصورة والتحقق من كل زوج من الأحرف للمساواة "12". زيادة العداد لكل مباراة. هذا النهج مناسب إذا كان حجم السلسلة س صغير.
تحتوي بعض لغات البرمجة على طريقة العد () المضمنة التي تسمح لك بحساب عدد تكرارات سلسلة فرعية معينة. إذا كانت لغة البرمجة التي تستخدمها تحتوي على مثل هذه الطريقة ، فسيكون هذا هو الحل الأبسط والأكثر فعالية.
التعبيرات العادية هي أداة قوية للعمل مع النص. باستخدام التعبيرات العادية ، يمكنك تحديد نمط السلسلة الفرعية "12" والعثور على جميع تكرارات هذا النمط في السلسلة س. هذا النهج مناسب تماما إذا كانت هناك حاجة إلى معالجة أكثر تعقيدا للسلسلة س.
يعتمد اختيار نهج معين على متطلبات الأداء وأدوات البرمجة المتاحة وتعقيد المهمة.
سؤال وجواب
هل من الممكن استخدام التعبيرات العادية لحساب عدد مرات تكرار السلسلة الفرعية " 12 " في سلسلة س?
نعم ، يمكنك استخدام التعبيرات العادية لحساب عدد مرات تكرار السلسلة الفرعية " 12 " في السلسلة ق. على سبيل المثال ، في بيثون ، يمكنك استخدام وحدة إعادة وإعادة.فيندال () وظيفة. هذه الوظيفة سوف تجد كل التكرارات منفصلة من سلسلة فرعية " 12 " في سلسلة الصورة وإعادتها كقائمة. سيحتوي طول هذه القائمة على عدد التكرارات.
هل يمكن للبرنامج أن يأخذ في الاعتبار حالة الأحرف عند حساب عدد تكرارات السلسلة الفرعية " 12 " في السلسلة س?
نعم ، يمكن للبرنامج أن يأخذ في الاعتبار حالة الأحرف عند حساب عدد تكرارات السلسلة الفرعية " 12 " في السلسلة س. إذا كنت بحاجة إلى أخذ الحالة في الاعتبار ، فعند مقارنة الأحرف ، تحتاج إلى استخدام تطابق تام ، دون تحويل حالة الحرف. إذا كان لا ينبغي أخذ الحالة في الاعتبار ، فقبل مقارنة الأحرف ، تحتاج إلى تحويل كلا الحرفين إلى أحرف كبيرة أو صغيرة بحيث تكون المقارنة غير حساسة لحالة الأحرف.
كيف سيتعامل البرنامج مع الحالة عندما تكون السلسلة الفرعية" 12 " جزءا من سلسلة فرعية أخرى?
إذا كانت السلسلة الفرعية" 12 "جزءا من سلسلة فرعية أخرى ، فسيعتبرها البرنامج بمثابة حدث واحد للسلسلة الفرعية"12". على سبيل المثال ، إذا كان هناك سلسلة فرعية "121" في السلسلة س ، فسيعتبر البرنامج هذا حدثا واحدا وليس اثنين. عند مقارنة الأحرف ، سيتحقق البرنامج بالضبط من أزواج الأحرف " 12 " في السلسلة س.
كيف سيعمل البرنامج مع سلسلة فارغة?
إذا كانت السلسلة س فارغة ، يقوم البرنامج بإرجاع 0 ، حيث لا يمكن أن يكون هناك تكرار واحد للسلسلة الفرعية" 12 " في سلسلة فارغة. باستخدام سطر فارغ ، يمكن للبرنامج التحقق من النتيجة وإعادتها على الفور ، دون إجراء دورات وعمليات أخرى.