Случайный афоризм
Графоман: человек, которого следовало бы научить читать, но не писать. Бауржан Тойшибеков
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

не стека лежит лишняя скобка. По  окончании  A  стек  становится
пустым  - если не считать этой скобки - а затем и совсем пустым.
Аналогично для (A).
     (2) Покажем, что если программа завершает работу с  ответом
"да",  то последовательность правильная. Рассуждаем индукцией по
длине последовательности. Проследим за состоянием стека  в  про-
цессе работы программы. Если он в некоторый промежуточный момент
пуст, то последовательность разбивается на две части, для каждой
из  которых  программа дает ответ "да"; остается воспользоваться
предположением индукции и определением правильности. Пусть  стек
все  время  непуст.  Это значит, что положенная в него на первом
шаге скобка будет вынута на последнем шаге. Тем самым, первый  и
последний символы последовательности - это парные скобки, и пос-
ледовательность имеет вид (A) или [A], а работа программы (кроме
первого  и  последнего  шагов) отличается от ее работы на A лишь
наличием лишней скобки на дне стека (раз ее не вынимают, она ни-
как не влияет на работу программы). Снова ссылаемся на предполо-
жение индукции и определение правильности.

     6.1.2. Как упростится программа, если известно, что в  пос-
ледовательности могут быть только круглые скобки?

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

     6.1.3. Реализовать с помощью одного массива два стека, сум-
марное количество элементов в которых ограничено длиной массива;
все  действия со стеками должны выполняться за время, ограничен-
ное константой, не зависящей от длины стеков.

     Решение. Стеки должны расти с концов массива навстречу друг
другу: первый должен занимать места
        Содержание[1] ... Содержание[Длина1],
а второй  -
        Содержание[n] ... Содержание[n - Длина2 + 1]
(вершины обоих стеков записаны последними).

     6.1.4. Реализовать k стеков с элементами типа T, общее  ко-
личество  элементов в которых не превосходит n, с использованием
массивов суммарной длины C*(n+k), затрачивая на каждое  действие
со  стеками (кроме начальных действий, делающих все стеки пусты-
ми) время, ограниченное некоторой константой.

     Решение. Применяемый метод называется "ссылочной реализаци-
ей". Он использует три массива:
        Содержание: array [1..n] of T;
        Следующий: array [1..n] of 0..n;
        Вершина: array [1..k] of 0..n.
     Массив Содержание будем изображать как n ячеек  с  номерами
1..n,  каждая  из которых содержит элемент типа T. Массив Следу-
ющий изобразим в виде стрелок, проведя стрелку из i  в  j,  если
Следующий[i] = j. (Если Следующий[i] = 0, стрелок из i не прово-
дим.) Содержимое s-го стека (s из 1..k)  хранится  так:  вершина
равна Содержание[Вершина[s]], остальные элементы s-го стека мож-
но  найти,  идя  по стрелкам - до тех пор, пока они не кончатся.
При этом (s-ый стек пуст) <=> Вершина[s] = 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 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.