Написать программу на С++ определения площади пятиугольника с заданными координатами его вершин (x1, y1), (x2, y2), (х3у3), (х4.y4), (х5,y5) как сумму площадей трех треугольников. Площадь треугольника, определенную по координатам вершин, рассчитать с функции.

Показать ответ

Ответ:

marisa10

09.05.2021 04:49

Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в i-ой компоненте связности n_i

вершин, то общее число рёбер будет суммой по всем компонентам связности:

$\displaystyle \sum_{i=1}^K\frac{n_i(n_i-1)}2=\frac12\sum_{i=1}^K n_i^2-\frac12\sum_{i=1}^Kn_i=\frac12\sum_{i=1}^K n_i^2-\frac N2$

Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.

Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.

Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов:
$\Delta(\sum n_i^2)=(1^2+(n_K+n_1-1)^2)-(n_1^2+n_K^2)=2(n_1-1)(n_K-1)$
Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.

Итак, должно выполняться
$n_1=n_2=\cdots=n_{K-1}=1;\qquad n_K=N-K+1$

Подставив в исходную формулу, получаем
$\displaystyle\frac{(N-K)(N-K+1)}{2}$

Это и есть ответ.

0,0(0 оценок)

Ответ:

vipvip16tk

13.12.2021 10:01

Const n=20;
var
a,b:array[1..n] of integer;
i,j,k,m,c:integer;
begin
Randomize;
writeln('Исходный массив:');
for i:=1 to n do
begin
a[i]:=random(51)-25;
write(a[i]:5);
end;
writeln;
j:=0;
for i:=1 to n do
if a[i]<0 then begin j:=j+1; b[j]:=a[i]; end;
m:=j;
for k := 1 to m-1 do
for i := 1 to m-k do
if (b[i]<b[i+1]) then
begin
c:=b[i]; b[i]:=b[i+1]; b[i+1]:=c;
end;
writeln('Вс массив:');
for i:=1 to m do write(b[i]:5);
writeln;
j:=0;
for i:=1 to n do
if a[i]<0 then begin j:=j+1; a[i]:=b[j]; end;
writeln('Полученный массив:');
for i:=1 to n do write(a[i]:5);
writeln;
end.

Пример:
Исходный массив:
-15 -8 -6 -13 15 24 5 -2 14 -1 19 -2 -7 -8 -23 20 -2 7 -2 -10
Вс массив:
-1 -2 -2 -2 -2 -6 -7 -8 -8 -10 -13 -15 -23
Полученный массив:
-1 -2 -2 -2 15 24 5 -2 14 -6 19 -7 -8 -8 -10 20 -13 7 -15 -23

0,0(0 оценок)

Популярные вопросы: Информатика