Простейшая задача сортировки – сортировка 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
Новые комментарии получены объединением новых знаний из внутреннего выражения 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 чтобы определить, что печатать первым.
При сборке программы мы оставляем только часть { что известно } разработочных комментариев. Программа достаточно простая и мы можем выполнить сборку за один шаг.
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-строк, мы смогли проанализировать данный путь решения задачи и сделать выводы насчет практической реализации.
