Пример проектирования : сложение смешанных чисел
В примере приводится последовательность шагов проектирования алгоритма сложения двух смешанных чисел (целое, числитель, знаменатель).
.
1. Представление данных.
int a[3]; a[0] - целое, a[1] - числитель, a[2] - знаменатель.
Целое число: b[3] = {3,0,1}; - знаменатель не может быть 0.
2. Модуль
void sum(int c[], int a[], int b[])
{}
3. Шаг1 алгоритма: простая последовательность действий
{
1.1 Сложить целые
1.2 Общий знаменатель
1.3 Сложить числители
1.4 Если числитель > знаменателя - скорректировать
1.5 Сократить числитель и знаменатель
}
4. Шаг 1.1
c[0] = a[0] + b[0];
5. Шаг 1.2
Общий знаменатель - наименьшее общее кратное,
минимальное числа, которое делится на числитель и
знаменатель без остатка.
6. Шаг 1.2 Конкретизируем на словах:
Алгоритм - проверять все числа от 1 до бесконечности, пока
не найдется первое которое делится на a[2] и b [2].
Замечание: можно начинать от любого a[2],b[2].
7. Шаг 1.2. Следующая конструкция:
for (начиная с b[2] до бесконечности проверять число)
{ если делится на оба знаменателя - выйти }
7. Шаг 1.2 Записывает отдельные фразы:
int N; - искомое число.
for (N=b[2]; 1; N++) - проверять от b[1] до бесконечности
N % b[2] - число делится на знаменатель
if (делится) выход из цикла.
8. Шаг 1.2. Запись алгоритма.
int N;
for (N=b[2]; 1; N++)
if (N % b[2]==0 && N % a[2]==0) break;
9. Шаг 1.3. Формулировка:
Сложить числители, домножив каждый на частное от
деления общего знаменателя на знаменатель дроби.
10.Шаг 1.3. Запись алгоритма.
c[1] = b[1] * (N / b[2]) + a[1] * (N / a[2]);
11.Замечание - общий знаменатель нужно сохранить в результате.
c[2] = N;
12.Шаг 1.4. Формулировка:
Если числитель => знаменателя, к целому добавить 1, а из
числителя вычесть знаменатель.
13.Шаг 1.4. Запись алгоритма.
if (c[1] >=c[2]) { c[1]-=c[2]; c[0]++; }
14.Шаг 1.4. Замечания: не больше, а больше или равно.
если числитель стал 0, то знаменатель нужно сделать
равным 1:
if (c[1]==0) c[2]=1;
(это, чтобы не было лишних множителей в знаменателе).
15.Шаг 1.5. Обсуждение:
Надо найти наибольший общий делитель, который делит
числитель и знаменатель без остатка. Для этого можно
проверять все числа, начиная, например, со знаменателя,
с убыванием, пока не найдем делитель, либо пока не
дойдем до 1 (кстати она всегда будет общим делителем).
16.Шаг 1.5. Формулировка:
Проверять все числа от c[2] до 1 с убыванием, пока
одновременно не разделится на c[2] и c[1].
c[1], c[2] разделить на найденное число.
17.Шаг 1.5. Следующая конструкция - простая
последовательность:
1.5.1. Поиск N
1.5.2. Деление c[1],c[2] на N
18.Шаг 1.5.1. Запись алгоритма:
for (N=c[2]; 1; N--)
if (c[2] % N==0 && c[1] % N==0) break;
19.Шаг 1.5.2. Запись алгоритма:
c[2] /=N; c[1]/=N;