ДСо18-13-Заключение (Лекции Северов Часть 3), страница 2

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

О полетах в космос в такиемоменты можно забыть: на всех трех астероидах разом случаетсяэкономический кризис. Ваша задача - определить, сколько ещетаких кризисов случится в будущем. Именно во время такихкризисов и приходится допускать к управлению биржами системытипа "SkyNet"65Замечание 1. Астероиды настолько малы, что их можно считатьточками.

Чтобы слишком не усложнять анализ, будем считать, чтоастероиды вполне могут оказываться одновременно в одной и тойже точке пространства. При этом они не сталкиваются, а пролетаютсквозь друг друга. Если угодно, можно думать, что на самом делеони просто проходят друг от друга на незначительном расстоянии.Замечание 2. Под "будущим" понимаются все моментывремени начиная с начала наблюдения. Само начало наблюдениятоже считаем частью "будущего".Вход. Входной файл содержит три строки, по одной на каждыйастероид. Каждая строка содержит 6 чисел X, Y, Z, Vx, Vy, Vz.Первые три числа задают координаты астероида в момент началанаблюдения, следующие три числа - координаты его вектораскорости. Все числа целые и не больше 20.Выход.

Одно целое число, равное количеству экономическихкризисов начиная с момента наблюдения. Если количество"кризисных моментов" бесконечно, выведите число -1.66(rC-rA)(rB-rA) + t*[(rC-rA)(vB-vA)+(vC-vA)(rB-rA)] + t2*(vC-vA)(vB-vA)=0X + t * Y + t2 * Z = 0Ri = ri + t* viAC = RC – RAAB = RB – RAAC ´ AB = 067Carnegie MellonОсновы анализаалгоритмов68Цена выполнения программыt = c1* d(n) + c2 * M + c3 * S,здесь ci(d(n)) – «веса» ресурсовT^ = maxdÎD T – наихудший случайTv = mindÎD T – наилучший случайŤ = Σ t / |T| – средний случай69Асимптотические оценки¢O (О большое)cg(n)f(n) и g(n): $c,n0:"n>n0c*g(n)≥f(n)>0 àf(n) = O( g(n) )f(n)Пример: F(x) = 4x2+ x = O(x2)70Сравнение времен выполненияалгоритмовn=10n=103n= 106Log2 n0,2 сек0,6 сек1,2 секn0,6 сек1 мин16,6 часn26 сек16,6 час1902 года2n1 мин10295 лет10300000 лет71Задача ИосифаПусть n человек, стоящие по кругу, считаются(начиная с первого) считалкой из m слов.Человек, на котором считалка заканчивается, выбывает, круг смыкается, а счет продолжается счеловека, следующего за выбывшим.Напишите программу, выводящую номера трехчеловек, выбывших последними, в порядке ихвыбывания.72Carnegie MellonРекурсия73РекурсияСпособ конечного описаниябесконечных объектов.¢ Мощный метод решениязадач рекуррентнойприроды.¢ Использование стека дляорганизации неявногохранения наборов данных.¢Накладные расходы,связанные с обращениемфункции к себе.¢ Экспоненциальный росттрудоемкости в случаеопределения одногозначения по несколькимдругим.¢ Сложность поискаошибок и верификациипрограмм.¢74n! = 1 · 2 · 3 · 4 · … · nОт простого к сложному От сложного к простомуn! = n·(n-1)! и 1! = 1x1= 1 и xn= n·xn-1int x = 1;for(int i=2; i<=n; i++) x *= i;Итерацииint f(n) = n>1?n*f(n-1):1;Рекурсия75Формальное представлениеПусть:P – рекурсивная процедура;Si – базовые операции, не содержащие P;P – композиция операторов;¢ Тогда:¢P = P[Si,P]¢Средство создания рекурсивной процедуры- описание функций, которые определяют впроцедуре имена, по которым процедурасама себя вызывает.76Классификация и данныеПрямо рекурсивнаяP = P[Si,P]Косвенно рекурсивнаяP = P[Si,Q]Q = Q[Si,P]Переменные, определённые внутрирекурсивной функции, создаются заново прикаждом вызове такой функции.Идентификаторы всегда ссылаются напеременные, созданные последними.77Важно !¢Проблема окончания работы.P = P[ Si, if !B then P]Наиболее надежный способ окончанияработы – связать с Р параметр n ирекурсивно вызывать Р с параметром n-1:P(n) = P[Si, if n>0 then P(n-1)]¢Глубина рекурсии.Следует убедиться, что она не толькоконечна, но и достаточно мала.78Примеры использования рекурсии при решении задачПОИСК ПУТИ В ЛАБИРИНТЕ79Сколько разбиений числа m на слагаемые ?65+14+24+1+13+33+2+12+2+22+2+1+11+1+1+1+1+13+1+1+12+1+1+1+1P(6) = 1180Сколько разбиений m на слагаемые £ nP(n) = Q(n,n)¢ Q(m,1) = 1¢ Q(1,n) = 1¢ Q(m,n) = Q(m,m)¢ Q(m,m) = 1 + Q(m,m-1)¢ Q(m,n) =Q(m-n,n) +¢Разбиения,содержащиеслагаемое, равное n1+1+…+1+1"n"n³mQ(m,n-1) " n < mРазбиения,не содержащиеслагаемое, равное n81ЧИСЛА ФИБОНАЧЧИИли о том, что рекурсию следуетиспользовать весьма осмотрительно…82ФУНКЦИЯ АККЕРМАНАИли о том, когда рекурсию не следуетиспользовать вообще…83Carnegie MellonДинамическоепрограммирование84Метод динамического«программирования»1.

Ричард Беллман 1953 год2. Пользуется свойствами задачи1.2.3.Оптимальная подструктураАддитивно перекрывающиеся подзадачиВозможность запоминания решений подзадач3. Эффективнее рекурсии и/или перебора4. Примеры задач1.2.3.4.5.Числа ФибоначчиО наибольшей подпоследовательностиО редакционном расстоянииО порядке перемножения матрицО ранце85Задача о хрустальном шаре.Ищем условия разбивания хрустального шара,сброшенного с высоты.Имеем m одинаковых хрустальных шаровЗа какое минимальное число попытокгарантированно найдём этаж N-этажного здания,начиная с которого этажа шары будут разбиваться ?86Задача о хрустальном шаре(подход на основе ДП)Пусть, для первой попытки оптимален этаж T.Количество попыток F(m,N) зависит от результатаПервый шар разбит:F(m-1, T-1) + 1Первый шар цел:F(m, N-T) + 1На этаже T:F(m,N) = max(F(m-1, T-1),F(m, N-T)) + 1В здании:F(m, N) = minT ( 1 + max(F(m-1, T-1),F(m, N-T)) );F(1,N)=N; F(m,0)=0; F(m,1)=1; F(m,2)=287Задача о минимальной сдачеИмеется неограниченное количество монетдостоинств V={v1,…,vK}.

"i: vi<vi+1Какое минимальное количество монет D(S)потребуется чтобы набрать заданную сумму S ?D(S) = mink( D(S – Vk) )88Задача о вариантах сдачиИмеется неограниченное количествомонет достоинств V={v1,…,vK}. "i: vi<vi+1Сколькими способами можно набратьзаданную сумму?89Код Хаффмана¢¢Более частые символы последовательности должны иметьболее короткий код, а более редкие – более длинныйЧтобы исключить проблема декодирования символов,кодированых двоичными кодами разной длины, естьпрефиксное кодирование:Код никакого символа не является началом кодадругого.¢Кодирование – бинарное дерево, где листья содержатсимволы, а набор ребер (левое – 0, правое – 1), входящих в путьот корня дерева к листу, порождает код символа.9091Carnegie MellonСортировки92Сортировки§ Введение§ Простые: O(n2)§ Сложные: O(n·log n)93Типы сортировкиВнутренняя§ все элементы находятся в памяти машины¢ Внешняя§ массив данных настолько велик, что в ОЗУ¢машины может храниться только лишь частьданных¢Устойчивая§ сохраняет порядок размещения элементов вмассиве, содержащем одинаковые ключи94Основные характеристикиВремя – характеристика вызывающаянаибольший интерес¢ Дополнительный объем оперативнойпамяти, используемый алгоритмом1.

Не требуется (In place);2. Для размещения указателей или индексов¢массивов;3. Для размещения еще одной копии массива.95Простые сортировки: О(n2)1.2.3.4.5.Сортировка вставкамиСортировка выборомСортировка пузырькомГномья сортировкаШейкерная сортировка96Сложные сортировкиСвойства§ В среднем O(n log n)§ Возможна деградация до О(n3/2) и даже О(n2)§ Не всегда «in line»¢Шелла¢Быстрая (Хоара)¢Слиянием¢Пирамидальная¢97Бинарное сортирующее дерево (куча)1. Ключ узла не меньше ключей справа и слева.2. Разница глубин листьев не более 13.

Последний слой заполняется слева направо без пустот89972544826198Структура данных кучи¢Индексы узлов в массиве12n2n42n+158123345961078611971210111299Действия с кучей¢Точечное исправление кучи: O(log n)§ По необходимости поменять узел с потомком иисправить нижеПостроение кучи: O(n)§ Исправление массива до кучи справа налево¢ Удаление максимального: O(log n)§ Поменять первый с последним, укоротить, исправить¢ Пирамидальная сортировка : O(n log n)§ Удалить все максимальные по очереди¢100Библиотечная функция qsortvoid qsort(void* a, size_t n, size_t s,int (*comp)(const void*, const void*))здесьa – имя сортируемого массиваn – количество элементов as – размерность одного элемента(*comp) – указатель на функцию сравнения> 0, если >= 0, если ==< 0, если <101Carnegie MellonПоиск102Линейный поиск O(N)template <typename T> class List {Item<T> *front,*back; T rab;Item<T>* find(Item<T>* &F, const T& k) {if(front==NULL) return (F=NULL);Item<T> *ptr=F=front;if(front->get_node()==k) return 0;while((F=ptr->get_next())!=NULL) {if(F->get_node()==k) break; ptr=F; }return ptr; }103Идеи ускорения с ценой¢Самоорганизующаяся таблица (кеш)§ обнаруженную запись – в «начало» таблицы и частоиспользуемые записи будут в «начале» таблицы§ нужно «начало» и переупорядочениеБинарный поиск§ посмотрим ключ в «середин廧 нужен произвольный доступ и упорядочение¢ Правильное дерево§ ищем за ≈m проверок среди ≈2m элементов§ нужна перестройка при записи и удалении¢104Поиск в дереве O(log N)¢Двоичное дерево поиска§ Tl < T < Tr,например: Tlll < Tll < Tl < T < rl < Trrl < Trr¢Вероятность найти среди n равновероятныхключей: 2*(ln n + g -1)0КонстантаЭйлера0,577…T1Tl2Tll3TlllTrTlrTrlTrrTrrl105Идеально сбалансированное деревоДвоичное дерево поиска + | nr – nl | £ 1¢ Вероятность найти среди n равновероятныхключей: log2 – 1, что лучше любого двоичногодерева поиска в 2ln2 ≈ 1,39…¢¢Выигрыш превышает затраты ?§ Если много узлов§ Если много поисков и мало вставок106А если не идеализировать?¢Дерево сбалансированное идеально| nr –nl | £ 1¢АВЛ-дерево, сбалансированное «неидеально», нопрактично по Адельсону-Вельскому и Ландису| hr –hl | £ 1log2 (n+1) < hb(n) < 1,4404* log2 (n+2) – 0.328¢Какое АВЛ-дерево самое «плохое» - минимум узловпри заданной высоте ?107108Эффективность ?¢Вопросы§ Какова средняя высота АВЛ-деревьев n! равновероятныхперестановок n ключей?§ Какова вероятность балансировки вставки?¢Ответы§ Математического исследования нет, а на практик姧¢h = log(n)+ 0.25Вероятность балансировки 0.5Вывод§ Трудно превзойти простейший алгоритм вставки в дерево§ Эффективность балансировки - условна109~O(1)ХЕШ-ТАБЛИЦЫ:ПОИСК НА ОСНОВЕ МАССИВА110H: KàANB: поиск по ключамf.e.: Поиск по фамилии, состоящей не болеечем из 10 букв.¢Множество возможных ключей ~3010¢Множество индексов массива ~103111Разрешение конфликтов1.