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

Маршрут - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Маршрут http://www.cyberforum.ru/cpp-beginners/thread180805.html
массив 10х10 заполнено числами. Начало маршрута в левом нижнем углу. Конец - в правом верхем. Можна двигаться только прямо или вправо. Найти такой маршрут, чтобы сума чисел в ячейках была максимальной
C++ Реализация графов Помогите пожалуйста!!!!! как написать программу на Си ++ на эту тему :реализация различных типов графов и операций над ними. спасибо зараннее. http://www.cyberforum.ru/cpp-beginners/thread180803.html
C++ Прототипы ф-й в *.h файле
у меня была задача.... Написать программу, к-я состоит из 10 ф-й, написать все ф-ии и вызвать их в мейн.... но прототипы функций нада реализовать в *.h файле и подключить эт файл... Подскажите как в этом файле описывать прототипы .... на любом примере плис...
C++ Builder Массив, найти количество чисел, кратных 3 и не кратных 2
Добрый день товарищи! В общем задание такое: Дана числовая последовательность чисел, необходимо посчитать, колличесвтво чисел кратных 3ом и не кратыных 2ум. Т.е. чтобы число делилось на 3 и не делиллось на 2 и подсчитать колличество этих чисел. Вот мои начинания, но выдаёт ошибки: void __fastcall TForm1::BitBtn1Click(TObject *Sender) { int i; int mas; int n=StringGrid1->RowCount; *
C++ Вычислить средние арифметические значения положительных и отрицательных элементов массива http://www.cyberforum.ru/cpp-beginners/thread180780.html
Добрый день. Помогите пожалуйста с задачками по C++. 1) Задан массив A из N элементов. Вычислить средние арифметические значения положительных и отрицательных элементов этого массива, а также максимальное из положи-тельных и максимальное из отрицательных. Значение N и элементы массива A ввести с клавиатуры 2) В целочисленной матрице A размерами N*M вычислить количество элементов, имеющих...
C++ Метод прямоугольника Составить программу вычисления значений определенного интеграла вычисления подъинтегральной функции f(x)=arctg(x)/x a=0 b=0,5; оформить в виде подпрограммы функции число разбиение n=32 методом прямоугольника подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.10.2010, 23:21     Маршрут
Mayonez, В общем эту задачу можно сделать так:
В один массив считываем данные (такие как у Вас на картинке). Создаем второй массив таким же размером. В этом массиве (после того как мы его заполним) в каждой ячейке будет хранится максимальное значение, которое можно для этой ячейки достигнуть, двигаясь только прямо или вправо с нижнего левого угла.
Теперь порядок заполнения значениями этого массива. Вариантов заполнения несколько (но результат всегда одинаковый), я приведу такой.
Сначало заполняем левую сторону вот так (идем снизу вверх):
- самая нижняя ячейка будет равна 15 (я беру данные сейчас для приведенного массива) - а в общем случае самая нижняя ячейка всегда будет равна значению левой нижней ячейки массива со входными данными.
- следующая (левая вторая снизу) будет равна 18 (сумме нижней на одну ступень ячейки второго массива и соответствующей ячейки первого массива) - тут уж не поспоришь (если двигаться можно только вверх и направо, то для данной ячейки самое большое значение может быть только 18)
- следующая (левая третья снизу) - по такой же аналогии (сумма нижней на одну ступень ячейки второго массива и соответствующей ячейки первого массива) - 23
- и т.д. до самого верха самого левого ряда.

Добавлено через 8 минут
Теперь второй слева столбец (и все остальные за ним) заполняются так (начинаем опять снизу):
- самый нижний элемент всегда будет равен сумме предудущего слева элемента во втором массиве и соответствующего элемента в первом массиве (т.е. для второго столбца самый нижний элемент будет равен - 22) тут тоже не поспоришь, ведь путь в эту клетку только один.
- все последующие элементы выбираются так: сравниваем во два элемента во втором массиве (слева от текущего элемента и снизу от текущего элемента), который элемент из этих больше, его значение суммируем с текущим элементом из первого массива и получаем значение текущего элемента во втором массиве. Таким образом мы определяем масимальное значение для каждой клетки которое можно набрать двигаясь только прямо или вправо с нижнего левого угла.

Добавлено через 11 минут
Таким образом мы заполним весь второй массив. В врехнем правом углу получится максимальное значение, которое можно набрать.
Теперь о пути. Путь можно вычислить, после заполнения второго массива, двигаясь обратно. Для этого создаем массив, в котором будем хранить сам путь (хотите типа char сразу, хотите типа int - это все непринципиально). Размер массива всегда будет равен n+(n-2) - не количество пройденных клеток, а количество перемещений между ними.
Итак начинаем с верхнего правого элемента второго массива - будем называть рассматриваемый элемент массива текущим. Если от значения текущего элемента второго массива отнять значение текущего элемента первого массива и получится значение левого от текущего элемента второго массива, то записываем в массив пути F и делаем текущим элемент слева от текущего. Если полученное значение равно значению нижнего от текущего элемента второго массива, то записываем в массив пути R и делаем текущим элемент снизу от текущего. И так до конца (до того момента пока текущим не станет самый ниэний левый элемент).
Вывод результата производить с конца массива пути.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru