Вкорзине лежат красные и желтые шары красных шаров 14. сообщение о том что достали жёлтый шар несёт 3 бита информации. сколько всего шаров в корзине?
Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в i-ой компоненте связности вершин, то общее число рёбер будет суммой по всем компонентам связности:
Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.
Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.
Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов: Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
void arithmeticProgression(const int& first, const int& differense, const int& N){ // first - первый номер арифметической прогрессии // difference - разность // N - число, до которого продолжать прогрессию
static int sum = 0; // тут будет сумма static int callsNumber = 0; // считаем число вызовов функции для определения номера элемента последовательности int next = first + differense; // следующий элемент прогрессии sum += first; // подсчет суммы
if(callsNumber == N){ cout << "finally item: " << first << endl; cout << "sum: " << sum << endl; sum = 0; callsNumber = 0; return; // если следующий элемент идет по порядку больше N, то прервать рекурсию } else{ callsNumber++; arithmeticProgression(next, differense, N); // иначе делать тоже самое со следующим числом прогрессии } }
int main(){ arithmeticProgression(2, 3, 3); // пример вызова return 0; }
Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.
Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.
Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов:
Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
Итак, должно выполняться
Подставив в исходную формулу, получаем
Это и есть ответ.
using namespace std;
void arithmeticProgression(const int& first, const int& differense, const int& N){
// first - первый номер арифметической прогрессии
// difference - разность
// N - число, до которого продолжать прогрессию
static int sum = 0; // тут будет сумма
static int callsNumber = 0; // считаем число вызовов функции для определения номера элемента последовательности
int next = first + differense; // следующий элемент прогрессии
sum += first; // подсчет суммы
if(callsNumber == N){
cout << "finally item: " << first << endl;
cout << "sum: " << sum << endl;
sum = 0;
callsNumber = 0;
return; // если следующий элемент идет по порядку больше N, то прервать рекурсию
}
else{
callsNumber++;
arithmeticProgression(next, differense, N); // иначе делать тоже самое со следующим числом прогрессии
}
}
int main(){
arithmeticProgression(2, 3, 3); // пример вызова
return 0;
}