1. Набрать по образцу следующий текст Стоит в поле теремок-теремок, Он не низок не высок, не высок. Как по полю, полю зайка бежит, У дверей остановился и кричит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? - Я, мышка-норушка. - Я, лягушка-квакушка! А ты кто? - Я зайчик-попрыгайчик! - Иди к нам жить! Стоит в поле теремок-теремок, Он не низок не высок, не высок. Уж как по полю лягушка бежит, У дверей остановилась и кричит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? - Я, мышка-норушка. А ты кто? - Я лягушка-квакушка! - Иди ко мне жить! Стоит в поле теремок-теремок, Он не низок не высок, не высок. Как по полю, полю мышка бежит, У дверей остановилась и пищит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? Никого в тереме нет. Залезла мышка в теремок, стала жить-поживать – песни распевать. Стоит в поле теремок-теремок, Он не низок не высок, не высок. Уж как по полю лисичка бежит, У дверей остановилась и кричит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? - Я, мышка-норушка - Я, лягушка-квакушка! - Я, зайчик-попрыгайчик! А ты кто? - Я лисичка-сестричка! - Иди к нам жить! 2. С перемещения и удаления фрагментов привести текст в «порядок» 3. Сохранить документ в папке со своей фамилией на рабочем столе («Практическая работа №2»

Информатика

Ответить

Ответы

Альберт Татьяна

02.05.2022

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

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

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

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

1. Набрать по образцу следующий текст Стоит в поле теремок-теремок, Он не низок не высок, не высок. Как по полю, полю зайка бежит, У дверей остановился и кричит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? - Я, мышка-норушка. - Я, лягушка-квакушка! А ты кто? - Я зайчик-попрыгайчик! - Иди к нам жить! Стоит в поле теремок-теремок, Он не низок не высок, не высок. Уж как по полю лягушка бежит, У дверей остановилась и кричит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? - Я, мышка-норушка. А ты кто? - Я лягушка-квакушка! - Иди ко мне жить! Стоит в поле теремок-теремок, Он не низок не высок, не высок. Как по полю, полю мышка бежит, У дверей остановилась и пищит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? Никого в тереме нет. Залезла мышка в теремок, стала жить-поживать – песни распевать. Стоит в поле теремок-теремок, Он не низок не высок, не высок. Уж как по полю лисичка бежит, У дверей остановилась и кричит: Кто, кто в теремочке живет? Кто, кто невысоком живет? Кто в тереме живет? - Я, мышка-норушка - Я, лягушка-квакушка! - Я, зайчик-попрыгайчик! А ты кто? - Я лисичка-сестричка! - Иди к нам жить! 2. С перемещения и удаления фрагментов привести текст в «порядок» 3. Сохранить документ в папке со своей фамилией на рабочем столе («Практическая работа №2»

Ответы

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

Ваше имя (никнейм)*

Email*

Комментарий*

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

Сколько раз будет выполнен этот цикл ? i=3 while i<6: print("Привет!") i+=1

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

Определите тип алгоритма "всегда"

Что не является стандартом сотовой связи? 1) gsm 2) cdma 3) mms 4) nmt 5) d-amps

Найдите объём стереофайла, длитильность звучания которого составляет 1 минута, глубина кодирования 16 бит, чистота дискритизации 48кгц

Опишите каждую строку программы tovar1=50 tovar2=32 if tovar1+tovar2 print(“ 99 рублей недостаточно»)else: print(“чек оплачен”)

Объясните в чем заключаются преимущество Web-страницы пред обычными текстовыми документами

Дано натуральное число. делится ли оно на 5? (информатика)

Ответы

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

Ваше имя (никнейм)*

Email*

Комментарий*

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

Сколько раз будет выполнен этот цикл ? i=3 while i&lt;6: print("Привет!") i+=1

Программа кумир. какие команды нужно ввести, чтобы робот переместился в обозначеную клетку? ​

Определите тип алгоритма "всегда"​

Что не является стандартом сотовой связи? 1) gsm 2) cdma 3) mms 4) nmt 5) d-amps

Найдите объём стереофайла, длитильность звучания которого составляет 1 минута, глубина кодирования 16 бит, чистота дискритизации 48кгц

Опишите каждую строку программы tovar1=50 tovar2=32 if tovar1+tovar2 print(“ 99 рублей недостаточно»)else: print(“чек оплачен”)

Объясните в чем заключаются преимущество Web-страницы пред обычными текстовыми документами

Дано натуральное число. делится ли оно на 5? (информатика)

Сколько раз будет выполнен этот цикл ? i=3 while i<6: print("Привет!") i+=1

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

Определите тип алгоритма "всегда"