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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



Этот день в истории
В 1681 году скончался(-лась) Педро Кальдерон


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

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

     1.2.12. Коэффициенты многочлена хранятся в массиве a: array
[0..n]  of  integer (n - натуральное число, степень многочлена).
Вычислить значение этого многочлена в точке x (т. е.  a[n]*(x  в
степени n)+...+a[1]*x+a[0]).

     Решение. (Описываемый алгоритм называется схемой Горнера.)

  k := 0; y := a[n];
  {инвариант: 0 <= k <= n,
   y= a[n]*(x в степени k)+...+a[n-1]*(x в степени k-1)+...+
                     + a[n-k]*(x в степени 0)}
  while k<>n do begin
  | k := k + 1;
  | y := y * x + a [n - k];
  end;

     1.2.13. (Для знакомых с основами анализа. Сообщил  А.Г.Куш-
ниренко.)  Дополнить  алгоритм  вычисления значения многочлена в
заданной точке по схеме Горнера вычислением значения его  произ-
водной в той же точке.

     Решение. Добавление нового коэффициента соответствует пере-
ходу от многочлена P(x) к многочлену P(x)*x + c. Его производная
в  точке  x равна P'(x)*x + P(x). (Это решение обладает забавным
свойством: не надо знать заранее степень многочлена. Если требо-
вать выполнения этого условия, да еще просить  вычислять  только
значение производной, не упоминая о самом многочлене, получается
не такая уж простая задача.)

     1.2.14.  В  массивах
  a:array  [0..k] of integer и b: array [0..l] of integer
хранятся коэффициенты двух многочленов степеней k и  l.  Помес-
тить в массив c: array [0..m] of integer коэффициенты их произ-
ведения.  (Числа k, l, m - натуральные, m = k + l; элемент мас-
сива с индексом i содержит коэффициент при x в степени i.)

     Решение.

          for i:=0 to m do begin
          | c[i]:=0;
          end;
          for i:=0 to k do begin
          | for j:=0 to l do begin
          | | c[i+j] := c[i+j] + a[i]*b[j];
          | end;
          end;

     1.2.15. Предложенный выше алгоритм перемножения многочленов
требует порядка n*n действий для перемножения  двух  многочленов
степени n. Придумать более эффективный (для больших n) алгоритм,
которому  достаточно  порядка  (n  в  степени  (log  4)/(log 3))
действий.
     Указание. Представим себе, что надо перемножить два многоч-
лена степени 2k. Их можно представить в виде
        A(x)*x^k + B(x)    и    C(x)*x^k + D(x)
(здесь x^k обозначает x  в степени k). Произведение их равно
       A(x)C(x)*x^{2k}  +  (A(x)D(x)+B(x)C(x))*x^k  + B(x)D(x)
Естественный способ вычисления AC, AD+BC, BD требует четырех ум-
ножений многочленов степени k, однако их количество можно сокра-

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