| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Object Pascal: кроссплатформенные технологии > Помогите решить задачу на ГРАФЫ или инфы подкиньте |
| Автор: 3uM6a6Ba 4.1.2005, 22:12 |
| Сразу оговорюсь читал, искал, смотрел весь форум, видимо, я не понял!!! ГРАФЫ ---->>> В деревне имеется 26 жителей, возраст каждого - А(большая буква) Известно, что самый старший возраст жителя <=100 (не может превосходить 100 лет) Во входном файле заданы информация о (определяемом кол-ве жителей), возрасте неравенствами типа: k=10 (//жителей надо определить) А-В>=10 B-C>=5 и т. д.(Неравенств может быть сколько угодно) Определить максимально возможный возраст каждого жителя деревни если удается!!! ПРосьба подсказать как строится граф и реализацию алгоритма!!! |
| Автор: Fedor 4.1.2005, 23:24 |
| Ну, первое что пришло в голову... граф строишь так: ориентированное ребро выходит из A в B и равно 5 если A-B>=5 А еще какое-то внутреннее сверхестественное чутье подсказывает мне, что тут нужно построить остовное дерево что-то типа алгоритмом Прима. Скорее всего, на 80% я не прав, но попробывать стоит. Просто сложно думать, когда такое неорганизованное условие. Ты можешь точно его переписать? И если можно несколько правильных примерчиков небольших с входными и выходными данными. З.Ы. А вообще задача интересная. Где взял? |
| Автор: 3uM6a6Ba 5.1.2005, 00:29 |
| --Условие переписано точно со слов препода (+подсказки от него же)--примеров нет Правильный ответ строиться по принцепу: Если допустим ====================================Вход=================== к=10 //кол-во жителей под "надзором" А-В>=5 //ЭТО ЗНАЧИТ, что A больше В на 5 лет B-C>=3 //по аналогии A-С>=15 // =========================================================== Если это и есть весь входной файл то Вывод, смый старый житель =100 2-95 3-85 ну и т.д. остльных неудлось определить т.к. не хватает данных, да и вот таких неравенств в входе может быть сколько угодно много. Если надо 10 жителей определить там такое можно замутить с неравенствами, что крыша съедет(может это я просто не понимаю структуру!!!) ============================================================== Фишка вот в чем, препод проговорился еще и про какоето М которое якобы тоже должно быть во входном файле а может и не долно!!! А если и есть, то М=кол-ву неравенств, я так думаю (или узлов в графе) Просьба еще описать структуру или как говориться код в голом виде с пояснениями что куда!!! А если есть желание могу таких задач еще достать (про шахматы, лабиринты и т.д.) |