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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

     Решение. Для вычисления f(x) вычисляем последовательность
        l(x), l(l(x)), l(l(l(x))),...
до появления нуля и запоминаем ее, а затем вычисляем значения  f
в точках этой последовательности, идя справа налево.

     Еще более сложный случай из следующей задачи вряд ли встре-
тится  на  практике  (а  если  и встретися, то проще рекурсию не
устранять, а оставить). Но тем не менее: пусть функция f с нату-
ральными аргументами и значениями определяется соотношениями
        f(0) = a,
        f(x) = h(x, f(l(x)), f(r(x))),
где a - некоторое число, а l, r и h - известные функции. Предпо-
лагается, что если взять произвольное число и начать применять к
нему функции l и r в произвольном порядке, то  рано  или  поздно
получится 0.

     8.3.2. Написать нерекурсивную программу вычисления f.

     Решение. Можно было бы сначала построить дерево, у которого
в корне находится x, а в сыновьях вершины i стоят l(i) и r(i)  -
если только i не равно нулю, а затем вычислять значения функции,
идя от листьев к корню. Однако есть и другой способ.

     "Обратной польской записью" (или "постфиксной записью") вы-
ражения  называют  запись,  где знак функции стоит после всех ее
аргументов, а скобки не используются. Вот несколько примеров:

          f(2)                  2 f
          f(g(2))               2 g f
          s(2,t(7))             2 7 t s
          s(2, u(2, s(5,3))     2 2 5 3 s u s

Постфиксная  запись  выражения  позволяет удобно вычислять его с
помощью "стекового калькулятора". Этот калькулятор  имеет  стек,
который  мы  будем представлять себе расположенным горизонтально
(числа вынимаются и кладутся справа). При нажатии на  клавишу  с
числом  это число кладется в стек. При нажатии на функциональную
клавишу соответствующая функция применяется к  нескольким  аргу-
ментам у вершины стека. Например, если в стеке были числа
        2 3 4 5 6
и  нажата  функциональная клавиша s, соотвтетствующая функции от
двух аргументов, то в стеке окажутся числа
        2 3 4 s(5,6)

Перейдем теперь к нашей задаче. В процессе  вычисления  значения
функции  f мы будем работать со стеком чисел, а также с последо-
вательностью чисел и символов "f", "l", "r", "h", которую мы бу-
дем интерпретировать как последовательность  нажатий  кнопок  на
стековом калькуляторе.  Инвариант такой:

      если стек чисел представляет собой текущее состояние
      стекового калькулятора, то после нажатия всех клавиш
      последовательности в стеке останется единственное
      число, и оно будет искомым ответом.

Пусть нам требуется вычислить значение, к примеру, f(100). Тогда
вначале мы помещаем в стек число 100, а  последовательность  со-
держит  единственный  символ "f". (При этом инвариант соблюдает-
ся.) Далее с последовательностью и стеком выполняются такие пре-

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