Форум программистов, компьютерный форум, киберфорум
Наши страницы
Prolog
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/14: Рейтинг темы: голосов - 14, средняя оценка - 4.86
WazZzuP
4 / 4 / 1
Регистрация: 23.09.2015
Сообщений: 12
1

Упрощение арифметических выражений

01.06.2010, 21:45. Просмотров 2710. Ответов 6
Метки нет (Все метки)

Буду очень благодарен, если мне помогут разобраться с этой задачей.
В общем нужно упростить арифметическое выражение, критерий простоты - длина выражения. Выражение может включать в себя только атомы, числа, скобки и знаки арифметических операций.
Пробовал делать сам, через предикат replace(...):- write(...), для каждого разного случая, но препод такую работу не принял. Код желательно для Strawberry.

Примеры упрощений:
m * n + k * n --> n * (m + k)
m * n + 3 + k * (-n) --> n * (-k + m) + 3
2 * 3 + 3 * 6 - 4 * 3 + 2 --> 14
2 * x - x * 3 + 34 + (3 * y * 2 + 2) * 6 --> -x + 46 + 36 * y
x + 0 --> x
1 * x --> x
0 * x --> 0
x + x --> 2 * x
5 * x + 6 * x --> 11 * x
3 + 5 * x + 6 * x --> 11 * x + 3
-3 * x + 3 * (4 * y - 3 * x) + 2 --> 12 * (-x + y) + 2
2 * x * (-y) + y * z + 4 --> y * ((- 2) * x + z) + 4
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2010, 21:45
Ответы с готовыми решениями:

Упрощение выражений
Такое задание: Создать процедуру simplify (+Expr,–Result), которая выполняет упрощение выражений,...

Создать список арифметических выражений
Определите предикат p(+List1,+List2,?List3), который из двух списков (возможно разной длины) и ...

Вычислитель арифметических выражений (DCG)
Здравствуйте! Задача тривиальная : нужно реализовать синтаксический анализатор арифметических...

Разбор и вычисление значений арифметических выражений
Реализовать разбор и вычисление значений арифметических выражений, атомы которого — целые 16-ричные...

Программа символьного дифференцирования арифметических выражений. Помогите
Доброго времени суток,задача такая: "Написать программу символьного дифференцирования...

6
Грымзик
2487 / 1462 / 36
Регистрация: 14.09.2009
Сообщений: 2,742
01.06.2010, 22:34 2
Почитайте книгу Сошникова "Парадигма логического программирования", там это есть, насколько я помню.
0
WazZzuP
4 / 4 / 1
Регистрация: 23.09.2015
Сообщений: 12
02.06.2010, 11:44 3
По книжке этой получилась вот такая программа, только она не работает. Числовые выражения считает, но ругается при введении переменной.
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
rule(A*B,B*A).
rule(A+B,B+A).
rule(A+B+C,A+(B+C)).
rule(A*B*C,A*(B*C)).
rule(A*B/C,A*(B/C)).
rule(A*(B+C),A*B+A*C).
rule(A*(B-C),A*B-A*C).
rule(A*B+A*C,A*(B+C)).
rule(A*B-A*C,A*(B-C)).
rule((A+B)*(A-B),A*A-B*B).
rule(A*A-B*B,(A+B)*(A-B)).
rule(A*X+X,(A+1)*X).
rule(X,X).
 
compute(X+Y,Z):- integer(X), integer(Y), Z is X+Y.
compute(X*Y,Z):- integer(X), integer(Y), Z is X*Y.
compute(X-Y,Z):- integer(X), integer(Y), Z is X-Y.
compute(X/Y,Z):- integer(X), integer(Y), Z is X/Y.
compute(1*X,X).
compute(0+X,X).
compute(0*X,0).
compute(X/X,1).
 
expr(Expr,Res):-
    Expr =.. [Op,A,B],
    expr(A,A1),
    expr(B,B1),
    R =.. [Op,A1,B1],
    (compute(R,Res);rule(R,Res)).
expr(X,X):- atomic(X).
 
convert(X,R):- search([X],[R|_]).
search(R,R).
search(P,R):-
    prolong(P,P1),
    search(P1,R,D1).
prolong([X|T],[Y,X|T]):-
    move(X,Y), not(member(Y, [X|T])).
 
cost(X,0):- number(X).
cost(X,1):- atom(X).
cost(X,Z):-
    X =.. [Op,A,B],
    cost(A,CA), cost(B,CB),
    Z is CA+CB+2.
 
simplify(E,R):-
    cost(E,C),
    search([E],C,R,[]).
 
move_grad(E1,E2):- expr(E1,E2), bettereq(E2,E1).
bettereq(E1,E2):- cost(E1,C1), cost(E2,C2), C1=<C2.
better(E1,E2):- cost(E1,C1), cost(E2,C2), C1<C2.
 
filter([],C,[]).
filter([X|T],C,[X|R]):- cost(X,CC), CC<C, !, filter(T,C,R).
filter([X|T],C,R):- filter(T,C,R).
 
search([X|T],C,R,Ban):-
    setof(Z,move_grad(X,Z),L), C1 is C-1, 
    filter(L,C1,L1), L1\=[],
    search(L1,C1,R,[]).
 
search([X|T],C,R,Ban):-
    setof(Z,move_grad(X,Z),L), C1 is C-1,
    filter(L,C1,L1), L1-[],
    appenduniq(T,L,Q),
    removeall(Q,[X|Ban],Res),
    search(Res,C,R,[X|Ban]).
 
search([X],_,X,_).
 
appenduniq(L1,L2,R):- setof(X,(member(X,L1),member(X,L2)),R).
removeall(L,S,R):- setof(X,(member(X,L),not(member(X,S))),R).
 
?- read(X), simplify(X,L), write(L),nl.
0
Грымзик
2487 / 1462 / 36
Регистрация: 14.09.2009
Сообщений: 2,742
02.06.2010, 23:42 4
А эта прога вроде под клубничным и не пойдет. Там же нет предикатов setof и member. И вообще в этой программе много неточностей, некоторые переменные и предикаты не используются, а некоторые наоборот не определены. Мой совет используйте SWI Prolog, там и предикаты нужные уже определены, и выполняется проверка семантики, т.е Вам укажеться место ошибки.
0
Jupiter
Каратель
Эксперт С++
6584 / 4005 / 400
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.11.2012, 01:43 5
Цитата Сообщение от wazzzup Посмотреть сообщение
Prolog
1
Expr =.. [Op,A,B]
=.. - а что это за оператор?
0
Грымзик
2487 / 1462 / 36
Регистрация: 14.09.2009
Сообщений: 2,742
19.11.2012, 21:36 6
Он разбивает терм на функтор и список параметров, например
f(a(b, c), d)=..[f, a(b,c), d]
1
Dude
0 / 0 / 0
Регистрация: 26.11.2009
Сообщений: 9
24.11.2012, 11:33 7
кто может помочь буду при много благодарен очень надо вот задание

Упрощение арифметических выражений

Назовем арифметическим выражением терм, при конструировании ко-торого используются только атомы, числа, скобки и знаки арифметических операций. Напишите программу для упрощения арифметических выражений на SWI-Prologе.
В целом, задача упрощения выражений является достаточно сложной и в каком-то смысле неконкретизованной, т. к. единого верного решения для этой задачи нет. Если арифметическое выражение имеет несколько вариантов более простого представления, то какой из них выбрать в качестве решения? Это зависит от того, для каких целей нам необходимо упрощение.
Задачу упрощения выражения поставим следующим образом. Необхо-димо найти эквивалентное выражение, форма записи которого является более короткой, чем форма записи исходного выражения. Для упрощения выраже-ний используйте различные рекурсивные "правила переписывания", каждое из которых "упрощает" какое-нибудь подвыражение в исходном выражении. Правила переписывания должны соответствовать обычным математическим преобразованиям, как-то: приведению подобных и т. п., и представляются правилами Пролога (см. программу "дифференцирование выражений" из кур-са лекций).
Ваша программа должна быть некоторым компромиссом между жела-тельной простотой написания и той сложностью, которой от нее требует по-ставленная задача.
0
24.11.2012, 11:33
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.11.2012, 11:33

Упрощение выражений
Извините за трату времени , но прошу вас помочь. Дали пример по логике , но слишком много зачётов и...

Упрощение выражений
При помощи каких законов упрощаются данные выражения(фото в приложении).

Упрощение выражений на Lisp
Здравствуйте, уважаемые профессионалы и начинающие специалисты! Появилась необходимость в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.