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

المهمة 391. الكمال مستطيل

بالنظر إلى المستطيلات المحاذية للمحور N حيث N> 0 ، حدد ما إذا كانت جميعها معًا تشكل غطاءً دقيقًا لمنطقة مستطيلة.
يتم تمثيل كل مستطيل كنقطة أسفل اليسار ونقطة أعلى اليمين. على سبيل المثال ، يتم تمثيل مربع الوحدة بـ [1،1،2،2]. (إحداثية النقطة السفلية اليسرى هي (1 ، 1) والنقطة العلوية اليمنى هي (2 ، 2)).

مثال 1: المستطيلات = [
[1،1،3،3]
[3،1،4،2]
[3،2،4،4]
[1،3،2،4]
[2،3،3،4]]
عودة صحيح. تشكل المستطيلات الخمسة جميعها غطاءً دقيقًا لمنطقة مستطيلة.
...
مثال 3: المستطيلات =
[[1،1،3،3]
[3،1،4،2]
[1،3،2،4]
[3،2،4،4]]
عودة كاذبة. لأن هناك فجوة في المركز العلوي.

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

يتم تمثيل البيانات الأولية بقائمة ، وأذكرك بإيجاز ، القائمة هي [Head | Tail] ، حيث Tail عبارة عن قائمة ، وأيضًا القائمة فارغة [] .

نحن صياغة 1

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

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

مثل هذا:

findsum([], Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T], Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectList):- mincon(Lx:Ly,LConerCur,LConerCur2), maxcon(Rx:Ry,RConerCur,RConerCur2), Scur2 is Scur+(Rx-Lx)*(Ry-Ly), not(chekin([Lx,Ly,Rx,Ry],RectList)), findsum(T, Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,[[Lx,Ly,Rx,Ry]|RectList]). 

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

لذلك:

 %   mincon(X1:Y1,X2:Y2,X1:Y1):-X1=<X2,Y1=<Y2,!. mincon(_,X2:Y2,X2:Y2). %  maxcon(X1:Y1,X2:Y2,X1:Y1):-X1>=X2,Y1>=Y2,!. maxcon(_,X2:Y2,X2:Y2). 

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

وكما اتضح فيما بعد ، فإن أهم شيء هو التحقق من عدم تقاطع المستطيلات ، فهي تتراكم في القائمة:

 %    chekin(X,[R|_]):-cross(X,R),!. chekin(X,[_|T]):-chekin(X,T). %     ,    cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). %,       cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11<Y22,Y22=<Y12,!.%rt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11<Y22,Y22=<Y12,!.%lt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11=<Y21,Y21<Y12,!.%rb cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11=<Y21,Y21<Y12. %lb 

تقاطع المستطيلات ، هذه أربعة خيارات لضرب الجزء العلوي الأول داخل الآخر.

والبيان الختامي:

 isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= (RconerX-LconerX)*(RconerY-LconerY). 

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

بعد ذلك ، أقوم بتشغيل هذا التطبيق في الاختبارات الحالية ، وأقتبس أول 40:

 %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]),true). :-assert_are_equal(isRectangleCover([[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[0,0,4,1]]),false). 

 :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[4,0,5,1],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[2,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,3,2],[1,0,2,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[0,3,1,4]]),true). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[2,0,3,1],[3,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,2,2],[1,1,3,3],[2,0,3,1],[0,3,3,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[1,0,2,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[2,2,4,4],[4,1,5,4],[1,3,2,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,2,1],[1,0,2,1],[0,2,2,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,2,1],[0,1,2,2],[0,2,1,3],[1,0,2,1]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[0,1,1,2],[1,0,2,1],[0,2,3,3],[2,0,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,4],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,3],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,5,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,2,1,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,4,4],[1,3,4,5],[1,6,4,7]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[2,0,3,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[1,1,2,2],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[2,1,3,2],[2,1,3,2],[2,1,3,2],[3,1,4,2]]),false). :-assert_are_equal(isRectangleCover([[0,1,2,3],[0,1,1,2],[2,2,3,3],[1,0,3,1],[2,0,3,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,2,1,3],[1,1,2,2],[2,0,3,1],[2,2,3,3],[1,0,2,3],[0,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[1,0,2,1],[1,0,2,1],[1,2,2,3],[2,0,3,1],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[-1,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[1,0,3,1],[3,0,4,1]]),false). :-assert_are_equal(isRectangleCover([[1,2,4,4],[1,0,4,1],[0,2,1,3],[0,1,3,2],[3,1,4,2],[0,3,1,4],[0,0,1,1]]),true). 

وهذه ليست النهاية ، المهمة من القسم "الصعب" ، في 41 اختبارًا ، تعرض قائمة من 10000 مستطيل ، في جميع الاختبارات الخمسة الأخيرة ، أحصل على مثل هذه الأوقات بالثواني:

 test 41:length=10000 goal->ok:212/sec test 42:length=3982 goal->ok:21/sec test 43:length=10222 goal->ok:146/sec test 44:length=10779 goal->ok:41/sec test 45:length=11000 goal->ok:199/sec 

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

الصياغة 2

الطريقة السابقة ، باستخدام القائمة لتجميع الأرقام ، تبين أنها غير فعالة للغاية ، وهذا التغيير يوحي بحد ذاته - بدلاً من التعقيد n ^ 2 ، اجعل n * log (n). يمكنك استخدام الشجرة للتحقق من التقاطعات في قائمة المستطيلات.

الشجرة الثنائية لـ Prolog هي أيضًا مصطلح منظم ، وكقائمة يتم تحديدها بشكل متكرر ، تكون الشجرة فارغة أو تحتوي على قيمة وشريحتين فرعيتين .

أستخدم دالات ثلاثية لهذا: t (LeftTree و RootValue و RightTree) ، وستكون الشجرة الفارغة [].

يمكن التعبير عن شجرة بسيطة من الأرقام ، مع ترتيب على اليسار أصغر وعلى اليمين كبير ، كما يلي:

 add_to_tree(X,[],t([],X,[])). add_to_tree(X,t(L,Root,R),t(L,Root,NewR)):- X<Root,!,add_to_tree(X,R,NewR). add_to_tree(X,t(L,Root,R),t(NewL,Root,R)):- add_to_tree(X,L,NewL). 

في الكتاب الكلاسيكي لـ I. Bratko "Programming in Prolog for الذكاء الاصطناعي" ، يتم إعطاء العديد من إنجازات الأشجار 2-3 ، متوازنة مع AVL ، ...

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

 righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. 

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

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). 

تؤخذ على الفور في الاعتبار آخر خدعة ميزة ، إذا كانت المستطيلات لها نفس العرض ، وكان لها وجه مشترك ، فيمكن دمجها في واحدة وعدم إضافتها إلى الشجرة ، ولكن ببساطة تغيير حجم المستطيل في عقدة واحدة. اختبار 41 يدفع من أجل هذا ، هناك مثل هذه البيانات هي: [[0 ، -1،1،0] ، [0،0،1،1] ، [0،1،1،2] ، [0،2،1 ، 3] ، [0،3،1،4] ، [0،4،1،5] ، [0،5،1،6] ، [0،6،1،7] ، [0،7،1 ، 8] ، [0،8،1،9] ، [0،9،1،10] ، [0،10،1،11] ، [0،11،1،12] ، [0،12،1 ، 13] ، [0،13،1،14] ، ... ، [0،9998،1،9999]].

نحن نجمع بين هذه التحسينات والحل السابق ، وأعطيه بالكامل ، مع بعض التحسينات:

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. findsum([],Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T],Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectTree):- coner(Lx:Ly,LConerCur,=<,LConerCur2), coner(Rx:Ry,RConerCur,>=,RConerCur2), Scur2 is Scur+abs(Rx-Lx)*abs(Ry-Ly), treechk([Lx,Ly,Rx,Ry],RectTree,RectTree2),!, findsum(T,Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,RectTree2). isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= abs(RconerX-LconerX)*abs(RconerY-LconerY). coner(X1:Y1,X2:Y2,Dir,X1:Y1):-apply(Dir,[X1,X2]),apply(Dir,[Y1,Y2]),!. coner(_,XY,_,XY). cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). cross2([X11,Y11,X12,Y12],[_,_,X22,Y22]):-X11<X22,X22=<X12, Y11<Y22,Y22=<Y12,!. %right-top cross2([X11,Y11,X12,Y12],[X21,_,_,Y22]):-X11=<X21,X21<X12, Y11<Y22,Y22=<Y12,!. %left-top cross2([X11,Y11,X12,Y12],[_,Y21,X22,_]):-X11<X22,X22=<X12, Y11=<Y21,Y21<Y12,!. %right-bottom cross2([X11,Y11,X12,Y12],[X21,Y21,_,_]):-X11=<X21,X21<X12, Y11=<Y21,Y21<Y12. %left-bottom 

فيما يلي وقت إجراء الاختبارات "الثقيلة":

 goal-true->ok:0/sec 41:length=10000 goal-true->ok:0/sec 42:length=3982 goal-true->ok:0/sec 43:length=10222 goal-true->ok:2/sec 44:length=10779 goal-false->ok:1/sec 45:length=11000 goal-true->ok:1/sec 

سأنهي هذا التحسين ، وكل الاختبارات تمر بشكل صحيح ، والوقت مرض. المهتمين ، أقترح عليك أن تجرب عبر الإنترنت أو هنا .

في المجموع

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

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

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