Графы и деревья

@IAmI · Регистрация: 10.05.2009

Студворк — интернет-сервис помощи студентам

Доброго времени суток!

Столкнулась с проблемой при решении задач:
1) Найти все вершины направленного графа, от которых недостижима заданная
2) Найти в дереве все отрицательные элементы и заменить их максимальным элементом

Заранее благодарю за помощь

@Грымзик · 22.12.2010, 19:53

1) На форуме часто встречается поиск в пространстве состояний, найдите поиск в глубину, и тогда решение будет
все_недостижимые_вершины(Начальная,Списо к):-findall(Вершина, not(поиск_в_глубину(Начальная,Вершина,_) ),Список).
2)

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
change(Tree,NewTree):-max(Tree,Max), change(Tree,NewTree,Max).
 
change(nil,nil,_).
change(t(A,Left,Right),t(Max,NewLeft,NewRight),Max):-A<0,!,
    change(Left,NewLeft,Max),change(Right,NewRight,Max).
change(t(A,Left,Right),t(A,NewLeft,NewRight),Max):-
    change(Left,NewLeft,Max),change(Right,NewRight,Max).
 
max(t(A,nil,nil),A):-!.
max(t(A,Left,Right),A):-max(Left,L),max(Right,R),A>L,A>R,!.
max(t(_,Left,Right),L):-max(Left,L),max(Right,R),L>R,!.
max(t(_,_,Right),R):-max(Right,R).

@IAmI · 22.12.2010, 20:05 **[ТС]**

Большое спасибо)

@IAmI · 24.12.2010, 00:18 **[ТС]**

Начала вникать и поняла, что не понимаю смысла строки:

Сообщение от Грымзик

max(t(A,nil,nil),A)

.

nil это что?

@Грымзик · 24.12.2010, 01:06

nil - это пустое дерево. Т.е если узел дерева является листом, то он описывается как t(значение_узла,nil,nil). И своим вопросом Вы навели меня на мысль, что я ошиблась

Если будет узел с одним сыном, то возникнет ошибка.

Prolog
1
2
3
4
max(nil,-1000):-!. %предположим, что все элементы дерева больше -1000
max(t(A,Left,Right),A):-max(Left,L),max(Right,R),A>L,A>R,!.
max(t(_,Left,Right),L):-max(Left,L),max(Right,R),L>R,!.
max(t(_,_,Right),R):-max(Right,R).

@IAmI · 24.12.2010, 02:25 **[ТС]**

Сообщение от Грымзик

nil - это пустое дерево

просто я обозвала его другим словом, что и потянуло за собой ошибку

Сообщение от Грымзик

Код Prolog
1
2
3
4
max(nil,-1000)

. %предположим, что все элементы дерева больше -1000
max(t(A,Left,Right),A):-max(Left,L),max(Right,R),A>L,A>R,!.
max(t(_,Left,Right),L):-max(Left,L),max(Right,R),L>R,!.
max(t(_,_,Right),R):-max(Right,R).

По какой причине компилятор может ругаться на А - свободная переменная? те неопределенная

Добавлено через 35 минут
Разобралась вроде как с А. Теперь вылез хвост про:

Prolog
1
2
change(t,t)
change(t,t,integer)

Потому, как

Prolog
1
change(nil,nil,_).

тогда ошибочен. Как же тогда переписать?

@Грымзик · 24.12.2010, 02:31

Выложите код целиком.

@IAmI · 24.12.2010, 02:34 **[ТС]**

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
domains
        list = integer*.
        treetype = der(integer, treetype,treetype); empty
 
predicates
 
        otobr(treetype).       
  
    max(treetype,integer)
    change(treetype,treetype)
    change(treetype,treetype,integer)
            
        treeresult(treetype)
      
clauses
 
/* Отображение дерева */
        otobr(empty).
        otobr(der(X,L,R)):- otobr(L),write(L," ",X," ",R),nl, otobr(R).
    
/*Максимальный элемен*/
 
    max(empty,-1000):-!.
    max(der(A,Left,Right),A):-max(Left,L),max(Right,R),A>L,A>R,!.
    max(der(_,Left,Right),L):-max(Left,L),max(Right,R),L>R,!.
    max(der(_,_,Right),R):-max(Right,R).
 
/*Замена элементов*/
    change(Tree,NewTree):-max(der(X,L,R),Max), change(Tree,NewTree,Max).
 
    change(empty,empty,0).
    change(der(A,Left,Right),der(Max,NewLeft,NewRight),Max):-A<0,!,
        change(Left,NewLeft,Max),change(Right,NewRight,Max).
    change(der(A,Left,Right),der(A,NewLeft,NewRight),Max):-
        change(Left,NewLeft,Max),change(Right,NewRight,Max).
  
 
    /* Вычисление результата */     
    treeresult(Tr):-                                    
             max(Tr,L),
             write("Максимальный элемент \n",L),
             change(Tr,Tk,A),
             write("\n Дерево \n"),write(Tk).
 
 
                
goal
    clearwindow,  
 
    treeresult(der(5,
                der(7,
                      der(-5,empty,empty),
                      der(10,empty,empty)),
                der(9,
                      der(-1,empty,empty),
                      der(18,empty,empty))
                ) 
               ),nl,    
 
    nl.

Сейчас все отрицательные заменяются на 0

@Грымзик · 24.12.2010, 02:42

Из-за этого правила change(empty,empty,0) предикат change завершиться удачно, только если максимальный элемент был нулем, или же если третий параметр при вызове был не определен. Что как раз у Вас и наблюдается. В change(Tr,Tk,A) переменная A не определена.

@IAmI · 24.12.2010, 02:56 **[ТС]**

Тогда просто можно было бы вызвать change(Tree,NewTree) и не определять А, но при этом опять ошибка. Хотя как такового значения А не требуется

@Грымзик · 24.12.2010, 03:05

Не понимаю что там у Вас за проблемы. Поправьте на change(empty,empty,_) и change(Tr,Tk,L). У меня все нормально работает.

@IAmI · 24.12.2010, 03:23 **[ТС]**

При запуске возникает предупреждение в строке change(empty,empty,_)
А результат работы в виде:

Prolog
1
2
3
4
5
6
7
8
der(5,
                der(7,
                      der(_,empty,empty),
                      der(10,empty,empty)),
                der(9,
                      der(_,empty,empty),
                      der(18,empty,empty))
                )

@Грымзик · 24.12.2010, 03:42

Не знаю, у меня все нормально. Попробуйте стереть change с двумя параметрами, он все равно не используется.

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@IAmI 0 / 0 / 0 Регистрация: 10.05.2009 Сообщений: 9

	Графы и деревья 22.12.2010, 19:32. Показов 2625. Ответов 12 Метки нет (Все метки) Доброго времени суток! Столкнулась с проблемой при решении задач: 1) Найти все вершины направленного графа, от которых недостижима заданная 2) Найти в дереве все отрицательные элементы и заменить их максимальным элементом Заранее благодарю за помощь 0

@IAmI 0 / 0 / 0 Регистрация: 10.05.2009 Сообщений: 9
	22.12.2010, 20:05 [ТС]
	Большое спасибо) 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	24.12.2010, 02:31
	Выложите код целиком. 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	24.12.2010, 02:42
	Из-за этого правила change(empty,empty,0) предикат change завершиться удачно, только если максимальный элемент был нулем, или же если третий параметр при вызове был не определен. Что как раз у Вас и наблюдается. В change(Tr,Tk,A) переменная A не определена. 0

@IAmI 0 / 0 / 0 Регистрация: 10.05.2009 Сообщений: 9
	24.12.2010, 02:56 [ТС]
	Тогда просто можно было бы вызвать change(Tree,NewTree) и не определять А, но при этом опять ошибка. Хотя как такового значения А не требуется 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	24.12.2010, 03:05
	Не понимаю что там у Вас за проблемы. Поправьте на change(empty,empty,_) и change(Tr,Tk,L). У меня все нормально работает. 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	24.12.2010, 03:42
	Не знаю, у меня все нормально. Попробуйте стереть change с двумя параметрами, он все равно не используется. 0