Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 04.11.2011, 21:04   #1
merhaba1992
Пользователь
 
Регистрация: 12.12.2010
Сообщений: 10
По умолчанию Жадный алгоритм

Добрый Вечер!! Помогите Пожалуйста написать код к задаче(Pascal):
Группе туристов нужно перейти через длинный узкий мост, на котором одновременно не может находиться более двух человек. Однако получилось так, что к мосту они пришли уже в темное время суток, и идти по мосту нужно с мощным фонарем, который у группы один. Как надо действовать — туристам понятно. Сначала
двое переходят мост, затем один возвращается и приносит с собой фонарь. Далее в
путешествие по мосту отправляется следующая пара. Для каждого из туристов известно время, за которое он может перейти мост. Когда туристы идут в паре, время перехода определяется как время, за которое пройдет мост более медленный турист. Туристы хотят переправиться на другую сторону за минимально возможное
время. Ваша задача — написать программу, определяющую, в какой последовательности нужно переходить мост туристам, и сколько времени они затратят на
переход.
Формат входных данных:
Первая строка — целое число N
Вторая строка содержит N чисел T1, T2, …, TN — время, за которое турист с соответствующим номером может перейти через мост.

Мой алгоритм:
- сначала отсортировать туристов по времени в порядке возрастания
Потом: - идут два самых быстрых
- самый быстрый возвращается
- идут два самых медленных
- самый быстрый возвращается
далее начинаем сначала.

Последний раз редактировалось merhaba1992; 04.11.2011 в 21:19.
merhaba1992 вне форума Ответить с цитированием
Старый 05.11.2011, 00:24   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Ваш алгоритм не всегда даст оптимальное решение.

эта задача была подробно (и исчерпывающе) рассмотрена в теме:
Задача про мост
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Жадный алгоритм в программировании nikita92 Помощь студентам 0 26.11.2010 20:20
Жадный алгоритм. Задача о размене денег. Multiman Помощь студентам 4 18.10.2010 13:15
Delphi(1й курс) Жадный алгоритм Archetype Помощь студентам 8 17.05.2010 19:49
Жадный алгоритм и перебор mailjaffka Помощь студентам 10 17.05.2010 16:20