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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

     Взять элемент;
        {Длина > 0}
        элемент := Содержание [Первый];
        Первый := (Первый + 1) mod n;
        Длина := Длина - 1;

     Пуста = (Длина = 0);

     Очередной = Содержание [Первый];

     6.2.2.  (Сообщил А.Г.Кушниренко) Придумать способ моделиро-
вания очереди с помощью двух стеков (и фиксированного числа  пе-
ременных  типа T). При этом отработка n операций с очередью (на-
чатых, когда очередь была  пуста)  должна  требовать  порядка  n
действий.

     Решение.  Инвариант:  стеки, составленные концами, образуют
очередь. (Перечисляя элементы одного стека вглубь и  затем  эле-
менты  второго  наружу,  мы  перечисляем все элементы очереди от
первого до последнего.) Ясно, что добавление сводится к добавле-
нию к одному из стеков, а проверка пустоты - к проверке  пустоты
обоих стеков. Если мы хотим взять элемент, есть два случая. Если
стек,  где  находится  начало очереди, не пуст, то берем из него
элемент. Если он пуст, то предварительно переписываем в него все
элементы второго стека, меняя порядок (это происходит  само  при
перекладывании  из стека в стек) и сводим дело к первому случаю.
Хотя число действий при этом и не ограничено константой, но тре-
бование задачи выполнено, так как каждый элемент  очереди  может
участвовать в этом процессе не более одного раза.

     6.2.3. Деком называют структуру, сочетающую очередь и стек:
класть и забирать элементы можно с обоих концов. Как реализовать
дек ограниченного размера на базе массива так, чтобы каждая опе-
рация требовала ограниченного числа действий?

     6.2.4. (Сообщил А.Г.Кушниренко.) Имеется дек элементов типа
T  и конечное число переменных типа T и целого типа. В начальном
состоянии в деке некоторое число элементов. Составить программу,
после исполнения которой в деке остались бы те же самые  элемен-
ты, а их число было бы в одной из целых переменных.

     Указание.  (1) Элементы дека можно циклически переставлять,
забирая с одного конца и помещая в другой. После  этого,  сделав
столько  же  шагов  в обратном направлении, можно вернуть все на
место. (2) Как понять, прошли мы полный круг или не прошли? Если
бы был какой-то элемент, заведомо отсутствующий в деке, то можно
было бы его подсунуть и ждать  вторичного  появления.  Но  таких
элементов нет. Вместо этого можно для данного n выполнить цикли-
ческий  сдвиг  на  n дважды, подсунув разные элементы, и посмот-
реть, появятся ли разные элементы через n шагов.

     Применение очередей.

     6.2.5. Напечатать в  порядке  возрастания  первые  n  нату-
ральных  чисел, в разложение которых на простые множители входят
только числа 2, 3, 5.


       Решение. Введем три очереди x2, x3, x5, в  которых  будем
хранить элементы, которые в 2 (3, 5) раз больше напечатанных, но

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 Большая Одесская Библиотека.