Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.
Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность...
Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.
Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части - готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].
На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда
1. найден элемент, меньший x или
2. достигнуто начало последовательности.
Ниже показан алгоритм выполнения данного метода.
При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в списке студентов фамилия Петров. Задачи такого типа называются поиском в массиве.
Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска.
Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).
Метод (алгоритм) бинарного поиска реализуется следующим образом:
1. Сначала образец сравнивается со средним (по номеру) элементом массива.
* Если образец равен среднему элементу, то задача решена.
* Если образец меньше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента, и задача сокращается на половину элементов и дальнейший поиск осуществляется в левой части массива.
* Если образец больше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента, и дальнейший поиск осуществляется в правой части массива.
Алгоритм бинарного поиска, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение минимального (по индексу) элемента больше, максимального.
Функция Генератор случайных чисел. Синтаксис #include<stdlib.h> int random(int num); Файл, содержащий stdlib.hпрототип Описание Функция random возвращает случайное число в диапазоне от 0 до num-1. random(num) это макро, определенное в виде (rand()%num). И num и возвращаемое значение целые. Возвращаемое random возвращает случайное число в диапазоне отзначение 0 до num-1. Переносимость Соответствующая функция существует в Turbo Pascal. Смотрите также rand, randomize, srand. Пример:
Внешняя память - это память, реализованная в виде внешних, относительно материнской платы, устройств с разными принципами хранения информации и типами носителя, предназначенных для долговременного хранения информации. В частности, в внешней памяти хранится все программное обеспечение компьютера. Устройства внешней памяти могут размещаться как в системном блоке компьютера, так и в отдельных корпусах. Физически, внешняя память реализована в виде накопителей.
Накопители - это запоминающие устройства, предназначенные для продолжительного (что не зависит от электропитания) хранения больших объемов информации. Емкость накопителей в сотни раз превышает емкость оперативной памяти или вообще неограниченная, когда речь идет о накопителях со сменными носителями.
Накопитель можно рассматривать как совокупность носителя и соответствующего привода. Различают накопители с сменными и постоянными носителями.
Привод - это объединение механизма чтения-записи с соответствующими электронными схемами управления. Его конструкция определяется принципом действия и видом носителя. Носитель - это физическая среда хранения информации, по внешнему виду может быть дисковым или ленточным. По принципу запоминания различают магнитные, оптические и магнитооптичческие носители. Ленточные носители могут быть лишь магнитными, в дисковых носителях используют магнитные, магнитооптические и оптические методы записи-считывания информации. Самыми распространенными являются накопители на магнитных дисках, которые делятся на накопители на жестких магнитных дисках (НЖМД) и накопители на гибких магнитных дисках (НГМД), и накопители на оптических дисках, такие как накопители CD-ROM, CD-R, CD-RW и DVD-ROM.
Накопители на жестких магнитных дисках (НЖМД)
НЖМД - это основное устройство для долговременного хранения больших объемов данных и программ. Другие, названия: жесткий диск, винчестер, HDD (Hard Disk Drive). Внешне, винчестер представляет собой плоскую, герметически закрытую коробку, внутри которой, находятся на общей оси несколько жестких алюминиевых или стеклянных пластинок круглой формы. Поверхность любого из дисков покрыта тонким ферромагнитным слоем (вещество, которое реагирует на внешнее магнитное поле), собственно на нем хранятся записанные данные. При этом запись проводится на обе поверхности каждой пластины (кроме крайних) с помощью блока специальных магнитных головок. Каждая головка находится над рабочей поверхностью диска на расстоянии 0,5-0,13 мкм. Пакет дисков вращается непрерывно и с большой частотой (4500-10000 об/мин), поэтому механический контакт головок и дисков недопустим.
Запись данных в жестком диске осуществляется следующим образом. При изменении силы тока, проходящего через головку, происходит изменение напряженности динамического магнитного поля в щели между поверхностью и головкой, что приводит к изменению стационарного магнитного поля ферромагнитных частей покрытия диска. Операция считывания происходит в обратном порядке. Намагниченные частички ферромагнитного покрытия являются причиной электродвижущей силы самоиндукции магнитной головки. Электромагнитные сигналы, которые возникают при этом, усиливаются и передаются на обработку.
Работой винчестера руководит специальное аппаратно-логическое устройство - контроллер жесткого диска. В прошлом это была отдельная дочерняя плата, которую подсоединяли через слоты к материнской плате. В современных компьютерах функции контроллера жесткого диска выполняют специальные микросхемы, расположенные в чипсете.
В накопителе может быть до десяти дисков. Их поверхность разбивается на круги, которые называются дорожками (track). Каждая дорожка имеет свой номер. Дорожки с одинаковыми номерами, расположенные одна над другой на разных дисках образуют цилиндр. Дорожки на диске разбиты на секторы (нумерация начинается с единицы). Сектор занимает 571 байт: 512 отведено для записи нужной информации, остальные под заголовок (префикс), определяющий начало и номер секции и окончание (суффикс), где записана контрольная сумма, нужная для проверки целостности хранимых данных. Секторы и дорожки образуются во время форматирования диска. Форматирование выполняет пользователь с помощью специальных программ. На неформатированный диск не может быть записана никакая информация. Жесткий диск можно разбить на логические диски. Это удобно, поскольку наличие нескольких логических дисков упрощает структуризацию данных, хранящихся на жестком диске.
Существует огромное количество разных моделей жестких дисков многих фирм, таких как Seagate, Maxtor, Quantum, Fujitsu и т.д. Для обеспечения совместимости винчестеров, разработаны стандарты на их характеристики, определяющие номенклатуру соединительных проводников, их размещение в переходных разъемах, электрические параметры сигналов. Распространенными являются стандарты интерфейсов IDE-(Integrated Drive Electronics) или ATA и более продуктивные EIDE (Enhanced IDE) и SCSI(Small Computer System Interface). Характеристики интерфейсов, с помощью которых винчестеры связаны с материнской платой, в значительной степени определяют производительность современных жестких дисков.
Среди других параметров, которые влияют на быстродействие HDD следует отметить следующие:
ü скорость обращения дисков - в наше время выпускаются накопители EIDE с частотой обращения 4500-7200 об/мин, и накопители SCSI - 7500-10000 об/мин;
ü емкость кэш-памяти - во всех современных дисковых накопителях устанавливается кэш-буфер, ускоряющий обмен данными; чем больше его емкость, тем выше вероятность того, что в кэш-памяти будет необходимая информация, которую не надо считывать с диска (этот процесс в тысячи раз медленней); емкость кэш-буфера в разных устройствах может изменяться в границах от 64 Кбайт до 2Мбайт;
ü среднее время доступа - время (в миллисекундах}, на протяжении которого блок головок смещается с одного цилиндра на другой. Зависит от конструкции привода головок и составляет приблизительно 10-13 миллисекунд;
ü время задержки - это время от момента позиционирования блока головок на нужный цилиндр до позицирования конкретной головки на конкретный сектор, другими словами, это время поиска нужного сектора;
ü скорость обмена - определяет объемы данных, которые могут быть переданы из накопителя к микропроцессору и в обратном направлении за определенные промежутки времени; максимальное значение этого параметра равно пропускной способности дискового интерфейса и зависит от того, какой режим используется: PIO ли DMA; в режиме PIO обмен данными между диском и контроллером происходит при непосредственном участии центрального процессора, чем больше номер режима PIO, тем выше скорость обмена; работа в режиме DMA (Direct Memory Access) разрешает передавать данные непосредственно в оперативную память без участия процессора; скорость передачи данных в современных жестких дисках колеблется в диапазоне 30-60 Мбайт/с.
Накопители на гибких магнитных диска (НГМД)
НГМД или дисковод вмонтирован в системный блок. Гибкие носители для НГМД выпускают в виде дискет (другое название флоппи-диск). Собственно, носитель - это плоский диск со специальной, достаточно плотной пленкой, покрытой ферромагнитным слоем и помещенной в защитный конверт с подвижной задвижкой в верхней части. Дискеты используются, в основном, для оперативного переноса небольших объемов информации с одного компьютера на другой. Данные, записанные на дискете можно защитить от стирания или перезаписи. Для этого нужно передвинуть маленькую защитную задвижку в нижней части дискеты таким образом, чтобы образовалось открытое окошко. Для того, чтобы разрешить запись, эту задвижку следует переместить назад и закрыть окошко.
Лицевая панель дисковода выведена на переднюю панель системного блока, на ней расположены карман, закрытый шторкой, куда вставляют дискету, кнопка для вынимания дискеты и лампочка-индикатор. Дискета вставляется в дисковод верхней задвижкой вперед, ее нужно вставить в карман накопителя и плавно продвинуть вперед до щелчка. Правильное направление вставления дискеты помечено стрелкой на пластиковом корпусе. Чтобы вынуть дискету из накопителя, нужно нажать на его кнопку. Световой индикатор на дисководе показывает, что устройство занято (если лампочка горит, вынимать дискету не рекомендуется). В отличие от жесткого диска, диск в НГМД приводится во вращение только при команде чтения или записи, в другое время он находится в покое. Головка чтения-записи во время работы механически контактирует с поверхностью дискеты, что приводит к быстрому изнашиванию дискет.
Как и в случае жесткого диска, поверхность гибкого диска разбивается на дорожки, которые в свою очередь разбиваются на секторы. Секторы и дорожки получаются во время форматирования дискеты. Сейчас дискеты поставляются отформатировавши. Основными параметрами дискеты является технологический размер (в дюймах), плотность записи и полная емкость. По размерам различают 3,5-дюймовые дискеты и 5,25-дюймовые дискеты (сейчас уже не используются). Плотность записи может быть простойSD (Single Density), двойной DD (Double Density) и высокой HD (High Density). Стандартная емкость 3,5-дюймовой дискеты - 1,44 Мбайт, возможно использование дискет емкостью 720 Кбайт. В настоящее время стандартом являются дискеты размером 3,5 дюйма, высокой плотности HD, имеющие емкость 1,44 Мбайта.
Во время пользования дискетой следует придерживаться таких правил:
ü не касаться рабочей поверхности дискеты;
ü не выгибать дискету;
ü не снимать металлическую задвижку, загрязненная дискета может повредить головки ;
ü сохранять дискеты подальше от источника магнитных полей;
ü перед использованием проверить дискету на наличие вирусов с помощью антивирусной программы.
