Семейство программ IFSort

ЛОГИКА БУЛЯ И УСЛОВНОЕ ВЫПОЛНЕНИЕ

Как использовать логику Буля в построении условных выражений в СА Pascal. Задача сортировки символьных строк иллюстрирует систематический подход к построению условных выражений.

Новые идеи: сортировка строки символов, поиск минимального в строке символов, сравнение двух дизайнов программы.

Сортировка с условным выполнением.

Этот раздел демонстрирует как спроектировать и проанализировать семейство программ сортировки используя комментарии состояния для сохранения интеллектуального контроля над глубоко вложенными выражениями CF Pacsal. Анализ ведет к получению нового семейства улучшенных программ сортировки.

Новые идеи: комментарии состояния, проектирование семейства программ, улучшение проекта решения задачи.

Рассмотрим проблему сортировки строки символов из входного файла в выходной файл. Входные символы должны быть упорядочены в алфавитном порядке для вывода. Если в INPUT имеются дублирующиеся символы, они должны быть выведены в OUTPUT в том же порядке. Например:

Будут рассмотрены методы используемые для сортировки начиная с простых случае и заканчивая общим решением проблемы.

Есть спорное мнение, что удобно именовать строки таким образом, чтобы длина строки была частью имени. Мы будем строку длины 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:

1. Проектирование вложенных выражений путем последовательного раскрытия частей THEN и ELSE, накапливая занния до тех пор пока все варианты не станут нам точно известны.
2. Критически анализировать программу в процессе разработки.
3. Искать другие пути решения задачи, если анализ показывает что текущий способ решения не является практичным.

Основные принципы решения задач, рассмотренные на примере семейства IFSort

При решения задачи думайте о наборе задач увеличивающейся сложености и сосредотачивайтесь на одной из них. Далее разрабатывайте семейство решений начиная с простейшего варианта (1-строка, 2-строка, … n-строка)

Принцип начла решения с простейшего варианта – простейший способ размышления над решением с последующим обобщением до решения задачи в целом.

Если Вы начнете решать задачу IF-сортировки для 10-строк, то вам придется сначала потратить уйму времени чтобы понять, что проект невыполним. Решая задачу 2-строк и 3-строк, мы смогли проанализировать данный путь решения задачи и сделать выводы насчет практической реализации.

Date: 2016-11-17; view: 278; Нарушение авторских прав