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

Рассмотрим новую стратегию сортировки трех символов при помощи меньшего количества операторов 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 могут быть организованы в таблице:

Трехуровневой оператор 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)

Как видите, изменения проекта может привести к уменьшению размера программ. Однако даже программы MinSort растут довольно быстро.

Программы семейства MinSort были открыты с использованием другой стратегии проектирования:

Для решения одной задачи семейства, подумайте о способе решения меньших задач.

Подход IFSort трансформирует решения для меньших задач семейства в решения для более сложных задач, а программа MinSort – напротив, идет в противоположном направлении.

Анализируя эти простые стратегии сортировки, мы приходим к двум принципам проектирования программ:

1. Тщательно поразмышляйте о проекте, который может привести к программе меньшего размера.
2. Хорошая стратегия проектирования – это решение задачи путем уменьшения ее до более простого случая.

Булева логика.

Булева логика обеспечивает формальный и систематический метод рассуждения об условиях в операторах 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:= ‘С’

Булевы значения будут