![]() |
Модераторы: Daevaorn |
![]() ![]() ![]() |
|
sQu1rr |
|
||||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
В школе проходит олимпиада по информатике. У меня появилось пара вопросов
Вот собственно задания https://docs.google.com/fileview?id=0B579cK...jNzFl&hl=ru 3. У меня никак не получается сделать так, чтобы алгоритм перебора проходил за секнудну. Если он находит тройку диаметр которой 0, то программа завершается, а если нету такого, то идет полный перебор до конца... Не знаю, как с этим быть. Мое решение
6. Алгоритм сделал, но это тупой перебор всех ходов. Ну не может компьютер за нормальное кол-во времени выполнить поиск путей если комнат больше 10. Или я чтото неправильно делаю, или я не могу найти более простого пути. Сделал через рекурсию.
Не то что нуждаюсь в помощи, а просто ради интереса. Учитывая то что 5 заданий я сделал ( 3 походу и так сойдет ), я прошел первый тур олимпиады. И всетаки хочется увидеть более простые и интересные решения |
||||
|
|||||
Abyx |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 601 Регистрация: 3.11.2009 Репутация: 1 Всего: 10 |
3.
надо использовать то, что числа упорядочены по неубыванию это значит, что если у тройки A[i] < B[j] <= C[k] диаметр равен D[i][j][k] то если A[i+1]<=B[j] то D[i+1][j][k]<=D[i][j][k] а если A[i+1]>B[j], то последовательности меняются местами, получается либо B[j] < A[i+1] <= C[k] либо B[j] <= C[k] <= A[i+1] при этом, диаметр либо уменьшается, либьо увеличивается. если уменьшается - следующий шаг, иначе сохраняем результат i,j,k как лучший найденный и ищем дальше Добавлено через 2 минуты и 6 секунд 6. классическая задача на графы. только перебор. читай гугл |
|||
|
||||
sQu1rr |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
У меня примерно так и сделано. Ну ваше решение немного получше будет. Спасибо ) А можно самый простой вариант, просто с графами сталкиваюсь первый раз. перебор то перебором, но было б неплохо какойнибудь быстрый вариант ( по производительности ) |
|||
|
||||
zkv |
|
|||
![]() ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 2133 Регистрация: 23.7.2006 Где: Санкт-Петербург Репутация: 26 Всего: 92 |
||||
|
||||
sQu1rr |
|
||||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Делал просто с логической точки зрения Код медленный изза постоянного применения разных функций, я его уже чутка подправил, стал получше ![]() А нету другого способа. Там значения до 10000 есть, а у меня 11 считает несколько минут на 4х ядерном core 2 (((((( Подравил:
И всетаки работает ужасно медленно. 11 комнат с 66 ходами "изучает" аж 4.5 минуты. Не представляю что будет с 100 комнатами. а с 1000? Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 01:11 |
||||
|
|||||
W4FhLF |
|
|||
![]() found myself ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 2831 Регистрация: 2.12.2006 Репутация: 20 Всего: 121 |
А какая теоретическая сложность у алгоритма?
Для оптимизации кода: 1. Откажись от использования vector<bool>. Очень медленный контейнер. Заюзая vector<unsigned char>. 2. vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении. 3.
А ты где-то используешь параллельные вычисления? Что-то я не вижу. -------------------- "Бог умер" © Ницше "Ницше умер" © Бог |
|||
|
||||
Любитель |
|
||||
Программист-романтик ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 3645 Регистрация: 21.5.2005 Где: Воронеж Репутация: 24 Всего: 92 |
От таких конструкций 100% лучше избавиться. Это же линейный проход по массиву! Учитывая, что твой оператор сравнения просто сравнивает номера - можно же просто обрашаться по индексу.
Это тоже не понял. Ты хочешь полностью сохранить состояние посещённых комнат, а потом вернуть? Ну.. в принципе лучше это делать инкрементно (благо в данном случае это очень просто), но явно не делая два полных (!) прохода по всем комнатам. А вообще - само собой лучше избавиться от рекурсии (используя очередь). |
||||
|
|||||
sQu1rr |
|
||||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Не думаю, что это слишком поможет. Ну увеличится скорость на пару десятков процентов... и что? У меня 150 комнат считает больше 10 часов ((( Не подумал. Но это тоже не спасет производительность.
![]() Попробую. исправить это Так как vRooms содержит комнаты с указателями на комнаты, а копировать долго это все, то я просто сохраняю статус "пройденности" комнот перед рекурсией, потом восстанавливаю. Ато рекурсия работает пару раз, потом прекращается, так как все комнаты пройдены |
||||
|
|||||
Любитель |
|
|||
Программист-романтик ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 3645 Регистрация: 21.5.2005 Где: Воронеж Репутация: 24 Всего: 92 |
На каждом шаге рекурсии ты заходишь в одну комнату. Её и помечаешь пройдённой. А в конце функции - убираешь этот флаг. Это я и называл инкрементным способом в данном случае (иначе - вычисление state[n+1] основано на state[n]). И, ещё раз - вообще рекурсия (с достаточно большим уровнем вложенности, в данном случае - до M) - это большой удар по производительности.
ИМХО, vector<bool> как раз быстрее. Выигрыш без сомнения будет, но действительно не значителен. |
|||
|
||||
sQu1rr |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Я чтото не догадался срасывать флаг вконце рекурсии То что рекурсия все портит, согласен, но я просто не представляю, как можно сделать по другому ((( ![]() ![]() ![]() Только что попробовал ваш "инкриментный способ". Время уменишилось почти в 250 раз. Тоесть вместо 4 минут задача решилась за 1 секунду. Попробую дальше, Спасибо огромное! Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 13:10 |
|||
|
||||
Любитель |
|
|||
Программист-романтик ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 3645 Регистрация: 21.5.2005 Где: Воронеж Репутация: 24 Всего: 92 |
||||
|
||||
sQu1rr |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Даже если я так сделаю, скорость вряд ли увеличится на много. Думаю, что нужен другой алгоритм решения. Не представляю какой
![]() Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 14:20 |
|||
|
||||
Любитель |
|
|||
Программист-романтик ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 3645 Регистрация: 21.5.2005 Где: Воронеж Репутация: 24 Всего: 92 |
Проигрыш при использовании рекурсии достаточно значителен. Алгоритм - по-моему, тут особо больше ничего не придумаешь.
|
|||
|
||||
sQu1rr |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Я пока что сделал так - время уменьшилось на 40%. Ушел от STL, теперь все полностью на стандартных типах. Ща буду рекурсию переробатывать. Надеюсь получится. Если не сложно, опишите алгоритм именно для моей задачи. А то я чтото понять не могу ( *в размышлениях* ) Это сообщение отредактировал(а) sQu1rr - 14.11.2009, 15:53 |
|||
|
||||
Dov |
|
|||
![]() аСинизатор ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1721 Регистрация: 10.5.2003 Где: Эрец-Исраэль Репутация: 15 Всего: 88 |
А так не пойдёт? Я особо не тестировал.
-------------------- Тут вечности запах томительный, И свежие фрукты дешевые, А климат у нас – изумительный, И только соседи – #уевые. Игорь Губерман. |
|||
|
||||
![]() ![]() ![]() |
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |