cipfarm484
?>

с 3 заданиями Только ответы

Информатика

Ответы

marani2
Const
  n=15;
var
  i,np,nn,amax:integer;
  a:array[1..n] of integer;
begin
  Randomize;
  Write('Исходный массив: ');
  np:=0; nn:=0;
  for i:=1 to n do begin
    a[i]:=Random(51)-15;
    Write(a[i],' ');
    if a[i]>0 then Inc(np)
    else if a[i]<0 then Inc(nn);
    end;
  Writeln;
  if np/nn>2 then begin
    amax:=a[i];
    for i:=2 to n do
      if a[i]>amax then amax:=a[i];
    Write('Выходной массив: ');
    for i:=1 to n do begin
      if a[i]<0 then a[i]:=1
      else
        if a[i]>0 then a[i]:=a[i]*amax;
      Write(a[i],' ')
      end;
    Writeln
    end
  else Writeln('В массив изменения не вносятся')
end.

Пример работы программы
Исходный массив: 28 8 21 32 0 26 30 11 35 21 14 6 0 -4 -8
Выходной массив: 980 280 735 1120 0 910 1050 385 1225 735 490 210 0 1 1
infooem
Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в 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}

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

Ответить на вопрос

Поделитесь своими знаниями, ответьте на вопрос:

с 3 заданиями Только ответы
Ваше имя (никнейм)*
Email*
Комментарий*

Популярные вопросы в разделе

fruktovahere
ski89439
Tatarnikova1507
margarita25061961
M10M11M12
tanysha1990
vikanikita
Neveselova
diana-kampoteks
Sharmel26
ss2911
mishapavlov9
kuchin
zagadka27
Chistova-Dmitrii1162