8
2) 4 3 2 6 7 9 8
3) 2 3 4 6 7 9 8
4) 2 3 4 6 7 8 9
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Сортировки. Двоичный поиск
Содержание
- 2. Быстрая сортировка (Ч. Хоар, 1962)
- 3. Пример: 1) 4 9 7 6 2
- 4. Сортировка слиянием (Дж. Фон Нейман, 1945)
- 5. Пример:2 4 7 6 2 3 8
- 6. Пирамидальная сортировка
- 7. Сортировка подсчётомИдея: использование конечной длины сортируемых чиселВремя работы – O(n)Сортировка устойчива
- 9. Двоичный поискДвоичный поиск — алгоритм поиска объекта
- 10. ЗадачаПусть нам дан упорядоченный массив, состоящий только
- 11. Принцип работыДвоичный поиск заключается в том, что
- 13. Задача
- 14.
- 15.
- 16. Некоторые полезные советы при работе с вещественными числами
- 17. Когда имеешь дело с вещественными числами в
- 18. Неправильный выбор:If ((double)a/b < (double)с/d)Правильный выбор:If (a
- 19. Пример 2:Нам нужен цикл до sqrt(n) включительно.Неправильный выбор: for(int i = 0; i
- 20. Пример 3:Сравнить расстояния между точками a,b и
- 21. Если всё-таки приходится работать с вещественными числами,
- 22. Пример 2:У нас есть прямоугольный треугольник, мы
- 23. Если у нас возможно равенство вещественных чисел,
- 24. При работе с бинпоиском, если нам нужно
- 25. Скачать презентацию
- 26. Похожие презентации
Быстрая сортировка (Ч. Хоар, 1962)
![Пример:2 4 7 6 2 3 8 - [0;6]2 4 7 6](/img/tmb/15/1448970/8a87a0f92b663c62a42ca77dbe28f697-720x.jpg "Сортировки. Двоичный поиск")
Слайд 5
Пример:
2 4 7 6 2 3 8 -
[0;6]
2 4 7 6 2 3 8 - [0;3]
2
4 7 6 2 3 8 - [0;1]2 4 7 6 2 3 8 - [2;3]
2 4 6 7 2 3 8 - [4;6]
2 4 6 7 2 3 8 - [4;5]
Итог: 2 2 3 4 6 7 8
Слайд 7
Сортировка подсчётом
Идея: использование конечной длины сортируемых чисел
Время работы
– O(n)
Сортировка устойчива
Слайд 9
Двоичный поиск
Двоичный поиск — алгоритм поиска объекта по
заданному признаку в множестве объектов, упорядоченных по тому же
самому признаку, работающий за логарифмическое время.
Слайд 10
Задача
Пусть нам дан упорядоченный массив, состоящий только из
целочисленных элементов. Требуется найти позицию, на которой находится заданный
элемент или сказать, что такого элемента нет.
Слайд 11
Принцип работы
Двоичный поиск заключается в том, что на
каждом шаге множество объектов делится на две части и
в работе остаётся та часть множества, где находится искомый объект.Слайд 17 Когда имеешь дело с вещественными числами в первую
очередь нужно подумать нельзя ли от них избавиться и
перейти к целым.Пример 1:
Нам нужно сравнить два числа вида a/b, где а и b целые числа
Слайд 18
Неправильный выбор:
If ((double)a/b < (double)с/d)
Правильный выбор:
If (a *
d < c * b)
Исключение:
Когда a * d или
c * b не помещаются в целочисленный тип
Слайд 19
Пример 2:
Нам нужен цикл до sqrt(n) включительно.
Неправильный выбор:
for(int i = 0; i
for(int i = 0; i * i <= n; i++)
Слайд 20
Пример 3:
Сравнить расстояния между точками a,b и c,d
int
d1 = sqr(a.x-b.x) + sqr(a.y-b.y);
int d2 = sqr(c.x-d.x) +
sqr(c.y-d.y);Вместо:
if (sqrt(d1) < sqrt(d2))
Лучше:
if (d1 < d2)
Слайд 21 Если всё-таки приходится работать с вещественными числами, то
всегда нужно стараться уменьшить погрешность вычислений
Пример 1:
b/a + c/a
+ … = (b + c + …)/a;
Слайд 22
Пример 2:
У нас есть прямоугольный треугольник, мы знаем
длины его сторон a,b,c и один из углов A.
Нужно найти sin(B)Не лучший выбор:
sinb = sin(pi - A);
Можно так:
sinb = b/c;
Слайд 23 Если у нас возможно равенство вещественных чисел, то
их всегда нужно сравнивать по eps
abs(a - b)
eps <=> a == bEps должен быть меньше требуемой точности, но больше лучшей точности.
Обычно выбирают eps = 1e-9;
А вообще вопрос точности при работе с вещественными типами это философский вопрос ☺
Слайд 24 При работе с бинпоиском, если нам нужно найти
число с какой-то точностью, то почти всегда лучше это
делать итерационноПример:
Нам нужно найти корень функции с заданной точностью
Не правильный выбор:
while((r – l) < eps)
Правильный выбор:
for (int i = 0; i < 100; i++)
