0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
1 | |
Рекурсия: Найти путь от элемента первой строки матрицы до элемента последней с максимальной суммой23.02.2011, 12:06. Показов 4096. Ответов 20
Метки нет (Все метки)
ЛР 11.
Дана матрица a(m, n). Найдите в ней путь от элемента первой строки матрицы до элемента последней строки с максимальной суммой. Ходить можно вниз по вертикали или диагоналям. здесь пилится рекурсией =/
0
|
23.02.2011, 12:06 | |
Ответы с готовыми решениями:
20
Рекурсия.Дана матрица a(m,n). Найти в ней путь от элемента a[i1,j1] до элемента a[i2,j2] с максимальной суммой Дана матрица a(m, n). Найдите в ней путь от элемента a[i1, j1] до элемента a[i2, j2] с максимальной суммой Дана матрица a(m, n). Найдите в ней путь от элемента a[i1, j1] до элемента a[i2, j2] с максимальной суммой Найти максимальный элемент строки матрицы и заменить его суммой цифр этого элемента |
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 12:34 | 2 |
можешь привести простенький пример
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|||||||||||
23.02.2011, 12:52 [ТС] | 3 | ||||||||||
+ нужно запоминать путь
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:01 | 4 |
Что такое рекурсия я знаю, приведи простой пример своей матрице и какой должен быть ответ
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:03 [ТС] | 5 |
а, прости
любая матрица в принципе: 8 6 0 3 5 2 3 4 5 1 3 2 5 7 2 4 5 1 2 3 1 3 5 8 9 ответ я думал просто в виде последовательности пройденных элементов матрицы, по типу 8,3,5,5,5
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:03 | 6 |
Что именно тебе нужно найти
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:08 [ТС] | 7 |
последовательность пройденных элементов, но надо учесть что двигаться можно либо прямо вниз либо вниз по диагонали.
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:09 | 8 |
Значит ходить только можно вниз либо по диагонали влево или в право. И нужно максимальную сумму правильно? А изначально можно стартовать с 1 строки и с любого столбца?
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:13 [ТС] | 9 |
ой, да влево-вправо по диагонали и вниз.
начинать можно с любого элемента первой строки, т.е. найти наибольшее в первой строке и с него стартовать. я пока рекурсию осмысливаю (
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:16 | 10 |
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:21 [ТС] | 11 |
спасибо, если не отвлекаю, почему не совсем верно?
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
||||||
23.02.2011, 13:30 | 12 | |||||
Программа с входным и выходным файлами. Так просто удобней. в первой строке n и m. где n - количество столбцов. А m - количество строк. Ну а дальше находиться матрица Добавлено через 2 минуты приведу простой пример. 1 2 3 4 5 1000 1 2 3 4 1 2 3 4 5 если как вы говорите начинать с максимального элемента 1 строки(то есть 5) то мы никак не паподем на 1000. В итоге не верный ответ. Нужно перебирать все варианты
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:35 [ТС] | 13 |
о да, понял, благодраю
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:38 | 14 |
У меня всё работает
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:39 [ТС] | 15 |
но все равно какие то странные значения
например : результат: sum = 6 1 2 3 4 5 5 1 2 3 4 1 2 3 4 5
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:41 | 16 |
Вот исходник, exe и входной файл в архиве
1
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:43 | 17 |
5 3
1 2 3 4 5 5 1 2 3 4 1 2 3 4 5 ответ 14
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:46 [ТС] | 18 |
мой косяк в input.txt был, спасибо большое.
и если не трудно, прошу объяснить мне процедуру recurs, хотя думаю с вас и так достаточно)
0
|
54 / 54 / 23
Регистрация: 02.02.2011
Сообщений: 436
|
|
23.02.2011, 13:53 | 19 |
легко)) это процедура просчитывает все возможные варианты. У нас как бы получается дерева, каждая ветвь разветвляется если возможно на 3, то есть это и есть влево по диагонали, вправо по диагонали и вниз. и когда цепочка заканчивается, то мы смотрим сумму этой цепочки, если сумма больше sum(больше другой ране просчитанной) то в ячейку sum кладем новую сумму и все
1
|
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
|
|
23.02.2011, 13:56 [ТС] | 20 |
спасибо)
теперь поделаю другие варианты лаю на эту тему, руку набивать =/ ну или мозг
0
|
23.02.2011, 13:56 | |
23.02.2011, 13:56 | |
Помогаю со студенческими работами здесь
20
Найти максимальный элемент строки матрицы и заменить его суммой цифр этого элемента Найти в массиве три подряд идущих элемента с максимальной суммой Найти элемент массива с максимальной суммой цифр и номер этого элемента Найти сумму положительных элементов первой строки матрицы, расположенных после первого нулевого элемента Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |