> 1 <

Автор Сообщение

Кира

Members


Статус

25 сообщений

Где: Russia
Род занятий:
Возраст:

#1683   2010-03-26 15:33 GMT+3 часа(ов)      
1.Как сделать включение/удаление/замену данных! Работать с файлом! Дело в том, что добавление новых данных делается в начало документа вместо первой записи, а не просто в конец!

2.Дан некоторый связный неориентированный граф. Необходимо найти в нём центральную вершину (наиболее равноудалённую ото всех остальных). Наиболее равноудалённая вершина может быть получена как вершина, среднее расстояние от которой до других вершин наиболее близко к среднему значению этой величины для всех вершин графа. Если таких вершин несколько, вывести их все.

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1684   2010-03-26 17:27 GMT+3 часа(ов)      
И в какой прикажете из копий Вашей темы Вам отвечать?

misha

Moderators


Статус

1275 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#1685   2010-03-26 18:10 GMT+3 часа(ов)      
Цитата
Кира :
Дело в том, что добавление новых данных делается в начало документа вместо первой записи, а не просто в конец!
Какой диалект лиспа? Приведите пример.

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1687   2010-03-26 23:31 GMT+3 часа(ов)      
> расстояние от которой до других вершин
А если есть несолько путей разной длины из этой вершины до некоторой другой, то какой нужно брать путь (что вообще понимать под расстоянием)? В условии у ребер есть длина?

Кира

Members


Статус

25 сообщений

Где: Russia
Род занятий:
Возраст:

#1688   2010-03-27 00:53 GMT+3 часа(ов)      
Отвечать любой!
Длины в условиях нет!
Common Lisp

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1689   2010-03-27 02:12 GMT+3 часа(ов)      
> Отвечать любой!
Лучше удалите лишние, так будет удобнее использовать форум.

> Длины в условиях нет!
Т.е. расстояние между соседними вершинами считать за единицу? А что насчет выбора пути если их несколько (см. выше), какой брать: максимальный или минимальный или еще какой?

Кира

Members


Статус

25 сообщений

Где: Russia
Род занятий:
Возраст:

#1691   2010-03-27 12:54 GMT+3 часа(ов)      
Думаю брать за 1!
над 2 вопросом подумаю!

Кира

Members


Статус

25 сообщений

Где: Russia
Род занятий:
Возраст:

#1697   2010-03-27 23:50 GMT+3 часа(ов)      
А что делать с БД? Как в Common Lisp добавлять/удалять и заменять данные?
Я думала про добавление так: в конце документа ставить предположим @ и затем читать документ, как только встречаем @ на её место вставлять новые данные, но у меня не получилось! Делала через COND,EQUAL

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#1749   2010-03-31 19:20 GMT+3 часа(ов)      
Задача интересная.
(defun F (Net)
((lambda (enum counter)
((lambda (averages)
((lambda (mid)
((lambda (deviations)
(EXTRACT_MIN (apply 'min deviations) deviations enum))
(mapcar
#'(lambda (dist)
(abs (- dist mid)))
averages)))
(/ (apply '+ averages) counter)))
(mapcar
#'(lambda (node)
(/
(apply '+
(mapcar
#'(lambda (other)
(DIJKSTRA Net node other))
(remove node enum :test 'EQUAL)))
(1- counter)))
enum)))
(mapcar 'car Net)
(length Net)))

(defun EXTRACT_MIN (minimal deviations enum)
(if deviations
((lambda (test result)
(if test (cons (car enum) result) result))
(equal (car deviations) minimal)
(EXTRACT_MIN minimal (cdr deviations) (cdr enum)))))

(defun DIJKSTRA (Net Init Term
&optional (Tmp nil) (Fix (list (cons Init 0))))
((lambda (fix_label fix_value)
(if (equal fix_label Term) fix_value
(apply
#'(lambda (newTmp newFix)
(DIJKSTRA Net Init Term newTmp newFix))
(TRANSFER_MIN
(UPDATE_Tmp Tmp Fix (cdr (assoc fix_label Net)))
Fix))))
(caar Fix)
(cdar Fix)))

(defun UPDATE_Tmp (Tmp Fix Links)
(if Links
((lambda (link_label link_value)
(UPDATE_Tmp
(if (assoc link_label Fix :test 'EQUAL) Tmp
((lambda (link mark)
(if link
(subst
(cons link_label (min mark (cdr link)))
link
Tmp
:test 'EQUAL)
(cons (cons link_label mark) Tmp)))
(assoc link_label Tmp :test 'EQUAL)
(+ link_value (cdar Fix))))
Fix
(cdr Links)))
(caar Links)
(cdar Links))
Tmp))

(defun TRANSFER_MIN (Tmp Fix)
(if Tmp
(if (cdr Tmp)
(apply
#'(lambda (elem newTmp newFix)
(if (< (cdr elem) (cdar newFix))
(list
(cons (car newFix) newTmp)
(cons elem (cdr newFix)))
(list
(cons elem newTmp)
newFix)))
(cons (car Tmp) (TRANSFER_MIN (cdr Tmp) Fix)))
(list
(cdr Tmp)
(cons (car Tmp) Fix)))
(list Tmp Fix)))

Сеть связывается с формальным параметром Net и представлена списком списков связей узлов в следующем виде:
((узел (связанный_узел . длина_дуги)...)...)
Например, для сети
(setq Net
'((1 (2 . 4)(3 . 7))
(2 (1 . 4)(3 . 3)(6 . 1))
(3 (1 . 7)(2 . 3)(4 . 2)(5 . 5))
(4 (3 . 2)(5 . 1)(6 . 7))
(5 (3 . 5)(4 . 1)(6 . 3))
(6 (2 . 1)(4 . 7)(5 . 3))))
вызов (F Net) возвращает список «центральных» вершин из одной вершины (4).

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1751   2010-03-31 20:42 GMT+3 часа(ов)      
VH, извините, почему у Вас расстояния уже заданы? В условии этого не сказано. Или Вы какую-то другую задачу решили? Кароче, я хочу чтобы мне нормально, внятно сформулировали условие.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#1752   2010-03-31 21:31 GMT+3 часа(ов)      
2.Дан некоторый связный неориентированный граф. Необходимо найти в нём центральную вершину (наиболее равноудалённую ото всех остальных). Наиболее равноудалённая вершина может быть получена как вершина, среднее расстояние от которой до других вершин наиболее близко к среднему значению этой величины для всех вершин графа. Если таких вершин несколько, вывести их все.

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1753   2010-03-31 22:30 GMT+3 часа(ов)      
И что? Не сказано, что расстаяния известны изначально. И расстояние зависит от пути по которому двигаться.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#1755   2010-03-31 23:06 GMT+3 часа(ов)      
Граф - это множество вершин и множество соединяющих вершины дуг. Так как <в условии> речь идет об оценке расстояний, характеристикой дуги должно быть расстояние (длина) вдоль дуги. Предельный случай, когда все расстояния равны нулю, лишает задачу смысла. Следовательно, рассматриваемая характеристика имеет неотрицательные значения (а то, что они все могут быть равными - частный случай). Нижняя граница длины пути <от одной произвольной вершины до другой> - кратчайший путь, верхняя граница - бесконечная длина при «возвратно-поступательном движении» между парой промежуточных вершин. Рассмотрение иных, кроме нижней границы, величин пути (среди которых, попутно заметим, нет <каким-либо образом> выделенных) так же, на мой взгляд, лишено смысла. В итоге задача сводится к поиску вершины (либо вершин), для которой среднее кратчайшее расстояние до остальных вершин ближе всего к среднему значению этой величины для всех вершин графа.
Для определения кратчайшего расстояния между вершинами реализован алгоритм Дейкстры (тот самый, с пометками). Остальное не очень интересно.

отредактировал(а) VH: 2010-03-31 23:36 GMT+3 часа(ов)

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1756   2010-04-01 00:13 GMT+3 часа(ов)      
> характеристикой дуги должно быть расстояние (длина) вдоль дуги.
Но это не значит, что мы знаем сразу длины всех дуг. Достаточно знать длины ребер. Я спросил у OP: заданы ли длины ребер? Он сказал, что длины в усливии нет и что можно считать расстояние между соседними вершинами за единицу.

> Предельный случай, когда все расстояния равны нулю,
> лишает задачу смысла.
Длина ребра по определению строго больше нуля и, к тому же, граф связный. Следовательно, такой случай невозможен.

> Нижняя граница длины пути <от одной произвольной вершины до
> другой> - кратчайший путь,
Да, верно.

> верхняя граница - бесконечная длина при «возвратно-поступательном
> движении» между парой промежуточных вершин.
Если рассматривать такое движение, то да. Я имел ввиду только движения, при которых мы два раза в одну и ту же вершину не заходим. И естественно, такое перемещение будет конечным (т.к. вершин конечное число). Поэтому я спрашиваю, какое расстояние брать?

> Рассмотрение иных, кроме нижней границы, величин пути
> (среди которых, попутно заметим, нет <каким-либо образом> выделенных)
> так же, на мой взгляд, лишено смысла.
Почему это лишено смысла? А может OP имелл ввиду среднее растояние? Вполне "выделенное". Или одна третья от разности между максимальным и минимальным? Или корень квадратный из разности? В условии ничего об этом не сказано.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#1757   2010-04-01 00:32 GMT+3 часа(ов)      
Дуга <в графе> - синоним ребра.
«Он» и ОР - это кто?

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1758   2010-04-01 01:27 GMT+3 часа(ов)      
> Дуга <в графе> - синоним ребра.
Оказывается... На самом деле, это не одно и тоже. Дуга существует только в ориентированном графе: дуга - это ребро с заданным направлением. У нас граф неориентированный, поэтому говорить о дугах не корректно. Хорошо, я перепутал дугу с путем.

> «Он» и ОР - это кто?
Original poster.

отредактировал(а) Михаил: 2010-04-01 14:14 GMT+3 часа(ов)

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1766   2010-04-01 14:17 GMT+3 часа(ов)      
"На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины".
Всё, вопросов больше нет. Прошу прощения за свою невнимательность.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#1767   2010-04-01 15:39 GMT+3 часа(ов)      
Д.Филлипс,А.Гарсиа-Диас "Методы анализа сетей" (перевод Е.Г.Коваленко, М.Г.Фуругяна) стр.12:
«1.1. ПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ
Сеть состоит из множества узлов и множества дуг, соединяющих их. Узлы иногда называют вершинами или точками, а дуги - ребрами, звеньями, линиями или ветвями... Дуги сети могут быть неориентированными, ориентированными и биориентированными. Неориентированной дугой называется дуга, не имеющая определенного направления, ориентированной - дуга, имеющая одно направление, и биориентированной - дуга, имеющая два направления... При решении большинства практических задач нет необходимости делать различие между неориентированными и биориентированными дугами...»
А Вы кого процитировали?

Михаил

Members


Статус

120 сообщений

Где: ---
Род занятий:
Возраст:

#1777   2010-04-01 20:47 GMT+3 часа(ов)      
Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.

Цепи и циклы

Ребром графа G = (X U) называется множество из двух элементов x и у, для которых (х v) принадлежит U или (у, x) принадлежит U, это понятие нельзя смешивать с понятием дуги, в котором участвует ориентация.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#1856   2010-04-18 01:43 GMT+3 часа(ов)      
Пояснения к основной функции (F). Многоточие обозначает части, рассматриваемые на следующем уровне.
(defun F (Граф)
((lambda (перечень количество)
...
)
(mapcar 'car Граф) ; перечень вершин графа
(length Граф))) ; количество вершин графа
)
)


(defun F (Граф)
((lambda (перечень количество)
((lambda (средние)
...
)
(mapcar ; для каждой
#'(lambda (вершина) ; вершины из перечня вершин графа
(/ ; поделить на число других вершин - НАЙТИ СРЕДНЕЕ РАССТОЯНИЕ ДЛЯ <ДАННОЙ> ВЕРШИНЫ
(apply '+ ; сложить все расстояния отвершины до других
(mapcar ; для каждой
#'(lambda (другая) ; другой <вершины>
(DIJKSTRA Граф вершина другая)) ; расстояние от вершины до другой <вершины>
(remove вершина перечень :test 'EQUAL))) ; список <других> вершин за исключением <данной> вершины
(1- количество) ; число <других> вершин за исключением <данной> вершины
)
)
перечень
)
)
)
(mapcar 'car Граф)
(length Граф)))


(defun F (Граф)
((lambda (перечень количество)
((lambda (средние)
((lambda (середина)
...
)
(/ (apply '+ средние) количество) ; середина - среднее расстояние для всех вершин графа
)
)
(mapcar
#'(lambda (вершина)
(/
(apply '+
(mapcar
#'(lambda (другая)
(DIJKSTRA Граф вершина другая))
(remove вершина перечень :test 'EQUAL)))
(1- количество)))
перечень)))
(mapcar 'car Граф)
(length Граф)))


(defun F (Граф)
((lambda (перечень количество)
((lambda (средние)
((lambda (середина)
((lambda (отклонения)
...
)
(mapcar ; для каждого
#'(lambda (расстояние) ; расстояния из списка средних расстояний
(abs (- расстояние середина))) ; взять модуль разности расстояния и среднего расстояния для всех вершин графа - найти ОТКЛОНЕНИЕ
средние
)
)
)
(/ (apply '+ средние) количество)))
(mapcar
#'(lambda (вершина)
(/
(apply '+
(mapcar
#'(lambda (другая)
(DIJKSTRA Граф вершина другая))
(remove вершина перечень :test 'EQUAL)))
(1- количество)))
перечень)))
(mapcar 'car Граф)
(length Граф)))


(defun F (Граф)
((lambda (перечень количество)
((lambda (средние)
((lambda (середина)
((lambda (отклонения)
(EXTRACT_MIN (apply 'min отклонения) отклонения перечень)) ; возвратить список вершин с минимальными отклонениями - НАЙТИ ЦЕНТРАЛЬНЫЕ ВЕРШИНЫ
(mapcar
#'(lambda (расстояние)
(abs (- расстояние середина)))
средние)))
(/ (apply '+ средние) количество)))
(mapcar
#'(lambda (вершина)
(/
(apply '+
(mapcar
#'(lambda (другая)
(DIJKSTRA Граф вершина другая))
(remove вершина перечень :test 'EQUAL)))
(1- количество)))
перечень)))
(mapcar 'car Граф)
(length Граф)))

Кира

Members


Статус

25 сообщений

Где: Russia
Род занятий:
Возраст:

#1863   2010-04-21 01:06 GMT+3 часа(ов)      
А если принимать длину за 1, можно как-то упростить программу?!
В первой программе 5 функций-можно пояснение к каждой?
1. считаем минимальное кол-во дуг от каждой вершины до других (это видимо должна выполнять какая-то функция, подозреваю, что это алгоритм Дейкстры)
2. затем складываем полученные длины для каждой вершины и получаем n сумм (где n кол-во вершин) - что за функция?
3. теперь эти n суммы делим на кол-во этих значений и получаем одно среднее значение и с ним будем сравнивать те числа, которые получились во 2 пункте. И выводим на экран те вершины, значения которых наиболее близки к этому числу - опять же где это в программе?
Поясните! Нельзя ли как-то это всё упростить?а то мы некоторые функции ещё не проходили(((
> 1 <


Онлайн :

0 пользователь(ей), 37 гость(ей) :