Семейство программ 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 – напротив, идет в противоположном направлении.
Анализируя эти простые стратегии сортировки, мы приходим к двум принципам проектирования программ:
Булева логика.
Булева логика обеспечивает формальный и систематический метод рассуждения об условиях в операторах 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 := ‘С’
Булевы значения будут
Условия и утверждения В операторе IF могут быть даны следующие комментарии состояния:
IF Ch1 <> Ch2 THEN {Ch1 < Ch2} WRITE(Ch1) ELSE {Ch1 >= Ch2} WRITE(Ch2)
<Условие> Ch1 <> Ch2 в первой строке может принимать значение TRUE либо значение FALSE. Однако комментарий состояния в операторе THEN {Ch1 < Ch2} на следующей строке может быть утверждением того, что условие должно быть равно TRUE на входе в часть THEN оператора IF. Основа для этого утверждения в том, как выполняется оператор IF Паскаль-машиной. Т.е. не важно, что произошло раньше, не важно, какие значения переменных Ch1 и Ch2 могут быть на входе в часть THEN, значения условия Ch1 < Ch2 ДОЛЖНО быть равно TRUE.
Булевы операторы. Оператор NOT Ранее упомянутый оператор IF иллюстрирует о том как рассуждать о состоянии значений переменных в программе. Комментарии состояния в части THEN утверждают, что значение Ch1 < Ch2 – это TRUE. Комментарий ELSE отражает наше знание о том, что оператор >= является противоположным оператору <, а FALSE задается как противоположность TRUE. Поэтому, значение Ch2 >= Ch2 является иитинным (TRUE) в то время как значение Ch1 < Ch2 является ложью (FALSE) и наоборот. Булевый оператор NOT меняет значение остинности на противоположное:
NOT(TRUE) = FALSE NOT(FALSE) = TRUE
NOT – это унарный (применяющийся к одному операнду), префиксный (предшествующий операнду) оператор.
Поскольку NOT(NOT(FALSE)) = NOT(TRUE) = FALSE NOT(NOT(TRUE)) = NOT(FALSE) = TRUE И это единственные возможные варианты, то NOT(NOT(P)) = P для любого Булева значения P.
Оператор AND
Рассмотрим вложенный оператор IF с комментариями состояния:
IF Ch1 < Ch2 THEN { Ch1 < Ch2 } IF Ch2 < Ch3 THEN { Ch1 < Ch2 < Ch3 } WRITE(Ch1) ELSE { Ch1 < Ch2, Ch3 <= Ch2 } IF Ch1 < Ch3 THEN { Ch1 < Ch3 <= Ch2 } WRITE(Ch1_ ELSE { Ch3 <= Ch1 < Ch2 } WRITE(Ch3)
Комментарий состояния {Ch1 < Ch2 < Ch3} выражает два утверждения о том, что значение Ch1 преджествует Ch2 и значение Ch2 предшествует Ch3. Булевый оператор AND захватывает это интуитивное значение. AND – это бинарный (два операнда) инфиксный (расположенный между своими операндами) оператор, который принимает значение TRUE, если значения обоих Булевых операндов являются истинными (TRUE). Во всех остальных случаях он принимает значение FALSE.
TRUE AND TRUE = TRUE TRUE AND FALSE = FALSE FALSE AND TRUE = FALSE FALSE AND FALSE = FALSE
Операции сравнения могут обычно объединяться с оператором AND. Когда одинаковые операнды встречаются в объединенном условии, чаще получается более простое условие с тем же самым значением истинности. Например:
Более простое сравнение является эквивалентным, поскольку AND требует выполнения обоих объединенных сравнения, включая возможность их противоречия. Во втором случае, эквивалентность операндов не может быть произойти в Ch1<=Ch2, поскольку Ch1 < Ch2 это запрещает.
Оператор OR В предыдущем операторе IF есть 2 случая, когда оператор WRITE может быть достигнут. Значение Ch1 < Ch2 должно быть TRUE и одно либо оба значения Ch2 < Ch3, Ch1 < Ch3 должны быть TRUE. Булевый оператор OR – это бинарный инфиксный оператор:
TRUE OR TRUE = TRUE TRUE OR FALSE = TRUE FALSE OR TRUE = TRUE FALSE OR FALSE = FALSE
Вот несколько полезных комбинаций использования OR
Таблицы истинности для булевых операторов.
Булевы выражения. Булеы операторы и операнды могут быть объединены при помощи скобок в Булевы выражения. Любое такое выражение, внутренние операнды которого являются булевыми значениями могут быть преобразованы в одно значение истинности при помощи таблицы истинности. Например, используя T и F в качестве значений истинности.
T or ((NOT F) AND F) = T
Результат может быть получен за один шаг путем повторного нахождения внутреннего выражения, заключенного в скобки и замены его значением из таблицы истинности:
Булевы тождества.
Уравнение между двумя булевыми выражениями, которое не зависит от того, какие значения принимают соответствующие операнды, вроде NOT(NOT P) = P называется булевым тождеством.
15 полезных булевых тождеств показаны ниже:
Доказательства булевых тождеств могут быть организованы в таблицах, в которых перечислены все комбинации булевых значений операндов, и каждая часть тождества эквивалентна по базовым таблицам истинности, затем скомбинированы для того, чтобы найти значение левой и правой части. Если эти значения равны во всех случаях, то тождество считается доказанным.
Например:
1. TRUE AND P = P
9. P OR Q = Q OR P
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (305)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |