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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

самопересекающуюся незамкнутую ломаную, проходящую через все эти
точки.  (Соседним  отрезкам  ломаной разрешается лежать на одной
прямой.) Число действий порядка n*log n.

     Решение. Упорядочим точки по  x-координате,  а  при  равных
x-координатах  - по y-координате. В таком порядке и можно прово-
дить ломаную.

     4.3.4. Та же задача, если ломаная должна быть замкнутой.

     Решение. Возьмем самую левую точку (т.е. точку с наименьшей
x-координатой) и проведем из нее лучи во  все  остальные  точки.
Теперь упорядочим эти лучи, а точки на одном луче поместим в по-
рядке увеличения расстояния от начала луча.

     4.3.5. Дано n точек на  плоскости.  Построить  их  выпуклую
оболочку  -  минимальную  выпуклую фигуру, их содержащую. (Форму
выпуклой оболочки примет резиновое колечко, если его натянуть на
гвозди, вбитые в точках.)  Число операций не более n*log n.

    Указание. Упорядочим точки - годится любой из порядков,  ис-
пользованных в двух предыдущих задачах. Затем, рассматривая точ-
ки по очереди, будем строить выпуклую оболочку уже рассмотренных
точек. (Для хранения выпуклой оболочки полезно использовать дек,
см. главу 6 о типах данных.)


     4.4. Нижние оценки для числа сравнений при сортировке.

     Пусть  имеется  n  различных по весу камней и весы, которые
позволяют за одно взвешивание определить, какой из двух  выбран-
ных  нами  камней тяжелее. (В программистских терминах: мы имеем
доступ к функции  тяжелее(i,j:1..n):boolean.)  Надо  упорядочить
камни  по  весу,  сделав  как  можно меньше взвешиваний (вызовов
функции "тяжелее").

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

    4.4.1. Доказать, что сложность любого алгоритма сортировки n
камней не меньше log (n!). (Логарифм берется по основанию 2,  n!
- произведение чисел 1..n.)

     Решение. Пусть имеется алгоритм сложности не более  d.  Для
каждого  из n! возможных расположений камней запротоколируем ре-
зультаты взвешиваний (обращений к функции "тяжелее");  их  можно
записать  в  виде  последовательности  из не более чем d нулей и
единиц. Для  единообразия  дополним  последовательность  нулями,
чтобы ее длина стала равной d. Тем самым у нас имеется n! после-
довательностей  из  d нулей и единиц. Все эти последовательности
разные - иначе наш алгоритм дал бы одинаковые ответы для  разных
порядков  (и один из ответов был бы неправильным). Получаем, что
2 в степени d не меньше n! - что и требовалось доказать.

     Другой способ объяснить то же самое  -  рассмотреть  дерево
вариантов,  возникающее в ходе выполнения алгоритма, и сослаться
на то, что дерево высоты d не может иметь более (2 в степени  d)
листьев.

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