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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 5.00
pigah
 Аватар для pigah
12 / 12 / 2
Регистрация: 05.07.2009
Сообщений: 147
Записей в блоге: 1
#1

Минимальный штраф. - C++

13.10.2009, 01:09. Просмотров 2505. Ответов 14
Метки нет (Все метки)

Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо).
Известно, что 1 <= n <= 1000, 1<= m <= 1000, программа должна работать правильно при любых допустимых значениях n и m, даже если они равны 1.
Ввод из файла “input.txt”. В первой строке через пробел содержатся значения n и m (размеры матрицы), в последующих строках – сама матрица штрафов. Вывод в файл “output.txt”. В первой строке выходного файла содержится суммарный штраф по пути следования, во второй – последовательность набранных штрафов.
Примеры входных данных
input.txt
4 5
3 2 8 6 4
4 7 12 9 1
55 8 3 2 8
20 7 4 9 1
input.txt
3 1
3
4
1
Соответствующие выходные данные
output.txt
8
4 1 2 1
output.txt
8
3 4 1


Объясните плиз что здесь нужно сделать с массивом
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
13.10.2009, 06:03     Минимальный штраф. #2
с массивом делать ничего не надо.
требуется перебрать все возможные комбинации перемещения и выбрать оптимальный маршрут (минимальная сумма штрафов).
в начале будет основной цикл по всем элементам первой строки. а в теле будет перебор всех возможных перемещений с учётом ограничений по движению.

Если язык написания С++ то очень удобно использовать стандартные контейнеры.
Подобная задача: Коммивояжер (бродячий торговец), уже не раз поднималась на форуме. а там дальше при изучении наткнёшь на всякие графы и алгоритмы оптимального блуждания по ним.
PAKOT
1 / 1 / 0
Регистрация: 21.10.2009
Сообщений: 39
21.10.2009, 19:43     Минимальный штраф. #3
Нашел на форуме задачку Коммивояжер ( http://www.cyberforum.ru/cpp/thread5...read55616.html ) но никаких графов и алгоритмов я не нашел....
odip
Эксперт С++
 Аватар для odip
7151 / 3291 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
21.10.2009, 21:09     Минимальный штраф. #4
2TanT: Даю подсказку - задача решается алгоритмом динамического программирования.
Я тебе рассказывал этот алгоритм.
Сможешь написать ?

Добавлено через 24 секунды
Если блуждать в потемках - это будет очень долго.

Добавлено через 31 секунду
Сама задача похоже с сайта ********
PAKOT
1 / 1 / 0
Регистрация: 21.10.2009
Сообщений: 39
24.10.2009, 10:05     Минимальный штраф. #5
Ну так что никто не подскажет алгоритм ?
Malecha
16 / 16 / 1
Регистрация: 12.09.2009
Сообщений: 25
25.10.2009, 20:07     Минимальный штраф. #6
Ну вот так всегда.. каждый хочет получить золотую медальку и при этом не особо напрягать свои мозги..

Всеукраинский открытый чемпионат компьютерных талантов «Золотой Байт» основан Компьютерной Академией «ШАГ» в 2008 году, ориентирован на молодое, прогрессивное поколение, которое стремится проявить и реализовать свои способности в сфере IT-технологий, дизайна и коммуникаций...
Rififi
 Аватар для Rififi
2332 / 1047 / 43
Регистрация: 03.05.2009
Сообщений: 2,656
25.10.2009, 20:12     Минимальный штраф. #7
Malecha,
Ну вот так всегда.. каждый хочет получить золотую медальку и при этом не особо напрягать свои мозги..
А какой смысл во всем этом, что-то я не пойму? Если мозгов нет, то зачем медалька?
IT вроде бы не та область, где без мозгов надолго задерживаются.
Malecha
16 / 16 / 1
Регистрация: 12.09.2009
Сообщений: 25
25.10.2009, 20:30     Минимальный штраф. #8
Просто эта задача из конкурса "Золотой байт". После решения попадаеш во второй тур..
odip
Эксперт С++
 Аватар для odip
7151 / 3291 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
26.10.2009, 10:25     Минимальный штраф. #9
По стилю оформления задача похожа на олимпиадные задачи с сайта www.********.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
26.10.2009, 12:03     Минимальный штраф. #10
Цитата Сообщение от Malecha Посмотреть сообщение
Просто эта задача из конкурса "Золотой байт". После решения попадаеш во второй тур..

Не по теме:

а байт правда золотой или как всегда крашенный из нержавейки?
если золотой, то можно порешать, а скока у нас байт нынче весит?

Malecha
16 / 16 / 1
Регистрация: 12.09.2009
Сообщений: 25
26.10.2009, 12:21     Минимальный штраф. #11
Цитата Сообщение от TanT Посмотреть сообщение
Не по теме:
а байт правда золотой или как всегда крашенный из нержавейки?
если золотой, то можно порешать, а скока у нас байт нынче весит?
)))
http://www.goldenbyte.org - там все расценки
ThuND3Rb0LT
Сообщений: n/a
31.10.2009, 19:27     Минимальный штраф. #12
Вы, "неучи", которые хотят во второй тур, вот представьте себе, так же и в третий пройдете, а в третьем скажут типо "к нам подкатуйте, у нас пишите",и вы там облажаетесь более чем по полной программе; т.к. я сам участвую, то секрет решения открывать не буду, а вы, "неучи", могли бы и подумать, или вы думаете в "ШАГ"е дураки сидят?.. З.ы. Ник свой я вам не скажу. З.З.ы он не такой как тут. З.З.З.Ы. за 50 баксов могу подсказать идею
Прошу прощения если к pigah это не относится, но "некоторые" которые незнают как - бороздят просторами форума, поэтому прошу не выкладывать решение.)
Malecha
16 / 16 / 1
Регистрация: 12.09.2009
Сообщений: 25
31.10.2009, 19:37     Минимальный штраф. #13
ThuND3Rb0LT, можеш не переживать не ты один такой умный и нашел решение..
odip
Эксперт С++
 Аватар для odip
7151 / 3291 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
31.10.2009, 22:26     Минимальный штраф. #14
От темы не отвлекаемся.
Если кто не знает как делать и сам решил - пусть выкладывает код. Хоть ему одному будет какая-то польза от этого.
Ну а тем кто знает выкладывать код необязательно
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2009, 00:10     Минимальный штраф.
Еще ссылки по теме:

C++ Минимальный палиндром на с++
C++ Структура "Штраф". Функция поиска криво работает
C++ Стуктура ШТРАФ плохо с выводом и записью в файл
C++ Неправильный минимальный элемент
Из списка удалить минимальный и минимальный положительный элементы C++

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

Или воспользуйтесь поиском по форуму:
Malecha
16 / 16 / 1
Регистрация: 12.09.2009
Сообщений: 25
13.11.2009, 00:10     Минимальный штраф. #15
И так кто прошел во второй тур?
Yandex
Объявления
13.11.2009, 00:10     Минимальный штраф.
Ответ Создать тему
Опции темы

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