Рассмотрим новую стратегию сортировки трех символов при помощи меньшего количества операторов WRITE. Найдем минимальный символ среди Ch1, Ch2, Ch3, выведем его, позаботившись о том, чтобы оставшиеся символы находились в Ch1 и Ch2. Это уменьшит сложность первоначальной задачи, поскольку отсортировать нам надо всего 2 символа. Если минимум находится в переменной, отличной от Ch3, то значение переменной Ch3 должно быть помещено в переменную, значение которой мы выведем.
После предварительного анализа получается следующий проект:
Design Part 3
PROGRAM MinSort3 (INPUT,OUTPUT);
{сортирует 3-строку из INPUT в OUTPUT }
VAR
Ch1, Ch2, Ch3: CHAR;
BEGIN {MinSort3 }
READ(Ch1, Ch2, Ch3);
WRITELN('Входные данные ', Ch1, Ch2, Ch3);
WRITE('Сортированные данные ');
{Печатать минимум в OUTPUT, сохранить содержимое в Ch1 and Ch2 };
{ Сортировать Ch1, Ch2 в OUTPUT };
WRITELN
END.{Minsort3}
Design Part 3.1
BEGIN {Печатать минимум в OUTPUT, сохранить содержимое в Ch1 and Ch2 };
IF Ch1 < Ch2
THEN
{ Печатать минимум из Ch1, Ch3 в OUTPUT,
переместить Ch3 в Ch1,если необходимо}
IF Ch1 < Ch3
THEN
BEGIN
WRITE(Ch1);
Ch1:= Ch3
END
ELSE
|
|
WRITE(Ch3)
ELSE
{ Печатать минимум из Ch2, Ch3 в OUTPUT,
переместить Ch3 в Ch2,если необходимо}
IF Ch2 < Ch3
THEN
BEGIN
WRITE(Ch2);
Ch2:= Ch3
END
ELSE
WRITE(Ch3)
END
Раздел проекта 3.1 длиной 25 строк нарушает правило размера в 5-15 строк, но оно имеет очень простую структуру, а комментарии комментируют код во всех частях проекта.
Design part 3.2
BEGIN {Сортируем Ch1, Ch2 в OUTPUT }
IF Ch1 < Ch2
THEN
WRITE(Ch1, Ch2)
ELSE
WRITE(Ch2, Ch1)
END
После сборки разработочной программы Minsort3 будет иметь 6 операторов WRITE, как и IFSort3. На что же будет похода процедура MinSort4? Нам нужно только поменять раздел проекта 3, для того чтобы включить в него дополнительную переменную Ch3. Новый раздел проекта потребуется для нахождения минимального значения из Ch1, Ch2, Ch3, Ch4. Затем разделы проекта 3.1 и 3.1.1 могут быть повторно использованы для того, чтобы оставить оставшиеся символы в Ch1, Ch2 и Ch3. Т.е. Minsort4 просто записывает минимум и уменьшает сложности до уровня MinSort3.
Для того, чтобы найти минимум из 4-х переменных, потребуется оператор IF вложенностью как минимум 3 уровня в глубину, потому что минимальное значение должно предшествовать или быть равно трем другим переменным. Фактичести, 3 уровня вложенности достаточны, поскольку условия операторов IF могут быть организованы в таблице:
Сравнения для поиска минимума из четырех переменных | |
Условие | Минимум |
Ch1 < Ch2 | |
Ch1 < Ch3 | |
Ch1 < Ch4 | Ch1 |
Ch4 <= Ch1 | Ch4 |
Ch3 <= Ch1 | |
Ch3 < Ch4 | Ch3 |
Ch4 <= Ch3 | Ch4 |
Ch2 <= Ch1 | |
Ch2 < Ch3 | |
Ch2 < Ch4 | Ch2 |
Ch4 <= Ch2 | Ch4 |
Ch3 <= Ch2 | |
Ch3 < Ch4 | Ch4 |
Ch4 <= Ch3 | Ch4 |
Трехуровневой оператор IF потребует 8 операторов Write, поэтому количество операторов Write в программе MinSort4 будет 8 + 4 + 2 = 14, по сравнению с 4 * 3 * 2 * 1 = 24 для программы IFSort4.
|
|
Таблица ниже показывает количество операторов Write в двух семействах программ:
2 + 4 + 8 + 16 + … + 2^N-1 (MinSortN)
2 * 3 * 4 * 5 * … * N (IFSortN)
Количество операторов Write | ||
N | IFSortN | MinSortN |
5 040 | ||
40 320 | ||
362 880 | ||
3 628 800 | 1 022 |
Как видите, изменения проекта может привести к уменьшению размера программ. Однако даже программы MinSort растут довольно быстро.
Программы семейства MinSort были открыты с использованием другой стратегии проектирования:
Для решения одной задачи семейства, подумайте о способе решения меньших задач.
Подход IFSort трансформирует решения для меньших задач семейства в решения для более сложных задач, а программа MinSort – напротив, идет в противоположном направлении.
Анализируя эти простые стратегии сортировки, мы приходим к двум принципам проектирования программ:
- Тщательно поразмышляйте о проекте, который может привести к программе меньшего размера.
- Хорошая стратегия проектирования – это решение задачи путем уменьшения ее до более простого случая.
Булева логика.
Булева логика обеспечивает формальный и систематический метод рассуждения об условиях в операторах IF. Этот метод упрощает анализ поведения рограмм.
Новые положения: значения истинности, булевы значения, булевы оперторы NOT, AND, OR, булевы выражения, таблицы истинности, Булевые тождества.
Операторы IF и WHILE служат для условного выполнения в зависимости от результате <условия> во время выполнения.
IF Ch1 <> Ch2
THEN
WRITE(Ch1)
ELSE
WRITE(Ch2)
Такое условие имеет только два возможных результата – оно либо выполняется, либо нет. Условия, с двумя возможными результатами называются Булевыми условиями (Джордж Буль, 1815 – 1864, впервые систематически исследовал этот предмет). Результаты называются значениями истинности (truth values) или Булевыми значениями, с именами TRUE и FALSE. Это значения, принимаемые <условием> в операторах IF или WHILE, в то время как символьные переменные принимают символьные значения. Например, после следующих операторов присвоения:
Ch1:= ‘A’;
Ch2:= ‘С’
Булевы значения будут
<Условие> | Булево значение |
Ch1 < Ch2 | TRUE |
Ch1 >= Ch2 | FALSE |
Ch1 <= Ch2 | TRUE |
Ch1 = B | FALSE |
Ch2 = ‘C’ | TRUE |
‘X’ = ‘Y’ | FALSE |