مرحباً أيها السكان ، لقد حان الوقت للحديث عن البرمجة التعريفية. هذا عندما تم فرك في المعهد أنه لا يمكن ترميز البرامج ، ولكن صياغتها. هذا هو عكس الحتمية ، والتي هي الآن في جميع لغات البرمجة. دعونا نشيد بالنهج الوظيفي ، إنه أخوي هنا ، وهو يقوم بعمله بشكل أعمق وأعمق في الحداثة ، هنا لديك لامدا في C ++ وجافا سكريبت ، ربما هاسكل؟
لكن الشيء المحزن هو البرمجة المنطقية والمنتجة التي لا يمكن تمثيلها إلا في Prolog .
سأقوم هنا برمي فكرة مثيرة للاهتمام عن تأثير الحب. لماذا لا تكتب مقالا حول حل مشكلة البرمجة. لذا ، أعتقد أن الكثير من المشاركات قد ظهرت. أنضم إلى اختيار المواضيع. فيما يلي اتجاه أصلي جديد للتنمية والمنافسة بين المشاركين ، نوضح كيف يمكننا بالضبط حل المشاكل ، بحيث يهتم جميع القراء بالتعبير عن آرائهم والإشارة إلى أخطائك ، لأن لديك ما يكفي من المتخصصين في جافا سكريبت و C ++ ، ربما pythognose لا تزال تأتي ...
بشكل عام ، الغرض من المقالة : حل مشكلة لم تكن معروفة حتى الآن في بداية المشاركة وإظهار كود تفكيرك ، في وقت كتابة المقال ، والتأكيد على ذلك من خلال الدورة التدريبية وحل العمل الذي تم تلقيه. ولكن لهذا الاختيار تحتاج إلى حكم ، فأنت بنفسك لا تراجع نفسك. سأختار leetcode.com في هذا الدور.
1. لذا
هنا نختار المهمة الأقرب إلى الأصعب ، ونحاول حلها على Prolog ، نحتاج إلى إظهار مدى الترفيه.
2. المهمة 44. مطابقة أحرف البدل
بالنظر إلى سلسلة (سلاسل) الإدخال والنمط (p) ، قم بتطبيق مطابقة حرف البدل مع دعم '؟' و "*".
"؟" يطابق أي حرف مفرد.
يطابق '*' أي تسلسل من الأحرف (بما في ذلك التسلسل الفارغ).
يجب أن تغطي المطابقة سلسلة الإدخال بالكامل (وليس جزئيًا).
ملحوظة:
يمكن أن تكون s فارغة وتحتوي على أحرف صغيرة فقط az.
يمكن أن تكون p فارغة وتحتوي فقط على أحرف صغيرة az وحروف مثل؟ أو *.
مثال 1:
الإدخال:
ق = "أأ"
ع = "أ"
الإخراج: خطأ
Explanation: "a" لا يتطابق مع السلسلة "aa" بالكامل.
مثال 2:
الإدخال:
ق = "أأ"
ص = '*'
الإخراج: صحيح
Explanation: "*" يطابق أي تسلسل.
مثال 3:
الإدخال:
ق = "cb"
ع = "؟ أ"
الإخراج: خطأ
التفسير: "؟" يتطابق مع "c" ، لكن الحرف الثاني هو "a" ، ولا يطابق "b".
مثال 4:
الإدخال:
ق = "adceb"
ع = "* أ * ب"
الإخراج: صحيح
Explanation: أول "نجمة" يطابق التسلسل الفارغ ، بينما الثاني * يتطابق مع السلسلة الفرعية "dce".
مثال 5:
الإدخال:
ق = "acdcb"
ع = "أ * ج؟ ب"
الإخراج: خطأ
3. هذه هي الخطوة
نجاح باهر))) (يعذرني المشرفون) ، كانت هناك مهمة يلزم فيها تنفيذ المسند. المعجزات ، لست مضطرًا حتى لإجراء أي إدخال / إخراج ، الأمر الذي قد يكون صعبًا في مثل هذه البيئة. عند المدخلات ، أنواع بسيطة ؛ عند الإخراج ، منطقية. ابتدائي.
أثناء طرح أيقونات الاقتباس ، تعرفت لفترة وجيزة على المهمة ، لدينا آلة حالة محدودة ، وهناك سلسلة من الشخصيات ، إنه قالب ، نحتاج إلى تجاوزه وإجراء فحص ، وتجاوز الرسم البياني للحالة حتى إذا وصلنا إلى نهاية القمة ، فإن الإجابة صحيحة. هذه هي مهمة البحث العكسي.
ثم تابع ، أكتب على الفور مسودة هنا ، ثم سأعرض نسخة عمل:
سطر ... في المقدمة ، نوع البيانات المهم هو قائمة ، إنه مفهوم تعاودي ، موصوف بشكل معلن ، لذلك تحتاج إلى العمل معه ، تحتاج إلى تحويل السلاسل إلى قوائم الذرات. بالمناسبة ، الذرة ليست مجرد رمز ، على الرغم من أنها أيضًا ، الذرة هي سلسلة بحرف صغير بدون مسافات ، لأن Prolog عبارة عن ثوابت سلسلة ولا يمكنك وضع أي اقتباسات.
atom_to_list('',[]). %- atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %- ,
آسف لغتي الإنجليزية ، سوف نتحقق منها في أفضل بيئة في الوقت الحاضر ، swi-prolog.org ، هناك محرر عبر الإنترنت ، هنا:
عفوًا. هذا هو ما يعنيه عدم خداع أي شخص ، إنه عتبة عالية للدخول ، المكالمات إلى مسندات المكتبة ليست صحيحة. نحن نبحث عن المسندات المضمنة الصحيحة للعمل مع الذرات.
وفي الصورة ، هناك رسالة مفادها أن المتغير H تبين أنه غير مطلوب ، وبعض العيوب في المنطق ، ورأس القائمة هو الحرف الأول ، ويجب أن يكون مكانه Ch .
فيما يلي بعض الوثائق:
atom_concat (؟ Atom1 ،؟ Atom2 ،؟ Atom3)
تشكل Atom3 سلسلة من Atom1 و Atom2. يجب إنشاء نسختين على الأقل من الحجج للذرات. يسمح هذا المسند أيضًا للوضع (- ، - ، +) ، غير تقسيم حتمية> الوسيطة الثالثة إلى جزأين (كما يفعل الملحق / 3 للقوائم). يسمح SWI-Prolog بالحجج الذرية. يجب أن يستخدم الكود المحمول atomic_concat / 3 إذا كانت هناك وسيطات غير ذرية.
atom_length (+ Atom ، -Length)
صحيح إذا كانت Atom ذرة من أحرف الطول. يقبل إصدار SWI-Prolog جميع الأنواع الذرية ، بالإضافة إلى قوائم الرموز وقوائم الشخصيات. يجب أن يتجنب الرمز الجديد هذه الميزة ويستخدم write_length / 3 للحصول على عدد الأحرف التي ستتم كتابتها إذا تم تسليم الوسيطة إلى write_term / 3.
3.1 الذرة في قائمة الذرات
مثل هذا
3.2 آلة الدولة نفسها
تخيل رسمًا بيانيًا يقرأ الأحرف من القالب ويتحقق من الامتثال للأحرف في سطر الإدخال. مسودة الحلول:
%InpitList, PattList test_pattrn([],[]). %- test_pattrn([Ch|UnpTail],[Ch|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn([],['*'|PatTail]):-test_pattrn([],PatTail).
دعونا نجعل الواجهة النهائية:
isMatch (S، P): - atom_to_list (S، SL)، atom_to_list (P، PL)،!، test_pattrn (SL، PL)،!.
فيما يلي جميع الأمثلة من بيان المشكلة:
4. محكم
يبدو أن القرار جاهز ، والآن ننتقل إلى الحكم. على موقع leetcode.com (نعم ، نعم ، نحل المشكلة رقم 44) ، وسوف نتلقى اختبارات ، وسنحاول تنفيذها بالتتابع مع التنفيذ. حظ واحد سيئ ، أنهم لا يقبلون برامج في Prolog .
لا شيء ، سنحصل على كل المهام واحدة تلو الأخرى:
class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ if s=="aa" and p=="a":return False if s=="aa" and p=="*":return True if s=="cb" and p=="?a":return False if s=="adceb"and p=="*a*b":return True if s=="acdcb" and p=="a*c?b":return False if s=="aab" and p=="c*a*b":return False if s=="mississippi" and p=="m??*ss*?i*pi":return False if s=="aa" and p=="aa":return True if s=="aaa" and p=="aa":return False if s=="aa" and p=="a*":return True if s=="ab" and p=="?*":return True if s=="a" and p=="a":return True if s=="a" and p=="aa":return False if s=="aa" and p=="aaa":return False if s=="abefcdgiescdfimde" and p=="ab*cd?i*de":return True if s=="zacabz" and p=="*a?b*":return False if s=="leetcode" and p=="*e*t?d*":return False if s=="missingtest" and p=="mi*ing?s*t":return False if s=="aaaa" and p=="***a":return True if s=="" and p=="":return True if s=="" and p=="*":return True if s=="" and p=="a":return False if s=="" and p=="?":return False if s=="a" and p=="":return False if s=="a" and p=="a*":return True if s=="a" and p=="?*":return True if s=="a" and p=="*":return True if s=="b" and p=="?":return True if s=="b" and p=="??":return False if s=="bc" and p=="??":return True if s=="bcd" and p=="??":return False if s=="b" and p=="?*?":return False if s=="b" and p=="*?*?":return False if s=="b" and p=="*?*?*":return False if s=="c" and p=="*?*":return True if s=="cd" and p=="*?":return False if s=="cd" and p=="?":return False if s=="de" and p=="??":return True if s=="fg" and p=="???":return False if s=="hi" and p=="*?":return True if s=="ab" and p=="*a":return False if s=="aa" and p=="*a":return True if s=="cab" and p=="*ab":return True if s=="ab" and p=="*ab":return True if s=="ac" and p=="*ab":return False if s=="abc" and p=="*ab":return False if s=="cabab" and p=="ab*":return True if s=="cabab" and p=="*ab":return True if s=="ab" and p=="ab":return True if s=="ab" and p=="*?*?*":return True if s=="ac" and p=="ab":return False if s=="a" and p=="ab":return False if s=="abc" and p=="ab":return False if s=="" and p=="ab*":return False if s=="a" and p=="ab*":return False if s=="ab" and p=="ab*":return True if s=="ac" and p=="ab*":return False if s=="abc" and p=="ab*":return True if s=="" and p=="*a*":return False if s=="a" and p=="*a*":return True if s=="b" and p=="*a*":return True
فيما يلي قائمة بالاختبارات ، حاول شخص ما بجد من خلال تقديم قائمة مراجعة لهذه المشكلة.
وهذه ليست كل الاختبارات حتى نتوقف:
إليك البرنامج النهائي ، بالإضافة إلى بعض الاختبارات:
%- atom_to_list('',[]). %- , atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). is_letter(X):-X@>=a, X@=<z. %InpitList, PattList test_pattrn([],[]). %- test_pattrn([Ch|UnpTail],[Ch|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework assert_are_equal(Goal, false):-not(Goal),!,writeln(Goal->ok). assert_are_equal(Goal, true):-Goal,!,writeln(Goal->ok). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %main goal :-assert_are_equal(isMatch(aa,a),false). :-assert_are_equal(isMatch(aa,'*'),true). :-assert_are_equal(isMatch(cb,'?a'),false). :-assert_are_equal(isMatch(adceb,'*a*b'),true). :-assert_are_equal(isMatch(acdcb,'a*c?b'),false). :-assert_are_equal(isMatch(aab,'c*a*b'),false). :-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false). :-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true). :-assert_are_equal(isMatch(zacabz,'*a?b*'),false). :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false). :-assert_are_equal(isMatch(aaaa,'***a'),true). :-assert_are_equal(isMatch(b,'*?*?*'),false).
فيما يلي نتائج الاختبار:
isMatch(aa, *)->ok isMatch(cb, ?a)->ok isMatch(adceb, *a*b)->ok isMatch(acdcb, a*c?b)->ok isMatch(aab, c*a*b)->ok isMatch(mississippi, m??*ss*?i*pi)->ok isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok isMatch(zacabz, *a?b*)->ok isMatch(leetcode, *e*t?d*)->ok isMatch(aaaa, ***a)->ok isMatch(b, *?*?*)->ok true
5. الخلاصة
برولوج مثل تمرين للعقل. من المضحك حل المشكلات ، على الرغم من أن هذا الحل لم يكن لديه أي تحسين. تبين أن الحصول على اختبارات أكثر تعقيدًا يدويًا أمر شاق للغاية ، حتى الآن لم يكن من الممكن إثبات اكتمال الحل. ويبدو لي أنني وصلت بالفعل إلى حجم مقال هابر.
على أي مثال فشل هذا القرار؟
كيف تحب دعوتي سكان حبر؟
يمكنك التنافس عن طريق جعل عقلك يحل المشاكل ويظهر حلولًا مثيرة للاهتمام ، لأن البرمجة عملية إبداعية.