ОП лекции 2017-18 гг. - решение домашних заданий

16 сообщений перенесены в новую тему: Новые языки программирования за последние 10 лет

Сообщение перенесено в новую тему: ОП лекции 2017 - информация, материалы

Про задачу с треугольником и точкой внутри него. Можно ли соединить точку со всеми тремя вершинами, посчитать площадь трёх треугольников и если она равна площади исходного, то точка внутри ∆, иначе — за пределами ∆

Да, можно. Но вычисления с вещественными - приближённые. Пишите код :slight_smile:

Сообщение перенесено в тему Новые языки программирования за последние 10 лет

Сообщение перенесено в тему Новые языки программирования за последние 10 лет

Попыталась накидать алгоритм решения домашней задачи про возведения числа х в n-ую степень наименьшим количеством операций К сожалению годного кода написать не получилось, но хоть так🤷🏽‍♀️

Power меня тут смущает. Power нельзя пользоваться - она сама тянет за собой десятки умножений.

Домашняя работа, варианты округления 0,5 к ближайшему целому.

Отдельного описания требуют правила округления для специального случая, когда (N+1)-й знак = 5, а последующие знаки равны нулю. Если во всех остальных случаях округление до ближайшего целого обеспечивает меньшую погрешность округления, то данный частный случай характерен тем, что для однократного округления формально безразлично, производить его «вверх» или «вниз» — в обоих случаях вносится погрешность ровно в 1/2 младшего разряда. Существуют следующие варианты правила округления до ближайшего целого для данного случая:

  1. Математическое округление — округление всегда в бо́льшую по модулю сторону (предыдущий разряд всегда увеличивается на единицу).
  2. Банковское округление — округление для этого случая происходит к ближайшему чётному, то есть 2,5 → 2, 3,5 → 4.
  3. Случайное округление — округление происходит в меньшую или большую сторону в случайном порядке, но с равной вероятностью (может использоваться в статистике). Также часто используется округление с неравными вероятностями (вероятность округления вверх равна дробной части), этот способ делает накопление ошибок случайной величиной с нулевым математическим ожиданием.
  4. Чередующееся округление — округление происходит в меньшую или большую сторону поочерёдно.

Во всех вариантах в случае, когда (N+1)-й знак не равен 5 или последующие знаки не равны нулю, округление происходит по обычным правилам: 2,49 → 2; 2,51 → 3.

1 лайк

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

function BetweenR(m, l1, l2: real):boolean;
begin
  BetweenR:= ( m < l1) and (m >= l2) or (m > l1) and (m <= l2);
end;

begin
  var (x1, y1):= readReal2;
  var (x2, y2):= readReal2;
  var (x3, y3):= readReal2;
  var (xm, ym):= readReal2;
  var n:integer:= 0;
  if BetweenR(ym, y1, y2) then
    if xm <= x1 + (ym - y1) / (y2 - y1) * (x2 - x1) then
      n+=1;
  if BetweenR(ym, y2, y3) then
    if xm <= x2 + (ym - y2) / (y3 - y2) * (x3 - x2) then
      n+=1;
  if BetweenR(ym, y3, y1) then
    if xm <= x3 + (ym - y3) / (y1 - y3) * (x1 - x3) then
      n+=1;
  if (y1 = y2) and (y1 = ym) or
     (y2 = y3) and (y2 = ym) or
     (y1 = y3) and (y1 = ym) then n+=1;
  Writeln(odd(n));
end.

Принцип решения основан на принципе определения положения точки с помощью проведения луча из точки и подсчетом, сколько раз этот луч пересек стороны многоугольника. Если кол-во пересечений нечетно - лежит внутри, четно - снаружи. Интересные исключения те, когда луч проходит через вершину. Для удобства я брал луч параллельный ОХ. . Таким образом, я сравнивал сначала, лежит ли Ум между ординатами отрезков, а потом лежит “слева” или “справа” от отрезка с помощью хитрых формул. Создавал отдельную функцию, подобную Between, но с одним нестрогим сравнением. Необходимо было для обработки случаев, когда луч пересекал вершину. Единственное исключение, которое надо было отдельно обработать - когда луч совпадает с какой-то из сторон. Т.е. когда отрезок параллелен ОХ, а так же точка лежит на этой стороне. Жду комментариев от других, явно, что мой код не идеален.

Возведение в степень n числа a. Надеюсь, ничего страшного, если я написал на C++. Функции в паскале ещё не изучал

double my_power(double a, int n) {
	if(n==2) {
		return a*a;
	}
	if(n%2==0) {
		return my_power(a, n/2)*my_power(a, n/2);
	} else {
		return my_power(a, n/2)*my_power(a, n/2)*a;
	}
}

Задача про определение расположение точки( внутри или вне треугольника) Так же как и в прошлый раз только идея🤷🏽‍♀️ Нужно рассматривать 2 основных случая : 1) когда наиб у один 2) когда наиб у два И дальше долгое составление уравнений прямых, которые содержат стороны треугольника и, соответственно, подставление в эти уравнения координаты точки м. Если при такой подстановке выполняется требуемое неравенство ( либо больше либо меньше в зависимости от того о какой стороне идёт речь; имеется ввиду( рис 1) что например, здесь тоска должна находиться ниже ав и вс и выше ас, а на рис 2 ниже вс и выше ав и са), то точка имеет верное положение. Невыполнение хотя бы одного из неравенств исключает возможность нахождения точки внутри треугольника.

Тут конечно много повторяющихся вычислений. my_power(a, n/2) следует вначале вычислить в отдельной переменной, а то умножений будет всё равно n-1. И else по идее не нужно - всё равно return есть

Про отдельную переменную я вспомнил, когда уже вышел из дома C else для меня более читабельно, чем без

double my_power(double a, int n) {
	if(n==2) {
		return a*a;
	}
	double x = my_power(a, n/2);
	if(n%2==0) {
		return x*x;
	} else {
		return x*x*a;
	}
}

Просто если есть return, то else не пишется

Решение задачи на определение нахождения точки внутри треугольника с помощью псевдоскалярного произведения. https://pastebin.com/CjjKKshZ

Моя вариация на тему возведения в степень с наименьшим количество *. Постарался убрать не только * но и другие затратные действия, там / например. Без костылей не обошлось, но работать должен быстро.

Function Exp (a:Real;n:word):Real;
begin
  result := 1;
  While n > 1 do
  begin
    if Odd(n) then
      Result := (Result=1)?a:(Result*a);
    n := n shr 1;
    a *= a;
  end;
  Result := (Result=1)?a:(Result*a);
end;

Задание про точку внутри треугольника. Программа построена на принципе, подсказанным Ириной Алексеевной Чернявской. Функция Checkpoint составляет уравнение стороны треугольника по его двум точкам и подставляет другую точку в это уравнение. Знак полученного выражения определяет по какую сторону лежит точка с координатами x3 y3. Если знаки равны, то точки лежат по одну сторону от прямой. Если точка М будет иметь одинаковый знак относительно каждой прямой с соответственной точкой вершины, то точка М лежит внутри треугольника.

Лог программы
1.
Введите координаты точки А 3
3
Введите координаты точки В 4
10
Введите координаты точки С 9
6
Введите координаты точки М 7
9
Точка М не лежит внутри треугольника АВС 

2.
Введите координаты точки А -3
-2
Введите координаты точки В -6
3
Введите координаты точки С 2
5
Введите координаты точки М -2
1
Точка М лежит внутри треугольника АВС 

3.
Введите координаты точки А -3
-2
Введите координаты точки В -6
3
Введите координаты точки С 2
5
Введите координаты точки М -7
-3
Точка М не лежит внутри треугольника АВС 

}
function Checkpoint(x1, y1, x2, y2, x3, y3 : real): integer ;
begin
  Result := sign((y3 - y1) * (x2 - x1) - (x3-x1) * (y2 - y1));
end;

begin
  var (xа, yа) := ReadReal2('Введите координаты точки А');
  var (xb, yb) := ReadReal2('Введите координаты точки В');
  var (xc, yc) := ReadReal2('Введите координаты точки С');
  var (xm, ym) := ReadReal2('Введите координаты точки М');
  if (Checkpoint(xа, yа, xb, yb, xm, ym) = Checkpoint(xа, yа, xb, yb, xc, yc))
  and (Checkpoint(xb, yb, xc, yc, xа, yа) = Checkpoint(xb, yb, xc, yc, xm, ym)) 
  and (Checkpoint(xа, yа, xc, yc, xb, yb) = Checkpoint(xа, yа, xc, yc, xm, ym)) then
    print('Точка М лежит внутри треугольника АВС')
  else 
    print('Точка М не лежит внутри треугольника АВС');
  
  
end.

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

Введите координаты точки А 2 3 Введите координаты точки В 3 7 Введите координаты точки С 9 4 Введите координаты точки D 6 -3 Выпуклый четырехугольник существует

Введите координаты точки А -5 -4 Введите координаты точки В -2 3 Введите координаты точки С 5 -5 Введите координаты точки D 7 5 Четырехугольник не существует

Введите координаты точки А -5 -4 Введите координаты точки В -2 3 Введите координаты точки С 7 5 Введите координаты точки D 5 -5 Выпуклый четырехугольник существует

function Checkpoint(x1, y1, x2, y2, x3, y3: real): integer ;
begin
  Result := sign((y3 - y1) * (x2 - x1) - (x3 - x1) * (y2 - y1));
end;

begin
  var (xa, ya) := ReadReal2('Введите координаты точки А');
  var (xb, yb) := ReadReal2('Введите координаты точки В');
  var (xc, yc) := ReadReal2('Введите координаты точки С');
  var (xd, yd) := ReadReal2('Введите координаты точки D');
  if (Checkpoint(xa, ya, xb, yb, xc, yc) = Checkpoint(xa, ya, xb, yb, xd, yd)) and 
 (Checkpoint(xb, yb, xc, yc, xa, ya) = Checkpoint(xb, yb, xc, yc, xd, yd)) then
    print('Выпуклый четырехугольник существует')
  else print('Четырехугольник не существует');
end.

program task; begin var (x1, y1):= readreal2 ('введите координаты первой точки: '); var (x2, y2):= readreal2 ('введите координаты второй точки: '); var (x3, y3):= readreal2 ('введите координаты третьей точки: ');

//находим значения A, B, C для формирования общих уравнений прямых для каждой стороны

var (A12, A23, A31):= (y1-y2,y2-y3,y3-y1); var (B12, B23, B31):= (x2-x1,x3-x2,x1-x3); var (C12, C23, C31):= (x1y2-x2y1,x2y3-x3y2,x3y1-x1y3); var (x,y):=readreal2 ('введите координаты точки: '); //проверяем совпадение знака при подстановке третьей точки в уравнение прямой и даной точки //таким образом убеждаемся, что они лежат с однй стороны от данной прямой

if ( sign(a12x + b12y + c12) = sign(a12x3 + b12y3 +c12) ) and ( sign(a23x + b23y + c23) = sign(a23x1 + b23y1 +c23) ) and ( sign(a31x + b31y + c31) = sign(a31x2 + b31y2 +c31) ) then writeln (‘точка лежит внутри треугольника’) else writeln (‘точка не лежит внутри треугольника’); end.

{введите координаты первой точки: 34.5 11.8 введите координаты второй точки: 22.8 4 введите координаты третьей точки: 196.3 5 введите координаты точки: 120 -5 точка не лежит внутри треугольника}

{введите координаты первой точки: 3 3 введите координаты второй точки: 3 3 введите координаты третьей точки: 3 3 введите координаты точки: 3 3 точка лежит внутри треугольника}