Курс ОП ФИИТ 1 семестр 2020 год (старое)

Материалы буду выкладывать - здесь

Презентации: https://drive.google.com/drive/folders/1N0LzbJDtMNeYUPq3ZPMeLbMm3uoMRWJC?usp=sharing

1 лайк

Не знаю, сюда или нет, это задание с лекции

upd: Деление исправил

///Проверить, лежит ли точка М внутри треугольника ABC
##
var (Ax, Ay) := readreal2('Введите координаты A: ');
var (Bx, By) := readreal2('Введите координаты B: ');
var (Cx, Cy) := readreal2('Введите координаты C: ');
var (Mx, My) := readreal2('Введите координаты M: ');

var(Ox, Oy) := ((Ax + Bx + Cx) / 3, (Ay + By + Cy) / 3);//Координаты точки пересечения медиан
//Уравнение прямой по двум точкам (y-y1)/(y2-y1)=(x-x1)/(x2-x1) <=> (y-y1)*(x2-x1)-(x-x1)*(y2-y1)=0
var b1 := (Oy - Ay) * (Bx - Ax) - (Ox - Ax) * (By - Ay) > 0;//Положение точки O относительно прямой AB (выше=1/ниже=0)
var b2 := (Oy - Ay) * (Cx - Ax) - (Ox - Ax) * (Cy - Ay) > 0;//Положение точки O относительно прямой AС (выше=1/ниже=0)
var b3 := (Oy - By) * (Cx - Bx) - (Ox - Bx) * (Cy - By) > 0;//Положение точки O относительно прямой BC (выше=1/ниже=0)

if (((My - Ay) * (Bx - Ax) - (Mx - Ax) * (By - Ay) > 0) = b1) and
    (((My - Ay) * (Cx - Ax) - (Mx - Ax) * (Cy - Ay) > 0) = b2) and
      (((My - By) * (Cx - Bx) - (Mx - Bx) * (Cy - By) > 0) = b3) then
  print('Yes')//Если положение точки М относительно прямых AB, BC и AC такое же, как и у точки O, то M находится внутри треугольника
else
  print('No'); 

Сюда. Текст надо форматировать так:

```pascal
...
```

Вижу потенциальное деление на 0. То есть, вертикальные прямые запрещены?

//Алгоритм возведения в степень. Попытка сделать минимальное количество умножений/делений.
begin
  var a := ReadInteger('Введите число');
  var n := ReadInteger('Введите степень');
  var c := 1;
  var a1 := a;
  
  var k := 0; //счётчик умножений/делений
  
  while (c + c div 2) < n do //идём к ближайшей к n степени двойки: a^2, a^4, a^8...
  begin
    c += c;
    a1 *= a1;
    k += 1;
  end;
  
  if c >= n then //умножаем или делим на a, чтобы дойти до a^n
    for var i := 1 to (c - n) do
    begin
      a1 := a1 div a;
      k += 1;
    end
  else
    for var i := 1 to (n - c) do
    begin
      a1 *= a;
      k += 1;
    end;
      
      
  PrintLn($'Результат: {a1}, количество умножений: {k}');
end.

Делить нельзя :slight_smile:

Я говорил, что возможно a - это квадратная матрица - их умножать можно, а div для них нет

Похоже, только delphi работает %)

У тебя алгоритм выдает не самое минимальное значение. Нельзя все сводить к степени двойки. Очень часто это не оптимально. Вообще в данной задаче получить степень N можно тремя способами:

  1. Увеличить предыдущую степень на 1 за счет умножения на a (a^(n-1)*a)
  2. Умножить текущую степень на себя k раз (И совершенно не обязательно 2). Например: a^12a^12a^12=a^36
  3. Сложить две некоторые степени. Например: a^8*a^12=a^20

Я тоже написал алгоритм и он выдает несколько меньшее кол-во умножений чем твой. В нем я руководствовался тем что 3-ий способ не может быть эффективным так как очень дорого набирать вторую степень. Но я могу ошибаться.

В остальном же я делаю динамику где i - степень, а dp[i] - минимальное количество умножений для возведения в степень i.

Число a я не рассматриваю, так как кол-во умножений от него не зависит.

```pascal

begin
  var n := ReadInteger();//Считываем требуемую степень
  Assert(n > 1);
  var dp := ArrFill(n + 1, 0);//Создаем массив для динамического программирования. В i-той ячейке храним минимальное количество умножений для степени i
  var prev := ArrFill(n + 1, 0); //Создаем массив для восстановления порядка степеней
  dp[0] := 0;//задаем нули динамики
  dp[1] := 0;
  for var i := 2 to n do
  begin
    var min1 := dp[i - 1] + 1;//количество умножений если увеличиваем степень i-1 на один
    var min2 := integer.MaxValue;//количество умножений если какую-то степень умножать на саму себя некоторое количество раз
    var curPrev1 := i - 1;//предыдущая степень от 1-ого способа
    var curPrev2 := 0;//предыдущая степень от второго способа
    for var j := 2 to i - 1 do
    begin
      if((i mod j) = 0) then //степень обязательно должна быть кратна той которая умножается на саму себя
      begin
        var t := i div j - 1 + dp[j];//вычисление количества умножений для такого способа
        if(t < min2) then//нахождения лучшего варианта по второму способу
        begin
          min2 := t;
          curPrev2 := j;
        end;
      end;
    end;
    dp[i] := Min(min1, min2);//выбор лучшего из спосбов для i-той степени
    if(min1 <= min2) then
      prev[i] := curPrev1
    else
      prev[i] := curPrev2;
  end;
  Println($'Минимальное количество умножений равно {dp[n]}');
  var next := prev[N];
  var mas := ArrFill(dp[n] + 1, 0);
  mas[0] := n;
  for var i := 1 to dp[N] do//восстановление порядка степеней
  begin
    mas[i] := next;
    next := prev[next];
  end;
  Print('Порядок степеней: ');
  mas.Reverse.print;
  
  
end.
1 лайк
//Проверить, принадлежит ли точка М внутренности треугольника ABC
begin
 var (Ax,Ay,Bx,By) :=ReadInteger4('Введите координаты точек A и B - Ax,Ay,Bx,By:');
 var (Cx,Cy,Mx,My) :=ReadInteger4('Введите координаты точек C и M - Cx,Cy,Mx,My:');
 var (m1,m2):= (Ax,Ay); // Максимальные координаты (x,y) среди вершин треугольника ABC 
 var (m3,m4):= (Cx,Cy); // Минимальные координаты (x,y) среди вершин треугольника ABC
 
 m1:= Max(Ax,Bx,Cx); // Находим максимальную координату по x среди вершин треугольника ABC
 m3:= Min(Ax,Bx,Cx); // Находим минимальную координату по x среди вершин треугольника ABC
 
 m2:= Max(Ay,By,Cy); // Находим максимальную координату по y среди вершин треугольника ABC
 m4:= Min(Ay,By,Cy); // Находим минимальную координату по y среди вершин треугольника ABC
  
 {
 Если координаты точки M(Mx,My) находятся в промежутках 
 от минимальной до максимальной координаты по (x,y) среди вершин треугольника ABC, 
 то точка М принадлежит внутренности треугольника ABC
 }
 if (Mx <= m1) and (My <= m2) and (Mx >= m3) and (My >= m4) then 
   print('Результат: Точка М принадлежит внутренности треугольника ABC')
 
 else
   print('Результат: Точка М не принадлежит внутренности треугольника ABC')
end.

// Логи 
{
 A(1,1); B(2,3); С(3,2); M(2,2) >>> Точка М принадлежит внутренности треугольника ABC
 A(1,1); B(2,3); С(3,2); M(3,4) >>> Точка М не принадлежит внутренности треугольника ABC
 A(-1,-1); B(-2,-3); С(-3,-2); M(-2,-2) >>> Точка М принадлежит внутренности треугольника ABC
}
1 лайк

Это наверное не так: рассмотрим прямоугольник, описанный вокруг треугольника, со сторонами, параллельными осям. Очевидно, есть точка внутри прямоугольника, но не внутри четырёхугольника.

```pascal

{Даны точки ABCD, при этом никакие три не лежат на одной прямой. 
 Проверить, является ли ABCD четырехугольником.}

begin
  // Ввод четырех точек
  var (x1, y1) := readreal2('Введите координаты A:');
  var (x2, y2) := readreal2('Введите координаты B:');
  var (x3, y3) := readreal2('Введите координаты C:');
  var (x4, y4) := readreal2('Введите координаты D:');
  // уравнение прямой AB
  var A1 := y2 - y1;
  var B1 := -(x2 - x1);
  var C1 := -x1 * (y2 - y1) + y1 * (x2 - x1);
  // лежат ли точки C и D по одну сторону от AB 
  if (a1 * x3 + b1 * y3 + c1 > 0) = (a1 * x4 + b1 * y4 + c1 > 0) then
  begin
    // уравнение прямой ac
    var A5 := y3 - y1;
    var B5 := -(x3 - x1);
    var C5 := -x1 * (y3 - y1) + y1 * (x3 - x1);
    // уравнение прямой bd
    var A6 := y4 - y2;
    var B6 := -(x4 - x2);
    var C6 := -x2 * (y4 - y2) + y2 * (x4 - x2);
    // ищем точку пересечения (x,y) диагоналей AC и BD
    var x, y : real;
    // проверка на 0 в знаменателе
    if (a5 = 0) then    
      if (a6 = 0) then
      begin
      // диагонали параллельны -> abcd не прямоугольник
        print('ABCD не является четырехугольником.');
        exit;
      end
      else
      begin
        y := -c5 / b5;
        x := (-c6 - b6 * y) / a6;
      end
    else
    begin
      y := (-c6 + c5 * a6 / a5) / (b6 - b5 * a6 / a5);
      x := (-c5 - b5 * y) / a5;
    end;
    // (x,y) должна находится либо внутри треугольника ABD, либо на одной из его сторон
    var a := (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);
    var b := (x2 - x) * (y4 - y2) - (x4 - x2) * (y2 - y);
    var c := (x4 - x) * (y1 - y4) - (x1 - x4) * (y4 - y);
    if ((a > 0) and (b > 0) and (c > 0)) or ((a < 0) and (b < 0) and (c < 0)) or (a = 0) or (b = 0) or (c = 0) then
      print('ABCD является четырехугольником.')
    else
      print('ABCD не является четырехугольником.');
  end
  else
    print('ABCD не является четырехугольником.');
end.