Семейство программ IFSort
ЛОГИКА БУЛЯ И УСЛОВНОЕ ВЫПОЛНЕНИЕ
Как использовать логику Буля в построении условных выражений в СА Pascal. Задача сортировки символьных строк иллюстрирует систематический подход к построению условных выражений.
Новые идеи: сортировка строки символов, поиск минимального в строке символов, сравнение двух дизайнов программы.
Сортировка с условным выполнением.
Этот раздел демонстрирует как спроектировать и проанализировать семейство программ сортировки используя комментарии состояния для сохранения интеллектуального контроля над глубоко вложенными выражениями CF Pacsal. Анализ ведет к получению нового семейства улучшенных программ сортировки.
Новые идеи: комментарии состояния, проектирование семейства программ, улучшение проекта решения задачи.
Рассмотрим проблему сортировки строки символов из входного файла в выходной файл. Входные символы должны быть упорядочены в алфавитном порядке для вывода. Если в INPUT имеются дублирующиеся символы, они должны быть выведены в OUTPUT в том же порядке. Например:
| Входная строка | Сортированная выходная строка |
| abc | abc |
| cab | abc |
| character | aaccehrrt |
Будут рассмотрены методы используемые для сортировки начиная с простых случае и заканчивая общим решением проблемы.
Есть спорное мнение, что удобно именовать строки таким образом, чтобы длина строки была частью имени. Мы будем строку длины n называть “n-строкой”. Например, “cab” – 3-строка. Если в примерах будут присутствовать знаки пробела, то мы будем их явно указывать с помощью символа □.
Семейство программ IFSort
Простейшая задача сортировки – сортировка 1-строки. Но тут нет задачи, поскольку 1-строка всегда отсортирована.
Для 2-строк стратегия решения очевидна: прочитать 2 символа, сравнить, вывести в надлежащем порядке. Таким образом, 2-строки могут быть отсортированы с помощью одного выражения IF.
DP1 [Design Part 1]
PROGRAM IFSort2(INPUT, OUTPUT);
{Сортирует 2-строку из INPUT в OUTPUT}
VAR
Ch1, Ch2: CHAR;
BEGIN
READ(Ch1, Ch2);
WRITELN(‘INPUT DATA ’, Ch1, Ch2);
WRITE(‘SORTED DATA’);
IF (Ch1 < Ch2)
THEN {Сортировать Ch1, Ch2 в OUTPUT, зная что Ch1 < Ch2}
WRITELN(Ch1, Ch2);
ELSE{Сортировать Ch1, Ch2 в OUTPUT, зная что Ch1 >= Ch2}
WRITELN(Ch2, Ch1);
END. {IFSort2}
Выполнение:
INPUT: ca
OUTPUT: INPUT DATA ca
SORTED DATA ac
INPUT: 37
OUTPUT: INPUT DATA 37
SORTED DATA 37
Поскольку Design Part 1 полностью реализована в CF Pascal она также может быть названа Development Program 1A. Вторая строка OUTPUT завершается одним из двух выражений WRITE, выбираемых выражением IF. Комментарии в частях IF и ELSE описывают более простые задачи исходя из известных соотношений значений переменных Ch1 и Ch2.
Подобная стратегия может быть применена к 3-строке используя выражения IF и переменные Ch1, Ch2 и Ch3. В процессе разработки будет проиллюстрировано применение комментариев для интеллектуального контроля за процессом разработки. В этот раз задача не сможет так легко быть выполнена за один шаг, поэтому проектирование начнется как запись основных задач в виде комментариев для дальнейшей реализации. Только чтение и эхо будут выглядеть примерно следующим образом:
PROGRAM IFSort3(INPUT, OUTPUT);
{Сортирует 3-строку из INPUT в OUTPUT}
VAR
Ch1, Ch2, Ch3: CHAR;
BEGIN
READ(Ch1, Ch2, Ch3);
WRITELN(‘INPUT DATA ’, Ch1, Ch2, Ch3);
WRITE(‘SORTED DATA’);
{Сортировать Ch1, Ch2, Ch3 в OUTPUT}
END. {IFSort3}
Для того, чтобы решить задачу сортировки в следующем приближении, сначала необходимо сравнить Ch1 и Ch2. Это единственный выход и он копирует логику IFSort2. Знание результатов сравнения Ch1 и Ch2 делает оставшуюся часть задачи проще.
DP 2.1
BEGIN
IF (Ch1 < Ch2)
THEN
{ Ch1 < Ch2: сортировать Ch1, Ch2, Ch3 в OUTPUT}
ELSE
{ Ch1 >= Ch2: сортировать Ch1, Ch2, Ch3 в OUTPUT}
END
Комментарии описывающие оставшиеся задачи дают дополнительную информацию следующую за двоеточием: задачу, которую нужно выполнить. В части THEN ничего не известно о Ch3, следовательно следующее выражение IF должно прояснить эту ситуацию, например, сравнивая с Ch2
DP 2.1.1
{Ch1 < Ch2: сортировать Ch1, Ch2, Ch3 в OUTPUT}
IF (Ch2 < Ch3)
THEN {Ch1 < Ch2 < Ch3}
WRITELN(Ch1, Ch2, Ch3)
ELSE
{ Ch1 < Ch2, Ch2 >= Ch3: сортировать Ch1, Ch2, Ch3 в OUTPUT}
Новые комментарии получены объединением новых знаний из внутреннего выражения IF со знанием из комментария, который начинает DP 2.1.1. Вход в этот раздел программы означает, что Ch1 < Ch2. Новый IF задает нам вариант когда Ch2 < Ch3, таким образом комментарий в части THEN фиксирует наше знание о том, что Ch1 < Ch2 < Ch3, чего достаточно, чтобы завершить эту задачу выводя переменные в соответствующем порядке.
Аналогично разрабатываются части ELSE DP2.1.1 и DP2.1 Задача решается частным образо без утраты контроля над проектированием программы. Все что нам известно о ходе решения задачи фиксируется в комментариях. В части ELSE DP 2.1.1. Ch2 печатается последним, нам нужно сравнить Ch1 и Ch3 чтобы определить, что печатать первым.
DP 2.1.1.1
{ Ch1 < Ch2, Ch2 >= Ch3: сортировать Ch1, Ch2, Ch3 в OUTPUT}
IF (Ch1 < Ch3)
THEN {Ch1 < Ch3 <= Ch2: сортировать Ch1, Ch2, Ch3 в OUTPUT}
WRITELN(Ch1, Ch3, Ch2)
ELSE {Ch3 <= Ch1 <= Ch2: сортировать Ch1, Ch2, Ch3 в OUTPUT}
WRITELN(Ch3, Ch1, Ch2)
На этом шаге разработки мы систематизировали информацию для того, что написать выражения WRITE для остальных случаев. Аналогично ELSE для DP 2.1.:
DP 2.1.2
{Ch1 >= Ch2: сортировать Ch1, Ch2, Ch3 в OUTPUT}
IF (Ch1 < Ch3)
THEN {Ch2 <= Ch1 < Ch3: сортировать Ch1, Ch2, Ch3 в OUTPUT}
WRITELN(Ch2, Ch1, Ch3)
ELSE
{Ch2 <= Ch1, Ch3 <= Ch1: сортировать Ch1, Ch2, Ch3 в OUTPUT}
DP 2.1.2.1
{Ch2 <= Ch1, Ch3 <= Ch1: сортировать Ch1, Ch2, Ch3 в OUTPUT}
IF (Ch2 < Ch3)
THEN {Ch2 < Ch3 <= Ch1: сортировать Ch1, Ch2, Ch3 в OUTPUT}
WRITELN(Ch2, Ch3, Ch1)
ELSE {Ch3 <= Ch2 <= Ch1: сортировать Ch1, Ch2, Ch3 в OUTPUT}
WRITELN(Ch3, Ch2, Ch1)
В любом случае комментарии имеют форму
{ что известно : что нужно сделать }
При сборке программы мы оставляем только часть { что известно } разработочных комментариев. Программа достаточно простая и мы можем выполнить сборку за один шаг.
Development Program 2A
PROGRAM IFSort3(INPUT, OUTPUT);
{Сортирует 3-строку из INPUT в OUTPUT}
VAR
Ch1, Ch2, Ch3: CHAR;
BEGIN
READ(Ch1, Ch2, Ch3);
WRITELN('INPUT DATA ', Ch1, Ch2, Ch3);
WRITE('SORTED DATA');
BEGIN {Сортировать Ch1, Ch2, Ch3 в OUTPUT}
IF (Ch1 < Ch2)
THEN { Ch1 < Ch2 }
IF (Ch2 < Ch3)
THEN {Ch1 < Ch2 < Ch3}
WRITELN(Ch1, Ch2, Ch3)
ELSE { Ch1 < Ch2, Ch2 >= Ch3 }
IF (Ch1 < Ch3)
THEN {Ch1 < Ch3 <= Ch2}
WRITELN(Ch1, Ch3, Ch2)
ELSE {Ch3 <= Ch1 <= Ch2}
WRITELN(Ch3, Ch1, Ch2)
ELSE { Ch1 >= Ch2 }
IF (Ch1 < Ch3)
THEN {Ch2 <= Ch1 < Ch3}
WRITELN(Ch2, Ch1, Ch3)
ELSE {Ch2 <= Ch1, Ch3 <= Ch1}
IF (Ch2 < Ch3)
THEN {Ch2 < Ch3 <= Ch1}
WRITELN(Ch2, Ch3, Ch1)
ELSE {Ch3 <= Ch2 <= Ch1}
WRITELN(Ch3, Ch2, Ch1)
END
END. {IFSort3}
Выполнение:
INPUT: cabaret
OUTPUT: INPUT DATA cab
SORTED DATA abc
Хотя 3-строка всего лишь наполовину длинне 2-строки, IFSort3 (32 строки) существенно длиннее IFSort2 (14строк). Вот почему. В IFSort3 6 выражений WRITE (количество возможных сочетаний Ch1, Ch2, Ch3 3*2*1). В IFSort2 необходимо только 2 выражения WRITE (2*1) чтобы вывести возможные сочетания Ch1 и Ch2, их обслуживает один оператор IF. Корневое выражение IF в IFSort3 является расширением выражения IF IFSort2 таким образом, что каждый оператор WRITE из IFSort2 заменился выражениями IF с тремя операторами WRITE.
Аналогично если вы будете писать программу IFSort4, Каждое из 6 выражений WRITE будет заменено составными IF с 4 выражениями WRITE. Таким образом, IFSort4 будет содержать 4*3*2*1 = 24 выражения WRITE. IFSort5 будет содержать 5*4*3*2*1=120 выражений WRITE и т.д. Для 10-строки нам потребуется 10*9*8*7*6*5*4*3*2*1 = 3 628 800 выражений WRITE.
Очевидно, что проблема сортировки требует переосмысления.
Три основных урока из разработки семейства программ IFSort:
- Проектирование вложенных выражений путем последовательного раскрытия частей THEN и ELSE, накапливая занния до тех пор пока все варианты не станут нам точно известны.
- Критически анализировать программу в процессе разработки.
- Искать другие пути решения задачи, если анализ показывает что текущий способ решения не является практичным.
Основные принципы решения задач, рассмотренные на примере семейства IFSort
При решения задачи думайте о наборе задач увеличивающейся сложености и сосредотачивайтесь на одной из них. Далее разрабатывайте семейство решений начиная с простейшего варианта (1-строка, 2-строка, … n-строка)
Принцип начла решения с простейшего варианта – простейший способ размышления над решением с последующим обобщением до решения задачи в целом.
Если Вы начнете решать задачу IF-сортировки для 10-строк, то вам придется сначала потратить уйму времени чтобы понять, что проект невыполним. Решая задачу 2-строк и 3-строк, мы смогли проанализировать данный путь решения задачи и сделать выводы насчет практической реализации.