Работа с файлами (C++). Лекция 6 по основам программирования

Содержание

Слайд 2

РАБОТА С ФАЙЛАМИ #include для чтения данных из файла используются объекты

РАБОТА С ФАЙЛАМИ

     #include 
для чтения данных из файла используются объекты типа

ifstream (input file stream)
для записи данных в файл используются объекты типа ofstream (output file stream).
     ifstream in;  // Поток in для чтения
     ofstream out; // Поток out для записи
Слайд 3

РАБОТА С ФАЙЛАМИ Чтобы привязать тот или иной поток к файлу

РАБОТА С ФАЙЛАМИ

Чтобы привязать тот или иной поток к файлу (открыть

файл для чтения или для записи) используется метод open, которому необходимо передать параметр – текстовую строку, содержащую имя открываемого файла.
     in.open("input.txt");
     out.open("output.txt");
Слайд 4

РАБОТА С ФАЙЛАМИ После открытия файлов и привязки их к файловым

РАБОТА С ФАЙЛАМИ

После открытия файлов и привязки их к файловым потокам,

работать с файлами можно так же, как со стандартными потоками ввода-вывода cin и cout.
     out<     in>>x;
Слайд 5

РАБОТА С ФАЙЛАМИ Для закрытия ранее открытого файла используется метод close()

РАБОТА С ФАЙЛАМИ

Для закрытия ранее открытого файла используется метод close() без

аргументов:
     in.close();
     out.close();
Закрытый файловый поток можно переоткрыть заново при помощи метода open, привязав его к тому же или другому файлу.
Слайд 6

РАБОТА С ФАЙЛАМИ Также можно использовать в качестве условия результат, возвращаемой

РАБОТА С ФАЙЛАМИ

Также можно использовать в качестве условия результат, возвращаемой операцией

считывания. Если считывание было удачным, то результат считается истиной, а если неудачным  – ложью.
Считывание последовательности целых чисел:
     int d;      while(in>>d)      {      }
Слайд 7

ЛИНЕЙНЫЙ ПОИСК Если данные не упорядочены, то найти искомый элемент можно

ЛИНЕЙНЫЙ ПОИСК

Если данные не упорядочены, то найти искомый элемент можно только

путем последовательного перебора всех элементов.
for (i=0; i if (A[i]==B) break;
if (i != n) ...найден...
Поиск значения путем последовательного перебора всех элементов называется линейным поиском.
Сложность алгоритма - O(N).
Слайд 8

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК Если данные упорядочены, то найти искомый элемент можно

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

Если данные упорядочены, то найти искомый элемент можно значительно

быстрее.
Алгоритм двоичного или бинарного поиска основан на делении пополам текущего интервала поиска. В основе его лежит тот факт, что при однократном сравнении искомого элемента и некоторого элемента массива мы можем определить, справа или слева от текущего следует искать.
Слайд 9

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК искомый интервал поиска делится пополам и по значению

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

искомый интервал поиска делится пополам и по значению элемента

массива в точке деления определяется, в какой части следует искать значение на следующем шаге цикла;
для выбранного интервала поиск повторяется;
при «сжатии» интервала в 0 поиск прекращается;
в качестве начального интервала выбирается весь массив.
Сложность алгоритма - O(log(N)).
Слайд 10

ПОИСК В НЕУПОРЯДОЧЕННОМ МАССИВЕ Задача: дан одномерный неупорядоченный массив, состоящий из

ПОИСК В НЕУПОРЯДОЧЕННОМ МАССИВЕ

Задача: дан одномерный неупорядоченный массив, состоящий из целых

чисел. Проверить, содержится ли данное число в этом массиве.
Простой метод (последнее вхождение):
int j = -1;
for (i=0; i < n; i++)
if (a[i] == k) j = i;
«Барьерный» метод (первое вхождение):
a[n+1] = k;
for (i=0; a[i] != k; i++);
Слайд 11

БИНАРНЫЙ ПОИСК В УПОРЯДОЧЕННЫХ МАССИВАХ l=0; r=N-1; while (l m=(l+r)/2; if

БИНАРНЫЙ ПОИСК В УПОРЯДОЧЕННЫХ МАССИВАХ
l=0;
r=N-1;
while (lm=(l+r)/2;
if (a[m]else r=m;
}
if (a[r]==k)

cout<else cout<<"-1";
Слайд 12

БИНАРНЫЙ ПОИСК ДЛЯ МОНОТОННЫХ ФУНКЦИЙ Задача: для данного вещественного числа x

БИНАРНЫЙ ПОИСК ДЛЯ МОНОТОННЫХ ФУНКЦИЙ

Задача: для данного вещественного числа x (x≥1)

найти кубический корень с заданной точностью.
r = x;
l = 1;
while (fabs(l-r)>eps) {
m=(l+r)/2;
if (m*m*melse r=m;
}
Слайд 13

БИНАРНЫЙ ПОИСК ПО ОТВЕТУ Пусть у нас есть функция f, которая

БИНАРНЫЙ ПОИСК ПО ОТВЕТУ

Пусть у нас есть функция f, которая принимает

значения "истина" (1) или "ложь" (0), заданная на множестве [0..maxval].
При этом она обладает тем свойством, что сначала все значения истинны, а потом все ложны. [1, 1, ... , 1, 0, 0, ... , 0] - значения функции.
Иначе говоря, это означает, что
(f(x) и y <= x) => f(y).
Искомый элемент - самая правая единица в массиве (к отсортированному массиву применяется обычный бинарный поиск).
Слайд 14

БИНАРНЫЙ ПОИСК ПО ОТВЕТУ Обычный бинарный поиск - частный случай бинарного

БИНАРНЫЙ ПОИСК ПО ОТВЕТУ

Обычный бинарный поиск - частный случай бинарного поиска

по ответу.
Пусть нам дан массив, отсортированный по возрастанию. Требуется найти самое правое вхождение элемента key в массив.
Тогда положим f(x) = (x <= key).
Задача сведена к бинарному поиску по ответу.
Слайд 15

ЗАДАЧА СОРТИРОВКИ Пусть есть последовательность a0, a1... an и функция сравнения,

ЗАДАЧА СОРТИРОВКИ

Пусть есть последовательность a0, a1... an и функция сравнения, которая на

любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно.
Задача сортировки состоит в перестановке членов последовательности таким образом, чтобы выполнялось условие: ai <= ai+1, для всех i от 0 до n.
Слайд 16

АЛГОРИТМ СОРТИРОВКИ Алгоритм сортировки — это алгоритм для упорядочения элементов в

АЛГОРИТМ СОРТИРОВКИ

Алгоритм сортировки — это алгоритм для упорядочения элементов в последовательности.
Та

часть элемента данных, которая идентифицирует его и используется для поиска, называется ключом.
Остальная часть несет в себе содержательную информацию, которая извлекается и используется из найденного элемента данных.
Слайд 17

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ Время сортировки — основной параметр, характеризующий быстродействие алгоритма.

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ

Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется

также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера последовательности n.
Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2).
Идеальное поведение для сортировки — O(n).
Слайд 18

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ Память — ряд алгоритмов требует выделения дополнительной памяти

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ

Память — ряд алгоритмов требует выделения дополнительной памяти под временное

хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.
Слайд 19

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ Устойчивость — устойчивая сортировка не меняет взаимного расположения

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ

Устойчивость — устойчивая сортировка не меняет взаимного расположения элементов

с одинаковыми ключами.
Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Слайд 20

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ

Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов

между собой, называются основанными на сравнениях.
Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения.
Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Слайд 21

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ Признаками классификации могут быть: структуры данных, используемые при

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ

Признаками классификации могут быть:
структуры данных, используемые при сортировке (массивы,

списки, деревья),
местонахождение данных – в памяти (внутренняя) и в файлах (внешняя).
эффективность (трудоемкость) алгоритмов.
Слайд 22

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ

КЛАССИФИКАЦИЯ АЛГОРИТМОВ СОРТИРОВКИ

Слайд 23

КВАДРАТИЧНЫЕ И СУБКВАДРАТИЧНЫЕ АЛГОРИТМЫ СОРТИРОВКИ НЕ ИСПОЛЬЗУЮЩИЕ ДОПОЛНИТЕЛЬНУЮ ПАМЯТЬ

КВАДРАТИЧНЫЕ И СУБКВАДРАТИЧНЫЕ АЛГОРИТМЫ СОРТИРОВКИ

НЕ ИСПОЛЬЗУЮЩИЕ ДОПОЛНИТЕЛЬНУЮ ПАМЯТЬ

Слайд 24

СОРТИРОВКА ПУЗЫРЬКОМ При проходе снизу вверх по массиву сравниваются пары соседних

СОРТИРОВКА ПУЗЫРЬКОМ

При проходе снизу вверх по массиву сравниваются пары соседних элементов.

Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
Слайд 25

СОРТИРОВКА ПУЗЫРЬКОМ Производился ли на i-проходе обмен? Если нет - алгоритм

СОРТИРОВКА ПУЗЫРЬКОМ

Производился ли на i-проходе обмен? Если нет - алгоритм заканчивает

работу.
Шейкер-сортировка: направление следующих один за другим проходов меняется.
Слайд 26

СРАВНИТЕЛЬНЫЙ АНАЛИЗ Среднее количество сравнений, хоть и уменьшилось, но остается O(n2),

СРАВНИТЕЛЬНЫЙ АНАЛИЗ

Среднее количество сравнений, хоть и уменьшилось, но остается O(n2), в

то время как число обменов не изменилось. Среднее(оно же худшее) количество операций остается квадратичным.
Дополнительная память не требуется.
Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного.
Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
Слайд 27

СОРТИРОВКА ВЫБОРОМ Идея метода состоит в том, чтобы создавать отсортированную последовательность

СОРТИРОВКА ВЫБОРОМ

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем

присоединения к ней одного элемента за другим в правильном порядке.
Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.
Слайд 28

СОРТИРОВКА ВЫБОРОМ На i-м шаге выбираем min(a[i] ... a[n]) и меняем

СОРТИРОВКА ВЫБОРОМ

На i-м шаге выбираем min(a[i] ... a[n]) и меняем его

местами с a[i].
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] является упорядоченной.
Слайд 29

СОРТИРОВКА ВЫБОРОМ n + (n-1) + (n-2) + (n-3) + ...

СОРТИРОВКА ВЫБОРОМ

n + (n-1) + (n-2) + (n-3) + ... +

1 = 1/2 * ( n2+n ) = T (n2)
Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a, так что метод неустойчив.
Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Слайд 30

СОРТИРОВКА ВСТАВКАМИ В сортировке пузырьком на i-м шаге элементы a[0]...a[i] стоят

СОРТИРОВКА ВСТАВКАМИ

В сортировке пузырьком на i-м шаге элементы a[0]...a[i] стоят на

правильных местах и никуда более не переместятся.
При сортировке вставками последовательность a[0]...a[i] упорядочена. (более слабое утверждение)
При этом по ходу алгоритма в нее будут вставляться все новые элементы.
Слайд 31

СОРТИРОВКА ВСТАВКАМИ На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и

СОРТИРОВКА ВСТАВКАМИ

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем

на нужное место в готовую часть массива.
Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.
В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.
Слайд 32

СОРТИРОВКА ВСТАВКАМИ Таким образом, в процессе вставки мы "просеиваем" элемент x

СОРТИРОВКА ВСТАВКАМИ

Таким образом, в процессе вставки мы "просеиваем" элемент x к

началу массива, останавливаясь в случае, когда:
1. Найден элемент, меньший x или
2. Достигнуто начало последовательности.
Слайд 33

СОРТИРОВКА ВСТАВКАМИ Аналогично сортировке выбором, среднее, а также худшее число сравнений

СОРТИРОВКА ВСТАВКАМИ

Аналогично сортировке выбором, среднее, а также худшее число сравнений и

пересылок оцениваются как T(n2).
Дополнительная память не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро.
Алгоритм устойчив.
Слайд 34

СОРТИРОВКА ВСТАВКАМИ Заметим, что на каждом шаге внутреннего цикла проверяются 2

СОРТИРОВКА ВСТАВКАМИ

Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия.


Можно объединить из в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива.
Тогда при j=0 будет заведомо верно a[0] <= x. Цикл остановится на нулевом элементе, что и было целью условия j>=0.
Для окончания сортировки возвращаем элемент.
Слайд 35

СРАВНЕНИЕ АЛГОРИТМОВ

СРАВНЕНИЕ АЛГОРИТМОВ

Слайд 36

СОРТИРОВКА ШЕЛЛА Алгоритм сортировки массива a[0].. a[15]. Вначале сортируем простыми вставками

СОРТИРОВКА ШЕЛЛА

Алгоритм сортировки массива a[0].. a[15].
Вначале сортируем простыми вставками каждые 8

групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]).
Далее сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).
Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).
В конце сортируем вставками все 16 элементов.
Слайд 37

СОРТИРОВКА ШЕЛЛА

СОРТИРОВКА ШЕЛЛА

Слайд 38

СОРТИРОВКА ШЕЛЛА Приращение - расстояние между сортируемыми элементами, в зависимости от

СОРТИРОВКА ШЕЛЛА

Приращение - расстояние между сортируемыми элементами, в зависимости от прохода.
Формула

Седжвика:
последовательность вычисляется в порядке, противоположном используемому.
начальное приращение выбирается по правилу: начинаем с inc[s-1], если 3*inc[s] > size.
среднее количество операций: O(n7/6), в худшем случае - порядка O(n4/3).
Слайд 39

СРАВНЕНИЕ АЛГОРИТМОВ коричневая: пузырьком; синяя: шейкерная; розовая: выбором; желтая: вставками; голубая: вставками +СО; фиолетовая: Шелла.

СРАВНЕНИЕ АЛГОРИТМОВ

коричневая:
пузырьком;
синяя:
шейкерная;
розовая:
выбором;
желтая: вставками;
голубая: вставками +СО;
фиолетовая: Шелла.

Слайд 40

КОНТРОЛЬНАЯ РАБОТА N2 Алгоритмы сортировки реализовать в виде функций, возвращающих в

КОНТРОЛЬНАЯ РАБОТА N2

Алгоритмы сортировки реализовать в виде функций, возвращающих в качестве

результата характеристику трудоемкости алгоритма (количество сравнений).
Использовать файлы (fstream) для хранения промежуточных и окончательных результатов работы программы.
Получить трудоемкость для различных значений N=1000, 5000, 10000. Сравнить с теоретической оценкой. Нарисовать график.
- Предыдущая
Водный обмен растений
Следующая -
Пифагорейская школа

Похожие презентации

Унифицированный язык моделирования UML
Темпоральные логики и их применение в верификации реагирующих программных систем
Визуализация научных трудов и ораторское искусство
Базы данных в Microsoft Office Access
Информационные системы управления корпоративным контентом
Коммуникативная природа информационного общества
Поколения ЭВМ
Поиск объекта по фото в интернет-магазинах через Telegram
Файлы и файловая система. Информатика 7 класс
Правовые основы пользования информационными ресурсами (ОПОИБ, лекция 2)
Алгоритм. Исполнители алгоритмов
Introduction to Software Architecture and Design
Структура презентации
Синтаксис и алфавит языка Си. (Лекция 2)
Использование цифровых технологий и работа в цифровой среде
Заголовок слайда. Текст слайда
Семинары по подготовке к Олимпиаде D-Link по сетевым технологиям
Разработка дидактических материалов к учебному курсу Сам себе админ для системы дополнительного образования
Основные информационные процессы
Основные объекты и приемы управления ОС
Кодирование информации
Список источников. Правила оформления
Современные архитектуры ВС. Параллельные системы. ВС с массовым параллелизмом
Технические средства мультимедиа
Урок информатики 8 класс Тема: «Графические редакторы»
Строки. Создание строки
Несколько активностей. Лекция №5
Layout - разметка
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть