kiborg3014
1

Кратчайший маршрут робота

04.10.2014, 22:54. Показов 1674. Ответов 1
Метки нет (Все метки)

Нужно написать программу для определения маршрута робота.В клеточном поле двигается робот. Имеется система координат x и y (номер клетки по горизонтали и по вертикали). Робот сначала находился в точке c координатами x1,y1, а затем прошел в точку x2, y2. Программа должна получить на вход 4 числа - x1,y1,x2,y2, записанные в отдельных строках. Программа должна вывести на выход его кротчайший маршрут, т.е последовательность цифр, описывающих движение: 1-вверх , 2-вниз, 3-влево, 4- вправо. Например, робот из клетки 1,3 переместился в клетку 4,1. Программа получает на вход
1
3
4
1
и выдает 44422.
Помогите, пожалуйста!
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.10.2014, 22:54
Ответы с готовыми решениями:

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

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

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

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

1
906 / 754 / 833
Регистрация: 06.09.2013
Сообщений: 1,561
05.10.2014, 18:51 2
Лучший ответ Сообщение было отмечено как решение

Решение

Робот должет двигаться только в прямоугольнике с координатами противоположных вершин (x1, y1) и (x2, y2). Тогда таких "кратчайших" путей будет множество. Это количество равно произведению двух чисел, первое из которых - общее количество представлений числа |x2 - x1| в виде суммы нескольких положительных чисел (равно https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{|{x}_{2}-{x}_{1}|-1}), каждое из которых есть последовательное повторение однаковой команды; второе число - то самое, но только для |y2 - y1| (общее число представлений равно https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{|{y}_{2}-{y}_{1}|-1}). Тогда во всех случаях количество ходов будет равно https://www.cyberforum.ru/cgi-bin/latex.cgi?|{x}_{2}-{x}_{1}|+|{y}_{2}-{y}_{1}| (если я правильно понял условие).

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
  x1, y1, x2, y2: integer;
 
begin
  readln(x1);
  readln(y1);
  readln(x2);
  readln(y2);
  var dx := x2 - x1;
  var dy := y2 - y1;
  var p := abs(dx);
  var q := abs(dy);
  while (p > 0) or (q > 0) do 
  begin
    if p > 0 then begin
      var d1 := random(1, p);
      for var i := 1 to d1 do
        if dx > 0 then write(4) //Вправо
        else
        if dx < 0 then write(3); //Влево
      dec(p, d1);
    end;
    if q > 0 then begin
      var d2 := random(1, q);
      for var i := 1 to d2 do
        if dy > 0 then write(1) //Вверх
        else
        if dy < 0 then write(2); //Вниз
      dec(q, d2)
    end
  end 
end.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.10.2014, 18:51
Помогаю со студенческими работами здесь

Кратчайший путь
Здравствуйте... Помогите с задачкой пожалуйста. найти кратчайший путь между точками M и N зная...

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

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

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


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

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

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