МАССИВЫ Одномерные, двумерные и т. д :421 Лекция по АЯиОП уч. г. г.

Массивы Массив это пронумерованная последовательность величин одинакового типа, обозначаемая одним именем. Элементы массива располагаются в последовательных ячейках памяти, обозначаются именем массива и индексом. Каждое из значений, составляющих массив, называется его компонентой ( или элементом массива ). Массив данных в программе рассматривается как переменная структурированного типа. Массиву присваивается имя, посредством которого можно ссылаться как на массив данных в целом, так и на любую из его компонент. Вообще, массив – однородный, упорядоченный структурированный тип данных с прямым доступом к элементам :422

Массивы Переменные, представляющие компоненты массивов, называются переменными с индексами в отличие от простых переменных, представляющих в программе элементарные данные. Индекс в обозначении компонент массивов может быть константой, переменной или выражением порядкового типа ( целочисленный, логический, символьный, перечислимый, диапазон ). Если за каждым элементом массива закреплен только один его порядковый номер, то такой массив называется линейным. Вообще количество индексов элементов массива определяет размерность массива. По этом признаку массивы делятся на одномерные ( линейные ), двумерные, трёхмерные и т. д :423

Рекурсия

Рекурсия Рекурсия процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии. Термин « рекурсия » используется в различных специальных областях знаний от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций : рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений :425

Рекурсия " Чтобы понять рекурсию, сначала необходимо понять рекурсию ". Данное высказывание очень четко выражает суть рекурсии. Рекурсия является базовой концепцией программирования вообще. Она включает вызов функции из той же самой функции. Почему это может понадобиться ? Предположим, что имеется массив массивов. Каждый из этих массивов может иметь в себе массивы, которые могут иметь массивы, которые могут иметь... собственно, в этом и состоит идея. Таким образом мы имеем множество массивов в других массивах. Как выполнить одну и ту же операцию на всех элементах во всех этих массивах ? Можно попробовать использовать простой цикл for, но неизвестно, сколько имеется массивов, и неизвестно, как глубоко распространяется вложение массивов. Поэтому остается только концепция рекурсии :426

Рекурсия В этом примере мы циклически перебираем все элементы массива первого уровня. Если какой - либо из этих элементов в массиве сам будет массивом, мы снова вызываем функцию, передавая этот элемент как первичный массив. Затем функция будет перебирать этот массив и снова вызывать себя, пока не останется ни одного массива :427

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

Рекурсия в программировании Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят ( или в некоторых условиях могут приводить ) к слишком большой глубине рекурсии :429

Рекурсия в программировании Есть специальный тип рекурсии, называемый « хвостовой рекурсией ». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода ( исходного или исполняемого ), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны ( например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя ), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений язык Scheme ( диалект языка Lisp), описание которого содержит все необходимые сведения. Любую рекурсивную функцию можно заменить циклом и стеком :4210

Пример рекурсии :4211

Пример рекурсии #include #define N 5 void Print(int n) // функция печати { printf("%d\n",n); // печать до рекурсии if (n>0) // условие рекурсивного вызова Print(n-1); // рекурсивный вызов функции печати printf("%d\n",n); // печать после рекурсии } int main() { Print(N); // вызов функции на исполнение return 0; } :4212

Пример рекурсии #include #define N 5 void Print(int n) // функция печати { //printf("%d\n",n); // печать до рекурсии if (n>0) // условие рекурсивного вызова Print(n-1); // рекурсивный вызов функции печати printf("%d\n",n); // печать после рекурсии } int main() { Print(N); // вызов функции на исполнение return 0; } :4213

Ханойская башня Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее. Эту известную игру придумал французский математик Эдуард Люка, в 1883 году [1] её продавали как забавную игрушку. Первоначально она называлась « Профессор Клаус (Claus) из Колледжа Ли - Су - Стьян (Li-Sou-Stian)»[1] но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа не более чем анаграмма фамилии изобретателя игры профессора Люка (Lucas) из колледжа Сен - Луи (Saint Louis) :4214

Легенда о Ханойской башне Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным - давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска. Брахма поместил на один из стержней 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир :4215

Легенда о Ханойской башне Количество перекладываний в зависимости от количества колец вычисляется по формуле 2 n - 1. Число перемещений дисков, которые должны совершить монахи, равно Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет. В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к не рекурсивным :4216

Ханойская башня :4217

Пример алгоритма решения на языке C++: // Ханойские башни #include using namespace std; void hanoi_towers(int quantity, int from, int to, int buf_peg) //quantity- число колец, from- начальное положение колец (1-3),to- конечное положение колец (1-3) { //buf_peg - промежуточный колышек (1-3) if (quantity != 0) { hanoi_towers(quantity-1, from, buf_peg, to); cout "

Ханойская башня. Пример алгоритма решения на языке C: :4219

Ханойская башня. Пример алгоритма решения на языке C: #include /* _ ___ _____ a b c */ // ===> tmp cnt void Move ( char a, char b, char c, char n)// функция перемещения n колец с позиции а на позицию b, используя временную позицию c { static int k = 1; if (n>1) { Move ( a, c, b, n-1); // функция перемещает (n-1) колец с позиции а на позицию с, используя временную позицию b Move ( a, b, c,1); // функция перемещает 1 кольцо с позиции а на позицию b, используя временную позицию с Move ( c, b, a, n-1); // функция перемещает (n-1) колец с позиции с на позицию b, используя временную позицию а } else {printf( "%2d %c => %c\n",k, a, b); k++;} } int main() { Move( 'a', 'b', 'c', 5 );// 'a', 'b', 'c' - пирамидки, 5 - количество колец return 0; } :4220

С ode::Blocks Полезные функции компилятора языка С :4221

Вызов окна Watches В меню Debug во вкладке Debugging windows вызвать окно Watches :4222

Установка начальной точки пошагового просмотра кода :4223 В меню Debug выбрать Run to cursor (F4), появится желтый треугольник. После чего выбираем в том же меню Next line (F7) столько раз, сколько строк кода необходимо отследить.

Просмотр значений переменных по строкам кода :4224

Важное примечание окно Watches работает в С ode::Blocks в том случае, если путь к файлу проекта в С ode::Blocks лежит в корневом каталоге или в папке, именованной латинскими буквами, которая находится в корневом каталоге :4225

Одномерные массивы : задачи сортировок элементов массива :4226

Задача сортировки элементов массива Задача сортировки одна из фундаментных в программировании. Решению проблем, связанных с сортировкой, посвящено множество фундаментальных научных исследований, разработано множество алгоритмов :4227

Задача сортировки элементов массива В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке. Часто при сортировке больших объемов данных нецелесообразно переставлять сами элементы, поэтому для решения задачи выполняется упорядочивание элементов по индексам. То есть индексы элементов выстраивают в такой последовательности, что соответствующие им значения элементов оказываются отсортированными по условию задачи. Сортировка применяется для облегчения поиска элементов в упорядоченном множестве., :4228

Сортировка Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию. Чаще всего при сортировке данных лишь часть их используется в качестве ключа сортировки. Ключ сортировки – это часть данных, определяющая порядок элементов. Таким образом, ключ участвует в сравнениях, но при обмене элементов происходит перемещение всей структуры данных. Например, в списке почтовой рассылки в качестве ключа может использоваться почтовый индекс, но сортируется весь адрес. При решении задач сортировок массивов ключ и данные совпадают :4229

Сортировки Существует множество различных алгоритмов сортировки. Все они имеют свои положительные и отрицательные стороны. Скорость работы алгоритма сортировки. Она непосредственно связана с количеством сравнений и количеством обменов, происходящих во время сортировки, причем обмены занимают больше времени. Сравнение происходит тогда, когда один элемент массива сравнивается с другим ; обмен происходит тогда, когда два элемента меняются местами. Различные сортировки массивов отличаются по быстродействию. Существуют простые методы сортировок, которые требуют порядка n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют порядка n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы :4230

Сортировки Простые методы сортировки можно разделить на три основные категории : сортировка методом " пузырька " ( простого обмена ); сортировка методом простого выбора ( простой перебор ); сортировка методом простого включения ( сдвиг - вставка, вставками, вставка и сдвиг ) :4231

Сортировка « методом пузырька » Самый известный алгоритм – пузырьковая сортировка (bubble sort, сортировка методом пузырька или просто сортировка пузырьком ). Его популярность объясняется интересным названием и простотой самого алгоритма. Алгоритм попарного сравнения элементов массива в литературе часто называют " методом пузырька ", проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы они увеличивались сверху вниз :4232

Сортировка « методом пузырька » Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма элемент, стоящий не на своём месте, " всплывает " до нужной позиции ( рис. 12.1) :4233 Рис Демонстрация сортировки по неубыванию методом " пузырька "

Сортировка « методом пузырька » // Описание функции сортировки методом " пузырька " void BubbleSort (int k,int x[max]) { int i,j,buf; for (i=k-1;i>0;i--) for (j=0;jx[j+1]) { buf=x[j]; x[j]=x[j+1]; x[j+1]=buf; } :4234

Сортировка « методом пузырька » В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет сравнений, где n – количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n-1 раз, а внутренний выполняется в среднем n/2 раз. Пузырьковая сортировка имеет такую особенность : неупорядоченные элементы на " большом " конце массива занимают правильные положения за один проход, но неупорядоченные элементы в начале массива поднимаются на свои места очень медленно. Поэтому, вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления :4235

Сортировка методом простого выбора ( простой перебор ) Это наиболее естественный алгоритм упорядочивания. При данной сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т. д. ( рис. 12.2) :4236

Сортировка методом простого выбора ( простой перебор ) Шаги алгоритма : находим минимальное значение в текущей части массива ; производим обмен этого значения со значением на первой неотсортированной позиции ; далее сортируем хвост массива, исключив из рассмотрения уже отсортированные элементы :4237 Рис Демонстрация сортировки по неубыванию методом простого выбора

Сортировка методом простого выбора ( простой перебор ) // Описание функции сортировки методом простого выбора void SelectionSort (int k,int x[max]) { int i,j,min,temp; for (i=0;i

Сортировка методом простого выбора ( простой перебор ) Как и в пузырьковой сортировке, внешний цикл выполняется n-1 раз, а внутренний – в среднем n/2 раз. Следовательно, сортировка методом простого выбора требует сравнений. Таким образом, это алгоритм порядка n2, из - за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке простым выбором одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке :4239

Сортировка методом простого включения ( сдвиг - вставка, вставками, вставка и сдвиг ) Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы ( такие как быстрая сортировка ), у него есть ряд преимуществ : прост в реализации ; эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим ; эффективен на наборах данных, которые уже частично отсортированы ; это устойчивый алгоритм сортировки ( не меняет порядок элементов, которые уже отсортированы ); может сортировать массив по мере его получения ; не требует временной памяти, даже под стек :4240

Сортировка методом простого включения На каждом шаге алгоритма выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен ; может использоваться практически любой алгоритм выбора ( рис. 12.3) :4241 Рис Демонстрация сортировки по неубыванию методом простого включения

Сортировка методом простого включения // Описание функции сортировки методом простого включения void InsertSort (int k,int x[max]) { int i,j, temp; for (i=0;i=0 && x[j]>temp; j--) x[j+1]=x[j];// сдвигаем элемент вправо, пока не дошли // место найдено, вставить элемент x[j+1]=temp; } :4242

Сортировка методом простого включения В отличие от пузырьковой сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1 ; в противном случае его производительность является величиной порядка n :4243

Ключевые термины Ключ сортировки – это часть данных, определяющая порядок элементов. Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию. Сортировка методом " пузырька " – это алгоритм попарного сравнения элементов одномерного массива. Сортировка методом простого включения – это алгоритм последовательного помещения элемента массива в отсортированную часть в соответствии с ключом сортировки. Сортировка методом простого выбора – это алгоритм последовательного обмена минимального и первого элементов неотсортированной части массива :4244

Краткие итоги Задачи сортировок массивов имеют широкое прикладное значение. Существует большое количество алгоритмов сортировок массивов, различающихся трудоемкостью. При оценке трудоемкости алгоритмов учитываются критерии : количество сравнений и перестановок, время в лучшем и худшем случаях, естественность поведения. К алгоритмам простых сортировок относятся : сортировка методом " пузырька ", сортировка методом простого выбора, сортировка методом простого включения. Простые сортировки эффективны на небольших объемах данных :4245

Лекция окончена !!! :4246