Информатика: Дано обязательно и решение со всеми формулами! очень

Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в i-ой компоненте связности вершин, то общее число рёбер будет суммой по всем компонентам связности:Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K 1.Предположим, n1 = n2 = ... = nK - набор чисел,...

Дано обязательно и решение со всеми формулами! очень

Нажмите на рекламу ниже и сразу увидите ответ

↓

Популярные вопросы:

karina941

18.12.2021 17:44

Составе программу ввода с клавиатуры элементов массива а[1..8] и вывода элементов массива в обратном порядке...

Шишкин555

18.12.2021 17:44

Найдите значение логического выражения а и в или а; если а=1, в=0...

zyzae

22.09.2021 02:05

Нужно нарисовать скатывающийся по ступенькам шар в pascal abc. , )...

СуПерКотАйН

16.12.2021 11:51

Втерминологии сетей tcp/ip маской сети называется двоичное число, определяющее, какая часть ip-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в...

Vitaly536218

18.09.2020 02:39

Нужно сделать конвертер валют в javascript...

оеавц

14.11.2022 23:32

Операционная система windows: основные понятия, характеристики, структура. что означает разрядность операционной системы. нигде не могу найти эту информацию!...

kik678

18.04.2023 08:21

Какое будет решение этой задачи?ЭВМ запрашивает: “Сколько будет 2 + 2?”. Если ответ верен, то отвечает: “Молодец!”. В противном случае: “Запомните: 2 + 2 = 4!”....

arabenko

14.04.2022 14:43

Програму напишите в pascalabc по рисунку !...

зика356

07.08.2021 21:44

Типы меню в операционной системе windows 7....

sludkov

15.07.2020 10:06

Вкоробке меньше 9, но больше 3 шаров. сколько шаров может быть в коробке? а) 3; в) 9; с) 2; d) 5; е) 10....

Ответ:

Белоснежка333

16.09.2022 22:29

Для начала нужно отформатировать каждый заголовок, который Вы хотите, чтобы был в Оглавлении, с автостилей. Для этого заходим на вкладку "главная", далее панель "стили", выделяем нужный заголовок и нажимаем "Заголовок 1", так делает с каждым заголовком по всему тексту. Если вам нужен подпункт в оглавлении, то тогда выделяем его и там же в панели "стили" выбираем "Заголовок 2". Аналогично можно сделать ещё подпункты, выбрав "Заголовок 3".

Когда Вы сделаете так со всеми заголовками, дальше можно создавать оглавление. Устанавливаем курсор, где хотим, чтобы было оглавление. Если для оглавления вам нужная отдельная страница, то вставляем разрыв до и после оглавления (Ctrl+Enter). После этого переходим во вкладку "ссылки", дальше слева в группе "оглавление" выбираем "Автособираемое оглавление 1". После этого будет создано оглавление на основе ваших выделенных заголовков. Каждый из заголовков будет снабжён отбивкой из точек, после них будет стоять номер страницы (если он есть), на которой этот заголовок находится.

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

Указатель устанавливается по желанию для того, чтобы, нажимая на необходимый заголовок, переходить по ссылке на его содержание (если Вы будете распечатывать документ, то он точно не понадобится). Для того, чтобы сделать указание нужно выбрать текст, который будет элементом предметного указателя. Дальше на вкладке "ссылки", группа "предметный указатель" нажать "пометить элемент" и снова "пометить". После того как пометите все элементы (например, пункты или главы) выбираете место, где будет указатель, далее "ссылки", группа "предметный указатель" и команда "предметный указатель". Дальше выбираем нужный формат, номера страниц и нажимаем "ок". Предметный указатель будет готов.

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

Ответ:

Сашалажа

18.02.2021 00:11

Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в 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 оценок)

Полный доступ

Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку