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

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

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль

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

Ответ
 
Опции темы Поиск в этой теме
Старый 13.10.2009, 23:34   #11
breate
Пользователь
 
Аватар для breate
 
Регистрация: 30.12.2008
Сообщений: 78
По умолчанию

я считаю что не самым точным но самым быстрым будет
1 найти минимальный элемент каждой строки
2 посчитать каких элементов больше(примерно среднее арифметическое) с учетом отклонения +/-1
3 найти сумму

всего будет сделано n + 1 проходов по матрице

3____2____8____6____4 min 2
4____7____12___9____1 min 5
55___8____3____2____8 min 4
20___7____4____9____1 min 5

явно видно доминирование 5-го столбца над всеми
Моя работа - Создание сайтов

Последний раз редактировалось breate; 13.10.2009 в 23:39. Причина: дополнение примером матрици
breate вне форума Ответить с цитированием
Старый 14.10.2009, 00:59   #12
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Во-первых, асимптотика та же. Во-вторых, полный бред, так как нету алгоритмического обоснования - я даже не увидел в Вашем посте, чему равен ответ, скажем, для примера. В-третьих, проход по матрице будет 1. В-четвертых, повторю еще раз, решение, приведенное мною - полноценное и алгоритмически эталонное, вопрос только в пряморукой реализации. У кого вопросы - купите себе хотя бы сборник алгоритмов. В-пятых, нужно не "не самое точное", а ПОЛНОЕ решение, поэтому ваше заслуживает только на место на баше - примерные решения это марафон на топкодере, а не олимпиадная задача, в которой тестирование ведется по принципу "совпало - зачет, не совпало - незачет".
LeBron вне форума Ответить с цитированием
Старый 14.10.2009, 17:55   #13
Airo
 
Регистрация: 12.10.2009
Сообщений: 4
По умолчанию

Спасибо LeBron! Отличный способ решения, незнаю сколько бы у меня ушло времени додуматься до этого (думал только рекурсия подойдет). Правда не очень понял про массив указателей путей Пошел по своему пути, из нового массива иду снизу вверх от наименьшего элемента и запоминаю координаты которые потом применю к заданному массиву.
Еще вопрос, я впервые услышал (от тебя) понятие - динамическое решение, можешь объяснить где оно тут проявляется, просто задача как задача.. И извени если достаю =)
Airo вне форума Ответить с цитированием
Старый 14.10.2009, 21:36   #14
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Нет, не достаете. Вполне нормальные вопросы, которые нормально сформулированны и поставленны. Динамическое программирвание - даже не знаю, как объяснить. Есть формальные определения, можно в Вики почитать, коротко я не объясню. В задачах такого типа - определяется как разбиение задачи на простые подзадачи, доказательство их индуктивной коректности и поочередное решение. В конкретном случае - мы задачу "найти путь к енной строке" разбили на "найти путь к первой строке", "найти пусть с первой строки во вторую", и так делее. Часто используется, когда трудно в зависимостях найти определенную формулу, но можно делать индуктивно. Например, мы не знаем, чему равно f(x). но доказали, что f(x)=g(f(x-1)). Зная f(1), можем в цыкле или рекурсией найти сначала f(2), потом f(3), и так до искомого.
Еще случай - задача о ранце. Есть грузоподъемность ранца и массив весов возможных предметов, которые в него можно сунуть в любом количестве. Надо определить, можно ли заполнить ранец ровно по грузоподъемности. Простой перебор или рекурсия убиваются, а надо делать почти так же, как в прошлом примере - заводим массив "можно-нельзя". 0ой эллемент делаем 1 "можно", так как пустой ранец (вес 0) - не проблема. А дальше в цикле с 0 если эллемент "можно", то и все, которые "можно+любой из весов из массива" тоже "можно". Если эллемент не стал можно, пока мы до него добирались - он "нельзя". Снова получилось определять функцию через более низкие аргументы
По поводу указателей - в дополнительном массиве хранить для каждой клетки, откуда в нее надо прийти для минимального пути. Вот здесь можно для самого вывода уже и рекурсию использовать, если есть желание.
LeBron вне форума Ответить с цитированием
Старый 14.10.2009, 21:46   #15
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Airo, Ваше решение задачи поиска пути немногим хуже, чем мое, а в плане памяти - даже лучше. Просто у меня для каждой клетки будет извесно, как в нее прийти, а у Вас уйдет 3 действия (как я понял, Вы для клетки массива сум будете выбирать минимальную клетку массива сум, из которой можна в нее прийти), что не много, но зато память ненужную вы не используете, а я использую. Какое из 2 решений выбрать - нужно всегда смотреть в конкретном случае (по ограничениях и возможностях), но знать и уметь пользоватся надо обеими.
LeBron вне форума Ответить с цитированием
Старый 14.11.2009, 02:06   #16
rand8154
Пользователь
 
Регистрация: 20.10.2009
Сообщений: 18
По умолчанию

Мне понравлся неизвращенный и трезвый ход Вашых мыслей.
Может немного не по теме, но хочу спросить: есть ли красивая идея реализации зеркального отображения числа вида 011->110, 01011100111->11100111010 т.п. без тупого цикла?
архикриптокодоквазинаноультракванто вый генератор
rand8154 вне форума Ответить с цитированием
Старый 14.11.2009, 11:20   #17
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Цитата:
Сообщение от rand8154 Посмотреть сообщение
Мне понравлся неизвращенный и трезвый ход Вашых мыслей.
Может немного не по теме, но хочу спросить: есть ли красивая идея реализации зеркального отображения числа вида 011->110, 01011100111->11100111010 т.п. без тупого цикла?
Зависит от того, что называть тупым циклом. Я бы просто сделал цикл (тупой?), в котором через дополнительный массив сделал бы посимвольно "зеркальное отражение". Если хотите определенный "математический факт", то я его с ходу не вижу. А вдумываться глубше просто не вижу смысла.
LeBron вне форума Ответить с цитированием
Ответ


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



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Подскажите чайнику(мне) какую прогу написать? BETONOMESHALKA Свободное общение 23 26.10.2011 12:27
Остановился в развитии, направьте в какую сторону идти дальше! iukash Свободное общение 43 02.09.2009 19:16
Подскажите, какую программу выбрать... Лена Брусникина Помощь студентам 0 19.06.2009 21:10
Подскажите пожалуйста какую функцию необходимо использовать... Андрю)(@ Паскаль, Turbo Pascal, PascalABC.NET 1 10.12.2008 00:03
Подскажите пожалуйста какую функцию необходимо использовать... Андрю)(@ Помощь студентам 1 09.12.2008 23:53