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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

  | end else begin {x[m] > a}
  | | r := m;
  | end;
  end;
(Обратите внимание, что и в случае x[m] = a инвариант не наруша-
ется.)
     Каждый раз r-l уменьшается примерно вдвое, откуда и вытека-
ет требуемая оценка числа действий.
     Замечание.
l + (r-l) div 2 = (2l + (r-l)) div 2 = (r+l) div 2.

     1.2.27. (Из книги Д.Гриса) Дан массив x:  array  [1..n]  of
array  [1..m]  of  integer,  упорядоченный  по  "строкам"  и  по
"столбцам":
         x[i][j] <= x[i+1][j],
         x[i][j] <= x[i][j+1]
и число a. Требуется выяснить, встречается ли a среди x[i][j].

     Решение. Представляя себе  массив  a  как  матрицу  (прямо-
угольник,  заполненный числами), мы выберем прямоугольник, в ко-
тором только и может содержаться a, и будем его  сужать.  Прямо-
угольник этот будет содержать x[i][j] при 1<=i<=l и k<=j<=m.
                1                     k         m
               -----------------------------------
              1|                     |***********|
               |                     |***********|
               |                     |***********|
              l|                     |***********|
               |---------------------------------|
               |                                 |
              n|                                 |
               -----------------------------------
(допускаются пустые прямоугольники при l = 0 и k = m+1).

  l:=n; k:=1;
  {l>=0, k<=m+1, если a есть, то в описанном прямоугольнике}
  while (l > 0) and (k < m+1) and (x[l][k] <> a) do begin
  | if x[l][k] < a then begin
  | | k := k + 1; {левый столбец не содержит a, удаляем его}
  | end else begin {x[l][k] > a}
  | | l := l - 1; {нижняя строка не содержит a, удаляем ее}
  | end;
  end;
  {x[l][k] = a или прямоугольник пуст }
  answer:= (l > 0) and (k < m+1) ;

     Замечание.  Здесь та же ошибка: x[l][k] может оказаться не-
определенным. (Её исправление предоставляется читателю.)

     1.2.28. (Московская олимпиада по программированию) Дан не-
убывающий массив положительных целых чисел a[1] <= a[2]  <=...<=
a[n].  Найти наименьшее целое положительное число, не представи-
мое в виде суммы нескольких элементов этого массива (каждый эле-
мент массива может быть использован не более одного раза). Число
действий порядка n.

     Решение. Пусть известно, что  числа,  представимые  в  виде
суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некото-
рого N. Если a[k+1] > N+1, то N+1 и будет минимальным числом, не
представимым  в виде суммы элементов массива a[1]..a[n]. Если же

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