Prolog جميع التعبيرات الممكنة لـ x المعطى

Question

لدي برنامج prolog مع قواعد معينة:

sum --> [+], mult, sum | mult | num.
mult --> [*], num, xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] ... etc

لدي تمثيل شجرة مجردة لتعبيراتي.على سبيل المثال: mul(num(2),var(x)) الذي يساوي [*,2,x] صالح.أريد أن أكون قادرًا على إنشاء جميع التعبيرات التي تلبي x والحل المحدد.استخدام

allExpressions(Tree, X, Solution).

على سبيل المثال:

?- allExpressions(Tree, 2, 6)
Tree = mul(num(3),x)
Tree = sum(num(2),mul(num(2),var(x))
etc.

نظرًا لقواعد اللغة الخاصة بي، فمن الواضح أنه لن يكون هناك مجموعة غير محدودة من المعادلات لهذا الغرض.لقد قمت بالفعل ببرمجة evaluation(Tree, X, Solution) الذي يحسب الإجابة بالنظر إلى المتغير X.إذن ما أحتاج إلى المساعدة فيه هو إنشاء مجموعة المعادلات الممكنة لمتغير x والحل المحدد.

أي أفكار حول كيفية التعامل مع هذا؟شكرًا

Answer 1

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

:- use_module(library(clpfd)).

expression(var(x), X, X).
expression(num(N), _, N) :- phrase(num, [N]).
expression(mul(A,B), X, N) :-
        N1 * N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).
expression(sum(A,B), X, N) :-
        N1 + N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).

أترك العمليات الأخرى كتمرين.

مثال للاستعلام وبعض النتائج:

?- expression(Tree, 2, 6).
Tree = mul(var(x), num(3)) ;
Tree = mul(num(2), num(3)) ;
    [...solutions omitted...]
Tree = sum(num(2), mul(num(2), var(x))) ;
Tree = sum(num(2), mul(num(2), num(2))) ;
    [...solutions omitted...]
Tree = sum(sum(num(2), num(2)), num(2)) ;
false.

+1 لاستخدام تمثيل نظيف وغير معيب لأشجار التعبير (var(x), num(N) وما إلى ذلك)، والذي يتيح لك استخدام مطابقة الأنماط عند التفكير في الأمر.