Запишите алгоритм наливания воды в стакан двумя

Наши действия

Для того, чтобы решить задачу, нам не требуется делать какие-то сложные переборы в поисках кратчайшего пути. Так как на поле у нас нет никаких препятствий, нам достаточно рассчитать расстояние между клетками поля. Это и будет ответом.

Как рассчитать расстояние

Для этого используются метрики.

Мне тут давеча сказали, что это слово пугает детей и вводит их в паническое состояние.

¯\_(ツ)_/¯  Не понимаю, чего там такого пугающего)

На самом деле, тут всё просто, так что забудем про страшные слова и посмотрим, как можно вычислять расстояния.

Для примера возьмём плоскость, на которой нам достаточно 2-х координат для задания положения точек.

Как посчитать расстояние между точкой А(x0, y0) и B(x1, y1)?

Уроки геометрии учат, что . Поздравляю, ты познакомился со своей первой метрикой. Она называется Евклидова метрика. Или Евклидово расстояние - кратчайшее расстояние между двумя точками пространства.

А теперь представим, что ты оказался в центре города. И тебе надо узнать, как много нужно пройти от твоего местоположения до гостиницы. Путь это будут всё те же точки A и B.

Мы уже могли бы рассчитать Евклидову метрику. Однако она нам мало чем мы ведь не можем ходить насквозь домов. Придётся обходить. А значит, и расстояние увеличится.

Для такой ситуации подходит Манхэттенская метрика или по-другому Расстояние городских кварталов.

Рассчитывается она тоже просто . То есть просто сумма расстояний по x и по y. Если ходить по улицам, не через дворы, то нам не важно, сколько раз мы будем поворачивать. Мы пройдем столько же, сколько бы сначала по x, а потом по y.

Помимо этих двух метрик, есть ещё метрика Чебышёва.

Она рассчитывается как . То есть вычисляются расстояния по координатам, и выбирается максимальное из них.

Забавно, но одно из объяснений этой метрики звучит как "Минимальное количество ходов, которое требуется совершить королю из клетки A в клетку B".

Ниже я привел картинку, на которой можно увидеть, почему это работает.

Итак, решено. Будем рассчитывать искомое расстояние по методу Чебышёва.

КодProgram king;Varx0, y0, x1, y1: integer;BeginWriteln('Введите координаты точки s:');Readln(x0, y0);Writeln('Введите координаты точки f:');Readln(x1, y1);If ((a < 1) or (a > 8) or (b < 1) or (b > 8) or (c < 1) or (c > 8) or (d < 1) or (d > 8)) thenWriteln('Ошибка! Проверьте правильность введённых данных! Закрытие программы... ')ElseWriteLn(Max(Abs(x1 - x0), Abs(y1 - y0)));Readln;End.

program shkisvf;

uses

crt;

procedure minh(sx, sy, dx, dy: integer);

var

h: integer;

begin

h := 0;

while ((sx <> dx) and (sy <> dy)) do

begin

if (sx < dx) and (sy < dy) then

begin

sx := sx + 1;

sy := sy + 1;

h := h + 1;

end ;

if (sx > dx) and (sy < dy) then

begin

sx := sx - 1;

sy := sy + 1;

h := h + 1;

end ;

if (sx < dx) and (sy > dy) then

begin

sx := sx + 1;

sy := sy - 1;

h := h + 1;

end ;

if (sx > dx) and (sy > dy) then

begin

sx := sx - 1;

sy := sy - 1;

h := h + 1;

end ;

end;

while ((sx <> dx) or (sy <> dy)) do

begin

if sx < dx then

begin

sx := sx + 1;

h := h + 1;

end ;

if sx > dx then

begin

sx := sx - 1;

h := h + 1;

end ;

if sy < dy then

begin

sy := sy + 1;

h := h + 1;

end ;

if sy > dy then

begin

sy := sy - 1;

h := h + 1;

end ;

end;

writeln('Минимальное количество ходов: ', h);

end;

procedure cheb(sx, sy, dx, dy: integer);

var

max, rx, ry: integer;

begin

rx := abs(sx - dx);

ry := abs(sy - dy);

writeln('Минимальное кол-во ходов по Чебышёву:');

if rx > ry then

writeln(rx)

else

writeln(ry);

end;

var

a, b, c, d: integer;

begin

writeln('Введите координаты точки s:');

readln(a, b);

writeln('Введите координаты точки f:');

readln(c, d);

if ((a < 1) or (a > 8) or (b < 1) or (b > 8) or (c < 1) or (c > 8) or (d < 1) or (d > 8)) then

writeln('Ошибка! Проверьте правильность введённых данных! Закрытие программы... ')

else

minh(a, b, c, d);

cheb(a, b, c, d);

readln;

end.