ابحث عن سلسلة فرعية في النص (سلسلة). خوارزمية القوة الغاشمة

لدي مشكلة حسابية أحلها عن طريق التجربة والخطأ (أعتقد أن هذا يسمى القوة الغاشمة) ويعمل البرنامج بشكل جيد عندما تكون هناك معلمات متعددة ، ولكن مع إضافة المزيد من المتغيرات / البيانات ، يستغرق تشغيله وقتًا أطول.

مشكلتي هي أنه بينما يعمل النموذج الأولي ، فإنه مفيد لآلاف المتغيرات ومجموعات البيانات الكبيرة ؛ لذلك ، أنا أتساءل عما إذا كان يمكن توسيع نطاق خوارزميات القوة الغاشمة. كيف يمكنني الاقتراب من توسيع نطاقه؟

3 إجابات

عادةً ، يمكنك تحديد مدى جودة مقياس الخوارزمية باستخدام تدوين الاستدلال الكبير لتحليل معدل نموها. عندما تقول إن الخوارزمية الخاصة بك تعمل تحت القوة الغاشمة ، فمن غير الواضح إلى أي مدى ستتوسع. إذا كان حل القوة الغاشمة الخاص بك يعمل من خلال سرد جميع المجموعات الفرعية أو المجموعات الممكنة من مجموعة البيانات ، فمن شبه المؤكد أنه لن يتم قياسه (سيكون له تعقيد مقارب O (2 n) أو O (n!) ، على التوالي). إذا كان حل القوة الغاشمة الخاص بك يعمل من خلال إيجاد جميع أزواج العناصر واختبارها ، فيمكن أن يتوسع بشكل جيد بما فيه الكفاية (O (n 2)). ومع ذلك ، بدون معلومة اضافيةمن الصعب تحديد كيفية عمل الخوارزمية.

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

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

تم إغلاق خوارزمية حل هذه المشكلة للعملية التي ندرسها للتقسيم الرياضي اليدوي ، وكذلك للتحويل من نظام عشري إلى قاعدة أخرى ، مثل ثماني أو سداسي عشري ، باستثناء أنه في المثالين لم يتم النظر إلا في حل أساسي واحد.

للتأكد من اكتمال العودية ، من المهم طلب مجموعة البيانات. لكي تكون فعّالًا وللحد من عدد العودية ، من المهم أن تبدأ بقيم بيانات أعلى أيضًا.

على وجه التحديد ، إليك تطبيق Java تعاودي لهذه المشكلة - مع نسخة من متجه نتيجة المعامل لكل تكرار كما هو متوقع من الناحية النظرية.

استيراد java.util.Arrays ؛ فئة public Solver (رئيسي ثابت عام فارغ (سلاسل سلسلة) (int target_sum = 100 ؛ // متطلب سابق: قيم مرتبة !! int data = new int (5، 10، 20، 25، 40، 50)؛ / / متجه النتيجة ، init to 0 int coeff = new int؛ Arrays.fill (coeff، 0)؛ partSum (data.length - 1، target_sum، coeff، data)؛) لـ (int i = coeff.length - 1؛ i> = 0؛ i--) (if (coeff [i]> 0) (System.out.print (data [i] + "*" + coeff [i] + "") ؛)) System.out.println () ؛) مجموع الفراغ الثابت الخاص الجزئي (int k، int sum، int coeff، int data) (int x_k = data [k]؛ for (int c = sum / x_k ؛ c> = 0؛ c--) (coeff [k] = c؛ if (c * x_k == sum) (printResult (coeff، data)؛ تابع؛) وإلا إذا (k> 0) (// نتيجة سياقية في المعلمات ، محلي لنطاق الطريقة int newcoeff = Arrays.copyOf (معامل ، معامل طول) ؛ مجموع جزئي (k - 1 ، sum - c * x_k ، newcoeff ، بيانات) ؛ // for loop on "c" يستمر مع السابق محتوى معامل))))

لكن هذا الرمز الآن في حالة خاصة: الاختبار الأخير لقيمة كل معامل هو 0 ، لذلك لا حاجة إلى نسخة.

كتقدير للتعقيد ، يمكننا استخدام أقصى عمق للمكالمات المتكررة مثل data.length * min ((data)). بالطبع لن يتم القياس بشكل جيد وستكون ذاكرة تتبع المكدس (خيار JVM -Xss) عاملاً محدودًا. قد يفشل الرمز مع وجود خطأ في مجموعة كبيرةالبيانات.

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

استيراد java.util.Arrays ؛ استيراد java.util.ArrayDeque ؛ استيراد java.util.Queue ؛ فئة عامة غير متسلسلة (// متطلب سابق: قيم تم فرزها !! بيانات نهائية نهائية خاصة ثابتة = int (5 ، 10 ، 20 ، 25 ، 40 ، 50) ؛ // سياق لتخزين الحساب الوسيط أو فئة ثابتة للحل السياق (int k؛ int sum؛ int coeff؛ Context (int k، int sum، int coeff) (this.k = k؛ this.sum = sum؛ this.coeff = coeff؛)) private static void printResult (int coeff ) (لـ (int i = coeff.length - 1؛ i> = 0؛ i--) (if (coeff [i]> 0) (System.out.print (data [i] + "*" + coeff [ i] + "")؛)) System.out.println () ؛) مفتاح الفراغ الثابت العام (سلاسل السلسلة) (int target_sum = 100 ؛ // متجه النتيجة ، init إلى 0 int coeff = new int ؛ Arrays.fill ( معامل ، 0) ؛ // قائمة انتظار مع سياقات لمعالجة قائمة الانتظار السياقات = جديد ArrayDeque () ؛ // السياقات الأولية. إضافة (سياق جديد (طول البيانات - 1 ، المجموعة المستهدفة ، المعامل)) ؛ while (! Contexts.isEmpty ()) (Context current = Contexts.poll ()؛ int x_k = data؛ for (int c = current.sum / x_k؛ c> = 0؛ c--) (current.coeff = c ؛ int newcoeff = Arrays.copyOf (current.coeff، current.coeff.length) ؛ if (c * x_k == current.sum) (printResult (newcoeff) ؛ تابع ؛) وإلا إذا (current.k> 0) (سياقات .add (سياق جديد (current.k - 1، current.sum - c * x_k، newcoeff))؛)))))

من وجهة نظري ، من الصعب أن تكون أكثر كفاءة في تنفيذ مؤشر ترابط واحد - تتطلب آلية المكدس الآن نسخًا من مصفوفة المعاملات.

طريقة القوة الغاشمة

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

شاهد ما هو "أسلوب القوة الغاشمة" في القواميس الأخرى:

القوة الغاشمة الكاملة (أو طريقة "القوة الغاشمة") هي طريقة لحل مشكلة عن طريق تعداد جميع الخيارات الممكنة. يعتمد تعقيد البحث الشامل على أبعاد مساحة جميع الحلول الممكنة للمشكلة. إذا كانت مساحة القرار ...... ويكيبيديا

الفرز حسب التبادلات البسيطة ، الفرز حسب الفقاعة (فرز الفقاعات الهندسية) هو خوارزمية فرز بسيطة. للفهم والتنفيذ ، هذه الخوارزمية هي الأبسط ، لكنها فعالة فقط للمصفوفات الصغيرة. تعقيد الخوارزمية: O (n²). الخوارزمية ... ... ويكيبيديا

هذا المصطلح له معاني أخرى ، انظر القوة الغاشمة. طريقة حل القوة الغاشمة الكاملة (أو طريقة "القوة الغاشمة") مسائل حسابية... ينتمي إلى فئة الأساليب لإيجاد حل عن طريق استنفاد جميع أنواع ... ... ويكيبيديا

غلاف الطبعة الأولى من كتيب "وثائق بيل ..."

Snefru هي دالة تجزئة مشفرة أحادية الاتجاه اقترحها رالف ميركل. (اسم سنفرو نفسه ، استمرارًا لتقليد شفرات الكتلة خوفو وخفرع ، الذي طوره أيضًا رالف ميركل ، هو اسم المصري ... ... ويكيبيديا

محاولة كسر (فك تشفير) البيانات المشفرة بتشفير كتلة. جميع أنواع الهجمات الرئيسية قابلة للتطبيق على حظر الشفرات ، ولكن هناك بعض الهجمات المخصصة فقط لمنع الأصفار. المحتويات 1 أنواع الهجمات 1.1 عام ... ويكيبيديا

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

الطريق الأمثل لبائعي المبيعات المتجولين عبر أكبر 15 مدينة في ألمانيا. الطريق المشار إليه هو أقصر الطرق الممكنة 43589145600. مشكلة بائع متجول (TSP) (ويكيبيديا

وظيفة تجزئة التشفير الاسم N Hash تم إنشاؤه 1990 تم النشر في 1990 حجم التجزئة 128 بت عدد الدورات 12 أو 15 نوع Hash نوع N Hash تشفير ... Wikipedia

تعد مشكلة البائع المتجول (بائع متجول) واحدة من أشهر مشاكل التحسين الاندماجي. المهمة هي العثور على الطريق الأكثر ربحية يمر مدن محددةمرة واحدة على الأقل مع ... ... ويكيبيديا

أرز. 11.6. إجراء إنشاء القائمة أرز. 11.7. صورة بيانيةكومة أرز. 11.8 مثال شجرة ثنائية أرز. 11.9 خطوة تحويل الشجرة إلى ثنائي

يتم تحديد مشكلة الفرز بالطريقة التالية. يجب أن يكون هناك مجموعة من الأعداد الصحيحة أو أرقام حقيقيةيلزم إعادة ترتيب عناصر هذه المصفوفة بحيث يتم ترتيبها بعد إعادة الترتيب بترتيب غير تنازلي: الصيغة "src =" http://hi-edu.ru/e-books/xbook691/files/178- 2.gif "border =" 0 "align =" absmiddle "alt =" (! LANG:إذا كانت الأرقام مختلفة في الاتجاهين ، فإنهم يتحدثون عن الترتيب بترتيب تصاعدي أو تنازلي. فيما يلي ، سننظر في مشكلة الترتيب غير المتناقص ، حيث يتم حل المشكلات الأخرى بطريقة مماثلة. هناك العديد من خوارزميات الفرز ، ولكل منها خصائص سرعتها الخاصة. لنفكر في أبسط الخوارزميات من أجل زيادة سرعة عملها.

فرز حسب التبادلات (فقاعة)

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

بعد المرور الأول عبر المصفوفة ، يتضح أن "الجزء العلوي" (في بداية المصفوفة) هو العنصر "الأخف وزناً" (الأدنى) ، ومن هنا يكون التشابه مع فقاعة تنبثق (الشكل 11.1)
). يتم المرور التالي إلى العنصر الثاني من الأعلى ، وبالتالي يتم رفع ثاني أكبر عنصر إلى الموضع الصحيح ، وهكذا.

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

العنوان الفرعي "> فرز حسب التحديد

فرز التحديد أسرع قليلاً من فرز الفقاعة. الخوارزمية هي كما يلي: تحتاج إلى العثور على عنصر المصفوفة الذي يحتوي على أصغر قيمة ، وإعادة ترتيبه بالعنصر الأول ، ثم القيام بالشيء نفسه ، بدءًا من العنصر الثاني ، وما إلى ذلك. وبالتالي ، يتم إنشاء تسلسل تم فرزه عن طريق إرفاق عنصر تلو الآخر به بالترتيب الصحيح. تشغيل الخطوة الأولىاختر أصغر العناصر a [i] ... a [n] ، وقم بتبديلها بـ [i]. يظهر تسلسل الخطوات في الشكل. 11.2
.

بغض النظر عن رقم الخطوة الحالية i ، يتم ترتيب التسلسل a ... a [i]. وهكذا ، في الخطوة (ن - 1) ، يتم فرز التسلسل بأكمله باستثناء [n] ، و [n] يقف على آخر مكانعلى اليمين: جميع العناصر الأصغر انتقلت بالفعل إلى اليسار.

العنوان الفرعي "> فرز حسب الإدخالات البسيطة

يتم فحص المصفوفة ضوئيًا ، ويتم إدخال كل عنصر جديد [i] في مكان مناسب في المجموعة المرتبة بالفعل أ ، ... ، أ. يتم تحديد هذا المكان من خلال المقارنة التسلسلية لـ [i] مع العناصر المرتبة أ ، ... ، أ. وهكذا ، فإن التسلسل المصنف "ينمو" في بداية المصفوفة.

ومع ذلك ، في تصنيف الفقاعة أو التحديد ، يمكن للمرء أن يذكر بوضوح أنه في الخطوة الأولى ، تكون العناصر أ ... في الأماكن الصحيحة ولن تتحرك في أي مكان آخر. في حالة الفرز عن طريق عمليات الإدراج البسيطة ، يمكن القول أن التسلسل a ... a مرتب. في هذه الحالة ، في سياق الخوارزمية ، سيتم إدراج جميع العناصر الجديدة فيها (انظر اسم الطريقة).

ضع في اعتبارك إجراءات الخوارزمية في الخطوة الأولى. كما ذكرنا سابقًا ، يتم تقسيم التسلسل في هذه المرحلة إلى جزأين: جاهز a ... a وغير مرتب a [i] ... a [n].

في المرة التالية ، أي في كل خطوة من خطوات الخوارزمية ، نأخذ [i] ونقوم بإدخالها في المكان الصحيح في الجزء النهائي من المصفوفة. يتم البحث عن مكان مناسب للعنصر التالي من تسلسل الإدخال عن طريق مقارنات متتالية مع العنصر الموجود أمامه. اعتمادًا على نتيجة المقارنة ، يظل العنصر إما في موضعه الحالي (اكتمل الإدراج) ، أو يتم تبديلها وتتكرر العملية (الشكل 11.3)
).

وهكذا ، في عملية الإدراج ، نقوم "بغربلة" العنصر X إلى بداية المصفوفة ، ونتوقف إذا

• تم العثور على عنصر أقل من X ؛
• تم الوصول إلى بداية التسلسل.

حدد "> بواسطة خوارزمية البحث الخطي ، عندما يتم اجتياز المصفوفة بأكملها بالتسلسل ، ويتم مقارنة العنصر الحالي للمصفوفة بالعنصر المطلوب. في حالة التطابق ، يتم تخزين فهرس (مؤشرات) العنصر الذي تم العثور عليه.

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

ابحث عن سلسلة فرعية في النص (سلسلة). خوارزمية القوة الغاشمة

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

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

العنوان الفرعي "> خوارزمية Boyer-Moore

يتكون أبسط نسخة من خوارزمية Boyer-Moore من الخطوات التالية. تتمثل الخطوة الأولى في بناء جدول للتعويضات للعينة المرغوبة. ثم تتم محاذاة بداية السطر والنمط ويبدأ الاختيار من آخر حرف في النموذج. إذا كان الحرف الأخير من النمط وحرف السلسلة المقابل له عند التراكب غير متطابقين ، يتم إزاحة النمط بالنسبة إلى السلسلة بالمقدار الذي تم الحصول عليه من جدول الإزاحة ، ويتم إجراء المقارنة مرة أخرى ، بدءًا من الحرف الأخير من النمط . إذا تطابق الأحرف ، تتم مقارنة الحرف التالي إلى الأخير من النمط ، وهكذا. إذا تطابقت جميع الأحرف في النمط مع الأحرف المتراكبة في السلسلة ، فعندئذٍ تم العثور على السلسلة الفرعية وانتهى البحث. إذا كانت بعض الأحرف (وليس الأخيرة) من النمط لا تتطابق مع الحرف المقابل للسلسلة ، فإننا نحول النمط حرفًا واحدًا إلى اليمين ونبدأ في التحقق مرة أخرى من الحرف الأخير. يتم تنفيذ الخوارزمية بأكملها حتى يتم العثور على حدوث النمط المطلوب ، أو الوصول إلى نهاية السلسلة.

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

يعتمد مقدار الإزاحة لكل حرف في النمط فقط على ترتيب الأحرف في النمط ، لذلك من الملائم حساب الإزاحات مقدمًا وتخزينها كمصفوفة أحادية البعد ، حيث يتوافق كل حرف في الأبجدية مع إزاحة بالنسبة إلى الحرف الأخير في النمط. دعونا نشرح كل ما سبق في مثال بسيط... يجب أن تكون هناك مجموعة من خمسة أحرف: a ، b ، c ، d ، e وتحتاج إلى العثور على تكرار النمط "abbad" في السلسلة "abeccacbadbabbad". توضح المخططات التالية جميع مراحل تنفيذ الخوارزمية:

الصيغة "src =" http://hi-edu.ru/e-books/xbook691/files/ris-page184-1.gif "border =" 0 "align =" absmiddle "alt =" (! LANG:

بداية البحث. لا يتطابق الحرف الأخير في النمط مع حرف السطر المتراكب. انقل العينة إلى اليمين بمقدار 5 مواضع:

الصيغة "src =" http://hi-edu.ru/e-books/xbook691/files/ris-page185.gif "border =" 0 "align =" absmiddle "alt =" (! LANG:

الحرف الأخير يختلف مرة أخرى عن حرف السلسلة. وفقًا لجدول الإزاحة ، نحول العينة إلى موضعين:

الصيغة "src =" http://hi-edu.ru/e-books/xbook691/files/ris-page185-2.gif "border =" 0 "align =" absmiddle "alt =" (! LANG:

الآن ، وفقًا للجدول ، نحول العينة إلى موضع واحد ونحصل على التكرار المطلوب للعينة:

الصيغة "src =" http://hi-edu.ru/e-books/xbook691/files/ris-page185-4.gif "border =" 0 "align =" absmiddle "alt =" (! LANG:

الصيغة "src =" http://hi-edu.ru/e-books/xbook691/files/ris-page186.gif "border =" 0 "align =" absmiddle "alt =" (! LANG:

تُرجع الدالة BMSearch موضع الحرف الأول من التواجد الأول للنمط P في السلسلة S. إذا لم يتم العثور على التسلسل P في S ، تُرجع الدالة 0 (تذكر أنه في ObjectPascal ، يبدأ ترقيم الأحرف في السلسلة عند 1). تسمح لك معلمة StartPos بتحديد الموضع في سلسلة S لبدء البحث. يمكن أن يكون هذا مفيدًا إذا كنت تريد العثور على جميع تكرارات P في S. للبحث من بداية السلسلة ، قم بتعيين StartPos يساوي 1. إذا كانت نتيجة البحث ليست صفرًا ، فمن أجل العثور على التكرار التالي لـ P في S ، تحتاج إلى تعيين StartPos مساوية للقيمة "النتيجة السابقة بالإضافة إلى طول العينة".

بحث ثنائي (ثنائي)

يتم استخدام البحث الثنائي إذا كانت المصفوفة التي يتم تنفيذها مرتبة بالفعل.

يحتوي المتغيران Lb و Ub ، على التوالي ، على الحدود اليمنى واليسرى لمقطع الصفيف حيث يوجد العنصر المطلوب. يبدأ البحث دائمًا بفحص العنصر الأوسط للقطعة المستقيمة. إذا كانت القيمة المطلوبة أقل من العنصر الأوسط ، فأنت بحاجة إلى الانتقال إلى البحث في النصف العلوي من المقطع ، حيث تكون جميع العناصر أقل من العنصر المحدد للتو. بمعنى آخر ، Ub تصبح (M-1) ، يتم فحص نصف المصفوفة الأصلية في التكرار التالي. وبالتالي ، كنتيجة لكل فحص ، يتم تقسيم منطقة البحث إلى النصف. على سبيل المثال ، إذا كان هناك 100 رقم في المصفوفة ، فبعد التكرار الأول ، يتم تقليل منطقة البحث إلى 50 رقمًا ، وبعد الثانية - إلى 25 ، وبعد الثالث إلى 13 ، وبعد الرابع إلى 7 ، وما إلى ذلك. gif "حد = "0" align = "absmiddle" alt = "(! LANG:

تعتمد هياكل البيانات الديناميكية على استخدام المؤشرات واستخدام الإجراءات والوظائف القياسية لتخصيص / تحرير الذاكرة في سياق البرنامج. وهي تختلف عن هياكل البيانات الثابتة الموضحة في الأنواع وأقسام البيانات. عندما يتم وصف متغير ثابت في برنامج ، فعند تجميع البرنامج ، اعتمادًا على نوع المتغير ، الرامات "الذاكرة العشوائية في الهواتف والحواسيب... ومع ذلك ، لا يمكن تغيير حجم الذاكرة المخصصة.

على سبيل المثال ، إذا تم تحديد مصفوفة

Var S: مصفوفة من char ،

ثم يتم تخصيص 10 بايت من ذاكرة الوصول العشوائي لها مرة واحدة في بداية تنفيذ البرنامج.

تتميز الهياكل الديناميكية بعدم الاتساق وعدم القدرة على التنبؤ بحجم (عدد العناصر) للهيكل أثناء معالجته.

نظرًا لأن عناصر البنية الديناميكية توجد في عناوين ذاكرة غير متوقعة ، فلا يمكن حساب عنوان عنصر من هذا الهيكل من عنوان عنصر البداية أو العنصر السابق.

لإنشاء روابط بين عناصر بنية ديناميكية ، يتم استخدام المؤشرات التي يتم من خلالها إنشاء روابط صريحة بين العناصر. هذا التمثيل للبيانات في الذاكرة يسمى متماسك. يتكون عنصر الهيكل الديناميكي من حقلين:

• حقل معلومات أو حقل بيانات يحتوي على البيانات التي يتم إنشاء الهيكل من أجلها ؛ في الحالة العامة ، مجال المعلومات هو في حد ذاته بنية متكاملة: سجل ، متجه ، مصفوفة ، هيكل ديناميكي آخر ، إلخ ؛
• ربط الحقول التي تحتوي على واحد أو أكثر من المؤشرات المرتبطة عنصر معينمع عناصر الهيكل الأخرى.

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

مزايا تمثيل البيانات المتماسك:

• القدرة على توفير تنوع كبير في الهياكل ؛
• قصر حجم الهيكل فقط على المقدار المتاح من ذاكرة الجهاز ؛
• عند تغيير التسلسل المنطقي لعناصر الهيكل ، لا يلزم نقل البيانات في الذاكرة ، ولكن فقط لتصحيح المؤشرات ؛
• مرونة كبيرة في الهيكل.

في الوقت نفسه ، لا يخلو التمثيل المتماسك من عيوبه ، وأهمها:

يتم إنفاق ذاكرة إضافية في حقول الحزم ؛

يمكن أن يكون الوصول إلى عناصر بنية متماسكة أقل كفاءة من حيث الوقت.

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

الهياكل الديناميكية المستخدمة في البرمجة تشمل:

• المصفوفات الديناميكية (تمت مناقشتها في الموضوع 6) ؛
• قوائم خطية
• كومة؛
• بدوره ، ديسمبر
• الأشجار.

القائمة هي مجموعة مرتبة تتكون من عدد متغير من العناصر التي تنطبق عليها عمليات التضمين والاستبعاد. تسمى القائمة التي تعكس علاقة الجوار بين العناصر الخطية. طول القائمة يساوي عدد العناصر التي تحتوي عليها ؛ ويقال أن قائمة الطول الصفري فارغة. القوائم المرتبطة الخطية هي أبسط هياكل البيانات الديناميكية.

من الملائم تصوير الارتباطات بيانياً في القوائم باستخدام الأسهم ، كما هو موضح في القسم الذي يصف المؤشرات. إذا كان أحد عناصر القائمة غير مرتبط بأي عنصر آخر ، فستتم كتابة القيمة التي لا تشير إلى أي عنصر (مؤشر فارغ) في حقل المؤشر. يتم الإشارة إلى مثل هذه الإشارة في باسكال بواسطة Nil ، وفي الرسم التخطيطي يتم الإشارة إليها بواسطة مستطيل متقاطع. يوجد أدناه الهيكل قائمة مرتبطة منفردة(الشكل 11.4
)، بمعنى آخر. ينتقل الاتصال من عنصر في القائمة إلى عنصر آخر في اتجاه واحد... هنا الحقل D هو حقل معلومات يحتوي على بيانات (أي نوع مسموح به في باسكال) ، الحقل N (التالي) هو مؤشر إلى العنصر التالي في القائمة.

يجب أن تحتوي كل قائمة على المؤشرات التالية: العنوان - رأس القائمة ، Cur - العنصر الحالي في القائمة ، وأحيانًا في القوائم المرتبطة بشكل فردي ، يتم استخدام مؤشر الذيل أيضًا - ذيل القائمة (في قائمتين من الروابط يكون كذلك تستخدم دائما). حقل المؤشر الخاص بالعنصر الأخير في القائمة فارغ ؛ يحتوي على علامة خاصة لا شيء ، تشير إلى نهاية القائمة ويُشار إليها بمربع مشطوب.

تختلف القائمة الخطية المرتبطة بشكل مضاعف عن القائمة المرتبطة بشكل فردي من خلال التواجد في كل عقدة من القائمة بمؤشر واحد آخر B (للخلف) يشير إلى العنصر السابق من القائمة (الشكل 11.5).
).

تم وصف بنية البيانات المقابلة لقائمة خطية مرتبطة بشكل مزدوج في باسكال على النحو التالي:

علامة ">

إنشاء قائمة

إضافة عنصر جديد إلى القائمة: في رأس القائمة ، في ذيل القائمة ، بعد العنصر الحالي في القائمة ، قبل العنصر الحالي في القائمة ؛

إزالة عنصر من القائمة ؛

اجتياز القائمة لمعالجتها ؛

البحث عن عقدة في القائمة ؛

طريقة القوة الغاشمة هي نهج مباشر للحل

المهام ، وعادة ما تستند مباشرة إلى بيان المهمة وتعريفات المفاهيم التي تستخدمها.

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

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

من الواضح تمامًا أن وقت تشغيل هذه الخوارزمية يمكن أن يختلف ضمن حدود واسعة جدًا لنفس قائمة الحجم n. في أسوأ الحالات ، أي عندما لا يكون العنصر المطلوب موجودًا في القائمة ، أو عندما يكون العنصر المطلوب هو الأخير في القائمة ، فإن الخوارزمية ستنفذ أكبر عدد من عمليات مقارنة المفاتيح مع جميع عناصر القائمة n: C (n) = n.

1.2 خوارزمية رابين.

خوارزمية رابين هي تعديل للخوارزمية الخطية ، وهي مبنية على فكرة بسيطة للغاية:

"تخيل أنه في الكلمة A بطول m ، فإننا نبحث عن نمط X للطول n. دعنا نقطع "نافذة" بحجم n ونحركها على طول كلمة الإدخال. نحن مهتمون بمعرفة ما إذا كانت الكلمة الموجودة في "النافذة" تطابق النمط المحدد. تأخذ وقتا طويلا لمقارنة الحروف. بدلاً من ذلك ، نقوم بإصلاح بعض الوظائف العددية في الكلمات ذات الطول n ، ثم يتم تقليل المشكلة إلى مقارنة الأرقام ، وهو بلا شك أسرع. إذا كانت قيم هذه الوظيفة على الكلمة في "النافذة" وفي العينة مختلفة ، فلا يوجد تطابق. فقط إذا كانت القيم هي نفسها ، فمن الضروري التحقق من التطابق حرفًا بحرف على التوالي.

تنفذ هذه الخوارزمية تمريرة خطية على طول خط (خطوات n) وتمرير خطي على النص بأكمله (خطوات m) ، وبالتالي فإن إجمالي وقت التشغيل هو O (n + m). في الوقت نفسه ، لا نأخذ في الاعتبار التعقيد الزمني لحساب دالة التجزئة ، لأن جوهر الخوارزمية هو أنه يجب حساب هذه الوظيفة بسهولة بحيث لا يؤثر تشغيلها على التشغيل الكلي للخوارزمية.

تعد خوارزمية رابين وخوارزمية البحث المتسلسل أقل الخوارزميات كثافة في العمل ، لذا فهي مناسبة للاستخدام في حل فئة معينة من المشكلات. ومع ذلك ، فإن هذه الخوارزميات ليست هي الأفضل.

1.3 خوارزمية كنوث - موريس - برات (kmp).

تستخدم طريقة KMP المعالجة المسبقة للسلسلة المطلوبة ، وهي: يتم إنشاء وظيفة البادئة على أساسها. في هذه الحالة ، يتم استخدام الفكرة التالية: إذا كانت البادئة (تُعرف أيضًا باسم اللاحقة) لسلسلة طولها i أطول من حرف واحد ، فهي أيضًا بادئة سلسلة فرعية بطول i-1. وبالتالي ، نتحقق من بادئة السلسلة الفرعية السابقة ، إذا كانت غير متطابقة ، فإن بادئة البادئة الخاصة بها ، إلخ. بهذه الطريقة ، نجد أكبر بادئة مطلوبة. السؤال التالي الذي يستحق الإجابة هو: لماذا يكون وقت تشغيل الإجراء خطيًا ، لأنه يحتوي على حلقة متداخلة؟ حسنًا ، أولاً ، يتم تخصيص وظيفة البادئة بالضبط m مرات ، وبقية الوقت يتغير المتغير k. لذلك ، فإن إجمالي وقت تشغيل البرنامج هو O (n + m) ، أي الوقت الخطي.

والوظيفة التالية: عرض الوظيفة (pos ، path ، w ، h) (var canvas = document.getElementById ("canID") ؛ // الحصول على كائن canvas var ctx = canvas.getContext ("2d") ؛ // it له خاصية - سياق الرسم var x0 = 10 ، y0 = 10 ؛ // موضع الزاوية اليسرى العلوية من قماش الخريطة. العرض = w + 2 * x0 ؛ canvas.height = h + 2 * y0 ؛ // تغيير حجم اللوحة القماشية (أكبر قليلاً من wxh) ctx.beginPath () ؛ // ابدأ في رسم خط متعدد الخطوط ctx.moveTo (x0 + pos.x ، y0 + pos.y) // انتقل إلى المدينة 0 من أجل (var i = 1 ؛ i An مثال على نتيجة استدعاء دالة يجب أن يكون معنى أوامر الرسم واضحًا من أسمائهم وتعليقاتهم في الكود. أولاً ، يتم رسم خط متعدد مغلق (مسار بائع). ثم - دوائر المدن وفوقها لهم - عدد المدن. استخدام الطبقة يرسم، مما يبسط هذا العمل ويسمح لك في نفس الوقت بالحصول على صور بتنسيق svg.

خرق الموقت

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

نسخة الوظيفة (des ، src) (if (des.length! == src.length) des = new Array (src.length) ؛ لـ (var i = 0 ؛ i