Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
dota
3 / 3 / 0
Регистрация: 20.09.2010
Сообщений: 100
#1

Алгоритм решения задачи - C++

21.10.2012, 14:15. Просмотров 2268. Ответов 5
Метки нет (Все метки)

Есть вот такая вот задача . На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстояни*ем в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может старто*вать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время.
Задается число n — количество монет , для каждой монеты задается по 2 целых числа, первое из которых задает положение монеты, а второе — крайний срок в секундах, за который нужно успеть собрать эту монету. Нужно найти минимальное время сбора всех монет или сказать , что собрать все монеты невозможно.
Собственно , меня интересует только алгоритм решения (очень похоже на динамическое программирование , но как я не пробовал , не получается) и какие структуры данных лучше использовать . Буду благодарен за любую помощь .
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2012, 14:15     Алгоритм решения задачи
Посмотрите здесь:

Алгоритм решения задачи - C++
Помогите пожалуйста сделать алгоритм по коду, из блоков и стрелочек Вот код: //Библиотека контейнера #include<list> //Библиотека...

Подскажите алгоритм решения задачи - C++
Подскажите пожалуйста алгоритм решения этой задачи: Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую...

Алгоритм решения олимпиадной задачи - C++
clip2net . com/clip/m121445/1353341115-clip-71kb.jpg Дело в том, что я не знаю, как лучше считать данные. То есть прочитать всю строку, а...

Алгоритм решения задачи о раскрое материала - C++
Доброго времени суток. Читаю литературу по С++ для начинающих и уже стараюсь развивать мышление. Пока написание кода отложил, решил...

Составить алгоритм решения задачи согласно условию - C++
Помогите пожалуйста! Составить алгоритм решения задачи согласно своему варианту. В отчете предоставить три программы с разными...

Реализовать алгоритм решения задачи «Ханойские башни» - C++
задание: Реализовать алгоритм для решения задачи «Ханойские башни». Выписать последовательность ходов для перекладывания n дисков башни...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
De_N
28 / 26 / 9
Регистрация: 15.10.2012
Сообщений: 60
21.10.2012, 16:02     Алгоритм решения задачи #2
Если я правильно понял условие, то графически данную задачу можно представить как одномерную полуось, т.е. например только положительное направление оси X.
Начало координат расположено в начальной точке с координатой 0.
На этой оси имеется n точек (монет). Их координаты даны по условию.
Как я понимаю Али-баба может передвигаться от точки к точке и при этом сам выбирать первую точку.

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

int coord; // Координата (дана по условию)
int time; // Срочность/время на сбор (также дано)
bool take; // Показатель того, что монета собрана (точка посещена)
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
21.10.2012, 16:17     Алгоритм решения задачи #3
De_N, надо найти минимальное время. К примеру
Код
3 - 2 - 5
Ваш алгоритм выведет 3, а минимальное время 2.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.10.2012, 16:19     Алгоритм решения задачи #4
Цитата Сообщение от De_N Посмотреть сообщение
Мне кажется нужно начинать от самой срочной точки (монеты) и двигаться по мере уменьшения срочности.
Находясь в текущей точке, вибирать самую срочную и вычислять до нее расстояние.
Не все так просто. Допустим очередные по срочности оказались две монеты, причем можно успеть собрать одну а потом другую в любом порядке. Вот здесь может очень важным оказаться порядок их сбора, вернее где мы закончим сбор: около первой или второй (следующую по срочности монету после этих двух монет, можно успеть собрать из какого-то одного положения).
Или вот вариант:
Али-баба находится в точке 10, текущее время 10.
Остались две монеты: 3 19 и 11 20. Если двинуться за более срочной (которая на расстоянии 3), то вторую не успеем забрать. Здесь правильнее будет взять сначало на расстоянии 11, а затем на расстоянии 3.
Здесь, по-моему, лучше воспользоваться графами (поиском в глубину).
De_N
28 / 26 / 9
Регистрация: 15.10.2012
Сообщений: 60
21.10.2012, 21:12     Алгоритм решения задачи #5
Ок. Справедливо

Добавлено через 3 часа 27 минут
Подумал, подумал..
Мне кажется при таких условиях единственным выходом будет перебор решений. Должно быть некоторая часть решений отсеится уже на первых "ходах".
Ведь программа в праве сама выбирать первую монету. То есть если представлять решение как граф, его начальная точка (первая монета) не определена заранее.
К сожалению я не очень силен в теории графов, поэтому делаю лишь предположение.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.10.2012, 21:54     Алгоритм решения задачи
Еще ссылки по теме:

Составить алгоритм решения задачи в виде блок-схемы - C++
Последовательно вводятся N целых чисел.Определить,сколько из них совпадают с первым числом. Нужно составить алгоритм решения задачи в виде...

Составить программу решения задачи, используя рекурсивный алгоритм - C++
Задание во вложение

Разработать алгоритм решения задачи обработки одномерного массива. - C++
Помогите пожалуйста с написанием кода: Лабораторная работа № 4 Разработать алгоритм решения задачи обработки...

Разработать алгоритм и программу для решения задачи с использованием строк символов - C++
Дана строка символов. Определить количество слов, начинающихся с буквы ''а'', вывести на печать самое длинное слово, начинающееся с...


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

Или воспользуйтесь поиском по форуму:
dota
3 / 3 / 0
Регистрация: 20.09.2010
Сообщений: 100
21.10.2012, 21:54  [ТС]     Алгоритм решения задачи #6
Вот-вот , вообще непонятно с какой монеты надо начинать , а перебором не годится (
Yandex
Объявления
21.10.2012, 21:54     Алгоритм решения задачи
Ответ Создать тему
Опции темы

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