0 / 0 / 0
Регистрация: 16.06.2013
Сообщений: 45
1

В двухмерном массиве найти кратчайший маршрут

10.12.2013, 01:36. Показов 1322. Ответов 6
Метки нет (Все метки)

Помогите с такой делимой,Задача на массивы. Пробовал пару разных вариантов но не 1 не подошел, ваще не пойму тчо тут над делать ибо с ними не дружу((


В таблице размером (N x N), где Nбольше или равно 20, клетки заполнены цифрами случайным образом. Найти маршрут из клетки (1,1) в клетку (N,N), удовлетворяющий следующим условиям:
1) любые две последовательные клетки в маршруте имеют общую сторону
2)количество клеток маршрута минимально
3) сумма цифр в клетках маршрута максимальна

Добавлено через 10 часов 39 минут
Люди....
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.12.2013, 01:36
Ответы с готовыми решениями:

Найти кратчайший маршрут
Найти кратчайший маршрут, который начинается и завершается в заданной вершине ориентированному...

Кратчайший маршрут
Очень сложная задачка на мой взгляд. Подскажите хотя-бы алгоритм! Буду очень благодарен.

Найти кратчайший путь в двухмерном массиве (FormAplication)
мне нужно найти кротчайший путь в двухмерном массиве,и надо написать эту программу при помощи...

Найти кратчайший маршрут
Пожалуйста, помогите!!! Имеется несколько городов, связанных в виде графа. Каждое ребро графа...

6
510 / 195 / 26
Регистрация: 07.08.2013
Сообщений: 814
10.12.2013, 10:11 2
Цитата Сообщение от Isida48 Посмотреть сообщение
1) любые две последовательные клетки в маршруте имеют общую сторону
Перемещение только по горизонтали и по вертикали. Т.е. уменьшаться/увеличиваться за один шаг будет только один индекс (строка или столбец).
Цитата Сообщение от Isida48 Посмотреть сообщение
2)количество клеток маршрута минимально
3) сумма цифр в клетках маршрута максимальна
Здесь скорее всего нужно будет сделать рекурсию.
0
0 / 0 / 0
Регистрация: 16.06.2013
Сообщений: 45
10.12.2013, 12:45  [ТС] 3

Хоть вы так и сказали у меня не запускается
я или нуб или что то не понял((
0
510 / 195 / 26
Регистрация: 07.08.2013
Сообщений: 814
10.12.2013, 12:51 4
Isida48,
"Так" это как? не запускается что?
Я Вам привёл набросок логики программы. Ни про какое "запускать" я не говорил.
0
случайный прохожий
2228 / 1468 / 503
Регистрация: 20.07.2013
Сообщений: 4,159
10.12.2013, 15:17 5
Исходя из второго пункта, путь проходит (насколько я понял) рядом с "диагональю".
Далее сравниваем элементы попарно и находим максимум.
C++
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
  const dim = 25;
  int a[dim][dim], sum;
  String res = "Исходные данные:\n";
  randomize();
  for(int i = 0; i < dim; i++)
    for(int j = 0; j < dim; j++)
      a[i][j] = random(10);
 
  for(int i = 0; i < dim; i++)
  {
    for(int j = 0; j < dim; j++)
      res += String(a[i][j]) + "   ";
    res += "\n";
  }
 
  res += "\nПуть: (1,1)";
 
  sum = a[dim-1][dim-1];
  for(int i = 0; i < dim-1; i++)
  {
    sum += a[i][i];
    a[i+1][i] > a[i][i+1] ? (sum += a[i+1][i], res += "->("+String(i+2)+","+String(i+1)+")") : (sum += a[i][i+1], res += "->("+String(i+1)+","+String(i+2)+")");
    res += "->("+String(i+2)+","+String(i+2)+")";
  }
 
  MessageBox(NULL, (res + "\n\nСумма: " + IntToStr(sum)).c_str(), "Задача", 0);
Миниатюры
В двухмерном массиве найти кратчайший маршрут  
0
510 / 195 / 26
Регистрация: 07.08.2013
Сообщений: 814
10.12.2013, 15:35 6
Цитата Сообщение от gunslier Посмотреть сообщение
Исходя из второго пункта, путь проходит (насколько я понял) рядом с "диагональю".
А вот тут вопрос. Isida48, путь в приоритете или сумма? В примере (4,5)=6. Далее идёт шаг на (5,5)=6. Если в приоритете сумма, то нужо́н шаг (3,5)=9.
0
126 / 125 / 62
Регистрация: 07.09.2013
Сообщений: 343
11.12.2013, 15:55 7
gunslier, не обязательно рядом с диагональю. Если не "идти" влево или вверх, то длина пути всегда будет 2*n-1. Например, до упора вниз, и до упора вправо. Я так понимаю, нужен путь длины 2n-1 с максимальной суммой?!

Добавлено через 3 минуты
Возможно, тут нужна рекурсия с возвратом.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.12.2013, 15:55
Помогаю со студенческими работами здесь

Найти кратчайший маршрут
Пожалуйста, помогите!!! Имеется несколько городов, связанных в виде графа. Каждое ребро графа...

Найти кратчайший маршрут на графе
Помогите найти ошибку пожалуйста! задан граф, найти кратчайший путь. Задача на форме. 1я матрица...

Работа с графом.Найти кратчайший маршрут между двумя вершинами.
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень...

Найти кратчайший маршрут, и указать последовательности торговых точек. Графы
Условие: Программа должна найти длину кратчайшего маршрута, но и указать последовательность...

Найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города
Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана...

Кратчайший маршрут робота
Нужно написать программу для определения маршрута робота.В клеточном поле двигается робот. Имеется...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru