Курс Основы программирования (лекции) 1 семестр 2018-19 гг

Поддержка учебных курсов ФИИТ, 1 курс
#23

Первая задача. Проверка, находятся ли искомая точка по “правильную” сторону от отрезка треугольника с использованием сравнения знаков. В этом решении точка, лежащая на прямой считается частью треугольника.

//Функция проверяет знак, который имеет уравнение прямой при подстановке в него точки(её координаты - xx и yy)
//и точек, обозначающих прямую, составляющую сторону треугольника
function fu(xx,yy,m,n,l,k: real): real;
begin
  Result :=sign((xx-m)*(k-n)-(yy-n)*(l-m));
end;



begin
  var (x,y):=ReadInteger2('Введите координаты искомой точки');
  var (a,b):=ReadInteger2('Введите координаты первой точки треугольника');
  var (c,d):=ReadInteger2('Введите координаты второй точки треугольника');
  var (e,f):=ReadInteger2('Введите координаты третьей точки треугольника');
  if ((fu(x,y,a,b,c,d)=fu(e,f,a,b,c,d)) and (fu(x,y,e,f,c,d) = fu(a,b,e,f,c,d)) and (fu(x,y,e,f,a,b)=fu(c,d,e,f,a,b)))
  or (fu(x,y,a,b,c,d)=0) or (fu(x,y,e,f,c,d)=0) or (fu(x,y,a,b,e,f)=0) then
    writeln('Точка лежит внутри треугольника')
  else
    writeln('Точка не лежит внутри треугольника');
  
end.
#24

SSDD. Проверка на то, пересекаются ли все прямые. Если не пересекаются - прямоугольник, пересекаются - не он. Вероятно, можно и без последнего if но недостаточно данных для проверки.

function fu(xx,yy,m,n,l,k: real): real;
begin
  Result :=sign((xx-m)*(k-n)-(yy-n)*(l-m));
end;

begin
  var (x,y):=ReadInteger2('Введите координаты точки A');
  var (a,b):=ReadInteger2('Введите координаты точки B');
  var (c,d):=ReadInteger2('Введите координаты точки C');
  var (e,f):=ReadInteger2('Введите координаты точки D');
  if fu(c,d,x,y,a,b)<>fu(e,f,x,y,a,b) then
    writeln('Не является четырёхугольником')
  else if fu(x,y,a,b,c,d)<>fu(e,f,a,b,c,d) then
    writeln('Не является четырёхугольником')
  else if fu(a,b,c,d,e,f)<>fu(x,y,c,d,e,f) then
    writeln('Не является четырёхугольником')
  else if fu(c,d,e,f,x,y)<>fu(a,b,e,f,x,y) then
    writeln('Не является четырёхугольником')
  else
    writeln('Является четырёхугольником');
end.
#25

Задание про треугольник и точку. Программа находит площадь треугольника, затем мы подставляем точку вместо каждой из вершин и находим площади этих треугольников. Если разница площади данного треугольника и сумм треугольников, где мы подставляли точку вместо вершины, равна нулю, то точка лежит внутри треугольника.

 program Triangle;
//Вывести, принадлежит ли точка треугольнику
  function Square(x1,y1,x2,y2,x3,y3:real):real;
  begin
    Square:=abs((x1-x2)*(y3-y2)-(x3-x2)*(y1-y2))/2;
  end;  
begin
  var (xa,ya):=ReadReal2('Введите координаты точки A:');
  var (xb,yb):=ReadReal2('Введите координаты точки B:');
  var (xc,yc):=ReadReal2('Введите координаты точки C:');
  if Square(xa,ya,xb,yb,xc,yc)<=0 then
    println('Не является треугольником')
  else
    begin
      var (tmx,tmy):=ReadReal2('Введите координаты точки M:');
      var sum:real;
      sum:=Square(xa,ya,xb,yb,tmx,tmy)+Square(xa,ya,tmx,tmy,xc,yc)+Square(tmx,tmy,xb,yb,xc,yc);
      if abs(Square(xa,ya,xb,yb,xc,yc)-sum)<=0 then
        println('Точка принадлежит треугольнику')
      else
        println('Точка не принадлежит треугольнику');
    end;    
end.
#26

Тоже использовал алгоритм с площадями. Сначала находил расстояния между точками, потом считал площади по формуле Герона. В итоге получилось, что если точка лежит внутри треугольника, то программа выдаёт одинаковые значения для площади первого треугольника и суммы трёх других. Но, видимо, в двоичном коде получаются разные результаты, поэтому программа считает, площадь первого треугольника не равна сумме площадей трёх других и выдаёт неверный результат: Введите координаты первой вершины треугольника 1 1 Введите координаты второй вершины треугольника 4 1 Введите координаты третей вершины треугольника 1 4 Введите координаты проверяемой точки 2 2 4.5 1.5 1.5 1.5 //Площади треугольников 4.5 4.5 //Площадь первого и сумма площадей трёх других Точка находится не внутри треугольника При этом, если изменить условие s1=s2 на s1>=s2-0.000000000000001, всё работает

begin
r:=sqrt(sqr(x-x0)+sqr(y-y0));
end;

function s(q,r,t:real):real;
begin
var p:=(q+r+t)/2;
s:=sqrt(p*(p-q)*(p-r)*(p-t));
end;

begin
Var x1,x2,x3,x4,y1,y2,y3,y4:real;
(x1,y1):=readreal2('Введите координаты первой вершины треугольника');
(x2,y2):=readreal2('Введите координаты второй вершины треугольника');
(x3,y3):=readreal2('Введите координаты третей вершины треугольника');
(x4,y4):=readreal2('Введите координаты проверяемой точки');
Var a1,a2,a3,b1,b2,b3:real;
a1:=r(x1,y1,x2,y2);
a2:=r(x2,y2,x3,y3);
a3:=r(x1,y1,x3,y3);
b1:=r(x1,y1,x4,y4);
b2:=r(x2,y2,x4,y4);
b3:=r(x3,y3,x4,y4);
println(s(a1,a2,a3),s(a1,b1,b2),s(a2,b2,b3),s(b1,b3,a3) );
var s1,s2:real;
s1:=s(a1,a2,a3);
s2:=s(a1,b1,b2)+s(a2,b2,b3)+s(b1,b3,a3);
println(s1,s2);
if s1=s2 then
println ('Точка находится внутри треугольника')
else
println ('Точка находится не внутри треугольника');
end. ```
#27

Получаются вещественные числа, которые нельзя сравнивать на равенство

#28

А нельзя ли пояснить, какие именно знаки сравниваются?

#29

Алгоритм выглядит чисто. Но конечно многовато вычислений. Особенно функция Sqrt - вроде по сути задачи корни извлекать не надо

#30

Попробовал сравнить скорость нахождения корня с помощью стандартной функции и способа, предложенного на лекции. Узнать на практике что все-таки быстрее не получилось: одна и та же программа выдавала разные значения своей работы (даже 0 миллисекунд). Почему такая непостоянность? Привожу в пример вторую программу.

  var x := 17548826576.0;
  var a:= x;
  var b := real.MaxValue;
  var eps := 10E-15;
  while abs(a-b) >= eps do
    begin
    b:=a;
    a:= (a+ x/a)/2;
  end;
  print (a, Milliseconds);
end.
//Выводит 0, 7, 16, 20 или 22 миллисекунды(чаще всего 16)

P.S. Вопросы по бонусным заданиям задавать сюда?

#31

Надо обернуть это в большой цикл с 10000000 итераций - тогда время будет адекватное. Задавайте конечно

#32

Константа количества попыток всегда равна 15(просто если человек задаст себе диапазон в более чем 32000 чисел он может не угадать). P.S. Мне всегда надо удалять старые сообщения чтобы написать новые(просто писало что новые пользователи не могут оставлять более 3-х сообщений)

#33

Нет, это странное ограничение. Поднял Вам статус. Может, что изменится.

#34

Это реализация сдвига одноерного массива на К ячеек влево с тетта(n) Приношу извинеия за мой C#, он просто был под рукой.

class Program     
{        
   /// Меняет блок из К первых элементов с таким же по размеру блоком последних в массиве Х
    static void SwapArr(ref int[] x, int k)
    {
        int t; 
        for (int i = 0; i < k; i++)
        {
            t = x[i];
            x[i] = x[x.Length - k + i];
            x[x.Length - k + i] = t; 
        }
    } 
      /// Рекурсия! Возвращает суму из Изменённого массива как рекурсию какой-то части + правильно поставленный на место (в процедуре SwapArr) блок 
    static int[] ShiftLeft(int []x, int k)
    {
        if ((double)k == x.Length / 2.0)
        {
            SwapArr(ref x, x.Length / 2);
            return x;
        }
        else if (k < x.Length / 2.0)
        {
            SwapArr(ref x, k);
            int[] a = new int[x.Length - k];
            int[] b = new int[k];
            for (var i = 0; i < x.Length - k; i++)
                a[i] = x[i];
            for (var i = x.Length - k; i < x.Length; i++)
                b[i - a.Length] = x[i];
            int[] s = ShiftLeft(a, k); 
            int[] res = new int[a.Length + b.Length];
            for (var i = 0; i < s.Length; i++)
                res[i] = s[i];
            for (var i = 0; i < b.Length; i++)
                res[s.Length + i] = b[i];

            return res;
        }
        else if (k > x.Length / 2.0)
        {
            SwapArr(ref x, k - x.Length / 2);
            int[] a = new int[x.Length - k];
            int[] b = new int[k];
            for (var i = 0; i < x.Length - k; i++)
                a[i] = x[i];
            for (var i = x.Length - k; i < x.Length; i++)
                b[i - a.Length] = x[i];

            int[] s = ShiftLeft(b, k);
            int[] res = new int[a.Length + b.Length];
            for (var i = 0; i < a.Length; i++)
                res[i] = a[i];
            for (var i = 0; i < s.Length; i++)
                res[a.Length + i] = s[i];

            return res;
        }
        else
        {
            x = new int[0]; 
            return x;
        } 
    }

    static void Main(string[] args)
    {
        int[] p = new int[1000];
        for (int i = 0; i < p.Length; i++)
            p[i] = i + 1; 
        p = ShiftLeft(p, 250);
        string str = "";
        for (int i = 0; i < p.Length; i++)
        {
            str = str + p[i].ToString();
            str += ' '; 
        }
        Console.WriteLine(str);
        Console.ReadLine(); 
    }
}

}

Несмотря на то, что я не умею пользоваться срезами в C# и появляется ужасный программный стек, эта программа теоретически использует одну дополнительную ячейку памяти :joy:

Для справки: void = procedure, int = integer, static = неважно что, ref = var

#35

Сложновато. Хотелось бы более простой алгоритм увидеть.

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

Кстати, в C# нет срезов

#36

Добрый день, Станислав Станиславович! Вы нам обещали программу экзамена и конспекты лекций выложить на форуме. Хотелось бы узнать, когда мы сможем их увидеть?)

#37

А, прошу прощения, конспекты нашёл. А программа будет?

#38
1 лайк