Решить по блок - схеме составить программу и определить сумму какхи элементов массива вычисляет программа

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

Итак, должно выполняться


Подставив в исходную формулу, получаем


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

#include <iostream>

#include <vector>

#include <fstream>

#include <algorithm>

using namespace std;

class pacient {

private:

 string lastName_m, mOrFM_m, adress_m, diagnosis_m;

public:

 pacient(string lastName = "", string mOrFM = "", string adress = " ", string diagnosis = " ") {

  lastName_m = lastName;

  mOrFM_m = mOrFM;

  adress_m = adress;

  diagnosis_m = diagnosis;

 }

 string getLastName() {

  return lastName_m;

 }

 string getAll() {

  return lastName_m + ", " + mOrFM_m + ", " + adress_m + ", " + diagnosis_m + ".";

 }

};  

int main() {

fstream out("output.txt");

setlocale(LC_ALL, "Russian");

vector<pacient> arr;

for(int i = 0;;++i) {

 string a[4];

 for(int j = 0; j<4; ++j) {

  switch(j) {

   case 0: cout << "Last name: "; break;

   case 1: cout << "Male or FeMale: "; break;

   case 2: cout << "Adress: "; break;

   case 3: cout << "Diagnosis: "; break;

  }

  getline(cin, a[j]);

 }

 pacient temp(a[0], a[1], a[2], a[3]);

 cout << "Для окончания ввода введите 1: ";

 arr.push_back(temp);

 string temp1;

 getline(cin, temp1);

 if(temp1=="1") {

  break;

 }

}

for(int j = 0; j<1000; ++j) {

for(int i = 0; i<arr.size()-1; ++i) {

 if(arr[i].getLastName()[0]>arr[i+1].getLastName()[0]) {

  swap(arr[i], arr[i+1]);

 }

} }

for(int i = 0; i<arr.size(); ++i) {

 cout << arr[i].getLastName() << endl;

 out << arr[i].getAll();

 out << "\n";

}

out.close();

}