Пусть в "долях" a <= b <= c вершин, и проведены все рёбра между разными "долями". Так как из каждой вершины, лежащей в первой "доле", можно провести только b + c рёбер, из второй доли — a + c рёбер, из третьей — a + b рёбер, то общее количество рёбер равно (a * (b + c) + b * (a + c) + c * (a + b))/2 = ab + ac + bc (деление на 2 возникает из-за того, что каждое ребро подсчитывается дважды). Нужны такие a, b, c, при которых значение выражения ab + bc + ac будет максимально. Максимальное значение можно найти перебором.
python 3: max_value = 0
for a in range(41//3 + 1): for b in range(a, (41 - a)//2 + 1): c = 41 - a - b value = a * b + a * c + b * c max_value = max(max_value, value)
// PascalABC.NET 3.3, сборка 1607 от 31.12.2017 // Внимание! Если программа не работает, обновите версию!
function GCD(a,b:integer):integer; // НОД begin while b<>0 do begin a:=a mod b; Swap(a,b) end; Result:=a end;
procedure RedFrac(var a,b:integer); // сокращение дроби begin var (sgna,sgnb):=(Sign(a),Sign(b)); // мы должны учитывать знак! (a,b):=(Abs(a),Abs(b)); var d:=Gcd(a,b); (a,b):=((a div d)*sgna,(b div d)*sgnb) end;
begin var (a,b):=ReadInteger2('Числитель и знаменатель 1-й дроби:'); var (c,d):=ReadInteger2('Числитель и знаменатель 2-й дроби:'); var (p,q):=(a*d+b*c,b*d); RedFrac(p,q); Writeln('Результат: ',p,'/',q) end.
Пример Числитель и знаменатель 1-й дроби: -135 36 Числитель и знаменатель 2-й дроби: 31 60 Результат: -97/30
a := 6*12 + 3 = 72 + 3 = 75;
b := a div 10 + 5 = 7 + 5 = 12;
a := b mod 10 + 1 = 2 + 1 = 3;
c := a*a + b*b – a / 2 * b = 9 + 144 - 18 = 135;