(1 курс ФИИТ) CS101. Основы программирования — лекции (2016-17гг)

[Niki]

Приведу алгоритм решения задачи про четырехугольник. Очевидно, что нас не устраивает вариант, когда АВ пересекается с СD внутри этого “четырехугольника”,т.е когда порядок АСВD. Рассмотрим возможности пересечения AВ и СD. Точка пересечения М может находиться либо между отрезками АD и ВС, либо вне этих отрезков. Если она внутри, то четырехугольника не существует, если она вне, или прямые параллельны, то четырехугольник возможен. Если нарисовать картинку, то факт очевиден.

Дальше просто пишем уравнение всех прямых, находим точку пересечения прямых АВ и СD, а потом проверяем: если подставить координаты точки М в уравнения прямых АС и ВС, и при этом получится, что одна из левых частей уравнений больше нуля, а другая меньше, то четырехугольника не существует. В противном случае такой четырехугольник существует.

P.S. Адекватно реализовать алгоритм в программу не получилось, поэтому привел только сам алгоритм)

[Admin]

Хотелось бы довести до формул

[DasIgnis]

Еще одно решение задачи про треугольник, немного отличающееся от предоставленного выше

program op_task1;

begin

Var Xa, Ya, Xb, Yb, Xc, Yc: real; write('Введите Xa, Ya >> '); readln(Xa, Ya); write('Введите Xb, Yb >> '); readln(Xb, Yb); write('Введите Xc, Yc >> '); readln(Xc, Yc);

//Найдем общую площадь треугольника //Формула S=1/2[(x1-x3)*(y2-y3)-(x2-x3)(y1-y3)]

var So:=abs(1/2*((Xa-Xc)(Yb-Yc)-(Xb-Xc)(Ya-Yc)));

var Xm, Ym: real; write('Введите Xm, Ym >> '); readln(Xm, Ym);

//Найдем сумму треугольников, одна из вершин которой - исходная точка, а две другие - вершины треугольника //Всего таких треугольников будет 3

var S1:=abs(1/2*((Xa-Xm)(Yb-Ym)-(Xb-Xm)(Ya-Ym))); var S2:=abs(1/2*((Xa-Xc)(Ym-Yc)-(Xm-Xc)(Ya-Yc))); var S3:=abs(1/2*((Xm-Xc)(Yb-Yc)-(Xb-Xc)(Ym-Yc)));

var S:=S1+S2+S3;

//Проверяем, “складывается” ли из этих треугольников искомый

if S=So then println(‘Точка принадлежит треугольнику’) else println(‘Точка не принадлежит треугольнику’);

end.

[fSHARP]

На лекциях было предложено реализовать нерекурсивный вариант решения классической задачи про Ханои.

Рекурсивный вариант из лекции:

procedure Hanoi(f, t, w, n: integer);
begin
  if n = 0 then
    exit;
  Hanoi(f, w, t, n-1);
  WritelnFormat('Перенести с {0} на {1}.', f, t);
  Hanoi(w, t, f, n-1);
end;

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

type
  HanoiNode = auto class
    f, t, w, n: integer;
    function Shift: HanoiNode;
    begin
      WritelnFormat('Перенести с {0} на {1}.', f, t);
      Result := Self;
    end;
  end;

procedure Hanoi(f, t, w, n: integer);
begin
  var s := new Stack<HanoiNode>;
  var disc := new HanoiNode(f, t, w, n);

  while (s.Count > 0) or (disc.n > 0) do
  begin
    if disc.n > 0 then
    begin
      s.Push(disc);
      // Условно принимаем в рассмотрение корень всего левого поддерева
      disc := new HanoiNode(disc.f, disc.w, disc.t, disc.n - 1);
    end
    else begin
      // Принимаем в рассмотрение корень и сразу выводим сообщение о переносе
      disc := s.Pop.Shift;
      // Условно принимаем в рассмотрение корень всего правого поддерева
      disc := new HanoiNode(disc.w, disc.t, disc.f, disc.n - 1);
    end;
  end;
end;

[Admin]

Да, принимается. Только метод Shift какой-то странный - функция с побочным действием печати значения

[RAlex]

В книге С.А.Абрамов. “Математические построения и программирование”, М., Наука, 1978 глава III параграф 5 приведен отличный разбор задачи “Ханойские башни”, в частности, избавление от рекурсии. Вообще книжечка полезная. Там и деревья и многое другое.