Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [ 114 ] [115] [116] [117]

If KJ then set +1

else set J J+l fi, set 1.

В первом операторе /С полагается равным 1, если только / не меньше J; во втором операторе /С полагается равным 1 независимо от значения / или J.

Операторы цикла. Операторы цикла появляются в разных формах; например,

1. Шаг L I ] Do шаг i+1 while IM od.

Шаг [ ] If COST(/, ./XMIN

then set MIN COST (/, J); and /ч-/+1 fl.

2. Шаг i. [ ] Do through шаг i+3 while />0 od.

Шаг t+1. [ ] Операторы. Шаг i+2. [ ] Операторы. Шаг i+3. [ ] Операторы. Шаг i+4. [ 3 Операторы.

Порядок выполнения цикла 2 следующий: выполняются шаги 1+1, 1+2 и i+3, затем проводится проверка, положительно ли J: />0; если /0, то следующим выполняется шаг i+4; если />0, то выполняются опять шаги i+1, i+2 и i+3 и J еще раз сравнивается с нулем и т. д. Предполагается, что где-то в пределах шагов i+1, i+2 или i+3 значение J меняется; в противном случае существует возможность бесконечного цикла.

3. Шаг 1. [ ] While PTR>0 do PTR ч-LEFT (PTR) od.

4. Шаг i. [ 3 While />0 do through шаг i+2 od.

Шаг i+1. [ ] Операторы. Шаг i+2. [ ] Операторы. Шаг i+3. [ ] Операторы.

Выполнение цикла. while-do отличается от выполнения цикла do-while только- тем, что в одной форме проверка осуществляется перед первым выполнением шага (шагов), предписанного оператором do, а не после. Использование od, как в форме 3, служит для определения конца действия do; его применение идентично применению fi.

5. Шаг i. [ 3 For 1 to do шаг i+1 od.

Цель формы 5 - допустить выполнение типичного DO- или FOR-цикла с приращением, равным 1, вместо того, чтобы инициализировать индексную переменную / и увеличивать ее внутри цикла do-while или while-do.



Операторы goto. Хотя принципы структурного программирования исключают потребность в операторах goto, иногда встречаются ситуации, когда goto кажется подходящим и естественным средством. В таких случаях алгоритмы бывают обычно очень короткими, и применение операторов goto не мешает пониманию логики алгоритма. Поэтому мы умеренно используем операторы goto.



Приложение Б. Множества и некоторью основные алгоритмы на множествах

Множества являются наиболее общей из всех математических структур и появляются почти в каждой математической модели. Часто задачи моделируются в терминах множеств, а алгоритмы решения формулируются в терминах основных операций на этих множествах. Реализация любого алгоритма может включать различные способы представления множеств и их обработки.

Это приложение не является «введением в теорию множеств». Скорее оно предполагает знание основ теориимножеств и операций над ними. В какой-то мере мы хотели установить обозначения, используемые в книге, но основная цель приложения - ознакомить читателя с некоторыми вопросами, возникающими при использовании множеств для реализации алгоритмов.

Б.1. Обозначения

1. Множества обозначаются латинскими заглавными буквами, а элементы множеств изображаются строчными буквами; например, f/={r, S, t, и, V, w).

2. vU V - элемент множества U.

vU V - не является элементом множества U.

VU V-тздмножество U, т. е. каждый элемент V является также элементом U.

VczU V - собственное подмножество U, т. е. существует элемент и, который не является элементом V.

3. V=0 V- пустое множество, т. е. в У нет элементов.

4. IFI Кардинальность V, т. е. для конечных множеств

число элементов в V. Ъ. и\}V Объединение множеств U и V, г. е. множество,

состоящее из всех элементов U и всех элементов V.

иr\V Пересечение множеств U и V, г. е. множество, со-

стоящее из. всех элементов- являющихся одновременно элементами и U, и V.

V-и Разность V и U, т. е. множество, состоящее из тех

элементов V, которые не являются элементами U.

VU, V " Если V - подмножество U, тогда V обозначает

дополнение V в U, т. е. V=U-V. 6. Если V={vu V2, . . ., Vji} - Конечное множество действительных



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [ 114 ] [115] [116] [117]

0.0016