Метод функциональной декомпозиции

При решении сложных задач, как и при создании коллективных проектов зачастую бывает полезно разбить их на отдельные подзадачи, которые можно решать независимо друг от друга. Это ускоряет процесс разработки ПО и облегчает процесс устранения ошибок.

Рассмотрим следующую задачу

Задача №169.  Выпуклый четырёхугольник

Каждая вершина выпуклого четырехугольника A1, A2, A3, A4 задаётся парой координат на плоскости. Вершины четырехугольника перечисляются в правильном порядке. Найдите его площадь.

Входные данные

4 строки, в каждой из которых записано по 2 действительных числа с точностью, не превышающей 6 знаков после запятой

Выходные данные

Одно число – ответ на задачу сточностью не меньше, чем 10^-6.

Решение

Разделим четырёхугольник на 2 треугольника, площадь каждого из которых посчитаем с помощью формулы Герона

#include <bits/stdc++.h>

using namespace std;

 

typedef pair<double,double> point;

 

int main () {

point A1, A2, A3, A4;

cin >> A1.first >> A1.second

       >> A2.first >> A2.second

       >> A3.first >> A3.second

       >> A4.first >> A4.second;

double a = sqrt((A1.first - A2.first) * (A1.first - A2.first)

         + (A1.second - A2.second) * (A1.second - A2.second));

double b = sqrt((A2.first - A3.first) * (A2.first - A3.first)

         + (A2.second - A3.second) * (A2.second - A3.second));

double c = sqrt((A1.first - A3.first) * (A1.first - A3.first)

         + (A1.second - A3.second) * (A1.second - A3.second));

double d = sqrt((A3.first - A4.first) * (A3.first - A4.first)

         + (A3.second - A4.second) * (A3.second - A4.second));

double e = sqrt((A1.first - A4.first) * (A1.first - A4.first)

         + (A1.second - A4.second) * (A1.second - A4.second));

double p1 = (a + b + c) / 2, p2 = (e + c + d) /2,

       s1 = sqrt(p1 * (p1 - a) * (p1 - b) * (p1 - c)),

       s2 = sqrt(p2 * (p1 - e) * (p1 - c) * (p1 - d));

   

cout << s1 + s2;

}

Такое решение выглядит достаточно громоздким и, кроме того, легко ошибиться в индексах и переменных. Перестроим это решение с помощью пары вспомогательных функций len и sqrt для вычисления длины отрезка и площади треугольника соответственно:

#include <bits/stdc++.h>

#define SQR(x) (x)*(x)

using namespace std;

 

typedef pair<double,double> point;

 

// вычисление длины отрезка

double len(point A, point B){

return sqrt(SQR(A.first - B.first) + SQR(A.second - B.second));

}

 

// вычисление пощади треугольника

double square(point A, point B, point C){

double a = len(A, B), b = len(B, C), c = len(A, C),

       p = (a + b + c) / 2;

return sqrt(p * (p - a) * (p - b) * (p - c));

}

 

int main () {

point A1, A2, A3, A4;

cin >> A1.first >> A1.second

       >> A2.first >> A2.second

       >> A3.first >> A3.second

       >> A4.first >> A4.second;

cout << square(A1, A2, A3) + square(A1, A3, A4);

}

Это решение выглядит гораздо более компактным и читабельным. Если нам потребуется его перестроить для достижения большей точности вычислений, это сделать теперь гораздо проще. В самом деле, точность вычислений ухудшается из-за использования sqrt при нахождении полупериметра и площади треугольника. Воспользуемся формулой косого произведения векторов из раздела «Вычислительная геометрия» второй части этой книги. При этом вычислять длины каких-либо отрезков не требуется.

#include <bits/stdc++.h>

#define SQR(x) (x)*(x)

using namespace std;

 

typedef pair<double,double> point;

 

double square(point A, point B, point C){

return abs((B.first - A.first) * (C.second - A.second)

       -(C.first - A.first) * (B.second - A.second)) / 2;

}

 

int main () {

point A1, A2, A3, A4;

cin >> A1.first >> A1.second

       >> A2.first >> A2.second

       >> A3.first >> A3.second

       >> A4.first >> A4.second;

cout << square(A1, A2, A3) + square(A1, A3, A4);

}

Потребовалось внести изменения лишь в одной из подпрограмм. Содержимое основной программы в функции main() не изменилось.

Задача №170.  Красивые номера (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333.

Введем следующую оценку красоты разбиения номера. Будем разбивать номер дефисами на группы размером от 2 до 4 цифр. Теперь красотой разбиения назовем сумму баллов, которые приносит каждая группа. Эти баллы будем считать, пользуясь приведенной таблицей.

В этой таблице символами «а», «b», «с» обозначены различные цифры. Например, под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888». Пользуясь предложенной оценкой, найдите наиболее красивое разбиение заданного номера.

Шаблон группы	Баллы
aa	2
aba	2
aab, abb	2
aaa	3
abac, baca	2
abab	3
aabb	3
abba	4
baaa, abaa, aaba, aaab	3
aaaa	5

Входные данные

Одна строку из 7 цифр – заданный телефонный номер.

Выходные данные

Выведите в первой строке наиболее красивое разбиение номера, а во второй – величину его красоты. Если разбиений с максимальной величиной красоты несколько, выведите в выходной файл любое из этих разбиений.

Примеры

№	Ввод	Вывод
1	8727333	8727-333 5
2	8827291	88-272-91 4

Решение

Легко увидеть, что для семизначного номера существует всего 5 вариантов красивых номеров: "XXXX-XXX", "XXX-XXXX", "XX-XX-XXX", "XXX-XX-XX", "XX-XXX-XX". Опишем всё решение с помощью нескольких функций:

#include <iostream>

#define F a[t[i] - 'a']

using namespace std;

 

string a[] = {"aa", "aba", "aab", "abb", "aaa",

           "abac", "baca", "abab", "aabb", "abba",

           "baaa", "abaa", "aaba", "aaab", "aaaa"},

   v[] = {"XXXX-XXX", "XXX-XXXX", "XX-XX-XXX",

          "XXX-XX-XX", "XX-XXX-XX"};

 

int b[] = {2, 2, 2, 2, 3, 2, 2, 3, 3, 4, 3, 3, 3, 3, 5};

 

// проверка соответствия строки s шаблону t

bool mask(string s, string t){

int l = s.length();

if(l != t.length()) return 0;

int a[3] = {0,};

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

   if(F && F != s[i]) return 0;

   F = s[i];

}

return 1;

}

 

// вычисление наибольшей «красоты» для s по всем шаблонам

int check(string s){

int r = 0;

for(int i = 0; i < 15; i++)

   r = max(r, mask(s, a[i]) * b[i]);

return r;

}

 

// представление в варианте номер i «красивого» номера для s

string variant(string s, int i){

string tmp = "";

for(int p = 0, q = 0; v[i][p]; p++){

   tmp.push_back(v[i][p] == '-' ? '-' : s[q++]);

}  

return tmp;

}

 

// определение суммарной «красоты» конкретного номера

int sum(string s){

int k, res = 0;

string tmp = "";

for(int i = 0; s[i]; i++)

   if(s[i]=='-') {res += check(tmp); tmp = "";}

   else tmp.push_back(s[i]);

res += check(tmp);

return res;

}

 

int main () {

string num, ts, best;

cin >> num;

int p, q = 0, i;

best = variant(num, 0);

for(i = 0; i < 5; i++){

   ts = variant(num, i);

   p = sum(ts);

   if (p > q) { q = p; best = ts;}

}

cout << best << endl << q;

}