Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/22: Рейтинг темы: голосов - 22, средняя оценка - 5.00
0 / 0 / 1
Регистрация: 16.01.2011
Сообщений: 52
1

Рекурсия: Найти путь от элемента первой строки матрицы до элемента последней с максимальной суммой

23.02.2011, 12:06. Показов 4096. Ответов 20
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
ЛР 11.
Дана матрица a(m, n). Найдите в ней путь от элемента первой строки матрицы до элемента последней строки с максимальной суммой. Ходить можно вниз по вертикали или диагоналям. здесь пилится рекурсией =/
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.02.2011, 12:06
Ответы с готовыми решениями:

Рекурсия.Дана матрица a(m,n). Найти в ней путь от элемента a[i1,j1] до элемента a[i2,j2] с максимальной суммой
Помогите сделать на java.Не особо понимаю, как эту задачу можно реализовать. Дана матрица a(m,n)....

Дана матрица a(m, n). Найдите в ней путь от элемента a[i1, j1] до элемента a[i2, j2] с максимальной суммой
Дана матрица a(m, n). Найдите в ней путь от элемента a до элемента a с максимальной суммой. Ходить...

Дана матрица a(m, n). Найдите в ней путь от элемента a[i1, j1] до элемента a[i2, j2] с максимальной суммой
Help Дана матрица a(m, n). Найдите в ней путь от элемента a до элемента a с максимальной суммой....

Найти максимальный элемент строки матрицы и заменить его суммой цифр этого элемента
Программа должна находить максимальный элемент строки и заменять его суммой цифр этого элемента, а...

20
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
Pascal
1
2
3
4
5
6
Function factorial(N: integer) : longint; 
Begin 
   If N= 0 then 
   Factorial := 1 
   Else Factorial := factorial(N-1) * N 
End;
вот простейший пример рекурсивной ф-ции

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
program l11_27_l2;
uses
 crt;
type
 matrix = array[1..10,1..10] of real;
var 
  a:matrix;
  n:byte;
 
procedure read_matrix(fn:string; var a:matrix; var n:byte);
var 
 f:text;
 i,j:byte;
begin
 assign(f,'input.txt');
 reset(f);
 readln(f,n);
 for i:=1 to n do
  for j:=1 to n do
   read(f,a[i,j]);
 close(f);
end;
 
procedure obxod (var a:matrix; n:byte);
var
 i,j:integer;
begin
 for i:=1 to n do
 
 
end;
 
 
 begin
 
 end.
а вот то, что я пока запилил, чтение из файла. сейчас размышляю как обход запилить.

+ нужно запоминать путь
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
Цитата Сообщение от xamenrax Посмотреть сообщение
т.е. найти наибольшее в первой строке и с него стартовать.
не совсем верно
Ща напишу
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
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var
   a:array[1..100,1..100] of integer;
   i,j,n,m,sum:integer;
 
procedure recurs(i,j:byte; s:integer);
begin
   if j<=m then
   begin
      if i<>1 then recurs(i-1,j+1,s+a[i,j]);
      if i<>n then recurs(i+1,j+1,s+a[i,j]);
      recurs(i,j+1,s+a[i,j]);
   end
   else
      if s>sum then sum:=s;
end;
 
begin
   assign(output,'output.txt');
   rewrite(output);
   assign(input,'input.txt');
   reset(input);
   readln(n,m);
   for j:=1 to m do
   begin
      for i:=1 to n do
         read(a[i,j]);
      readln;
   end;
   for i:=1 to n do
      recurs(i,1,0);
   write(sum);
end.
Добавлено через 3 минуты
Программа с входным и выходным файлами. Так просто удобней. в первой строке 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 и входной файл в архиве
Вложения
Тип файла: rar Desktop.rar (20.1 Кб, 25 просмотров)
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.02.2011, 13:56
Помогаю со студенческими работами здесь

Найти максимальный элемент строки матрицы и заменить его суммой цифр этого элемента
программа заменяет максимальный элемент суммой цифр, проблема в том , что заменяется только...

Найти в массиве три подряд идущих элемента с максимальной суммой
Три подряд Дан массив, найдите в нем три подряд идущих элемента с максимальной суммой. Формат...

Найти элемент массива с максимальной суммой цифр и номер этого элемента
Дан массив,состоящий из n элементов,элементами массива являются двузначные числа. Найти элемент с...

Найти сумму положительных элементов первой строки матрицы, расположенных после первого нулевого элемента
Определить величину Y, как сумму положительных элементов первой строки матрицы, расположенных после...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru