Модификация массивов. Лабораторная работа 7. Алгоритмы поиска в регулярном типе данных. Простейшие классические Алгоритмы. Сортировка в массиве

Модификация массивов

1. В одномерном массиве переставьте первый и последний элементы местами.

2. Переставьте элементы одномерного массива в обратном порядке. Нового массива не заводить.

3. Осуществите циклическую перестановку элементов одномерного массива: первый элемент должен стать вторым, второй - третьим и т. д., последний - первым. Нового массива не заводить.

4. Из массива В(k) убрать все отрицательные элементы, заменив их на значения предыдущих элементов.

5. Дан одномерный массив N(5). Все его элементы, не равные 0 переписать, сохраняя их порядок в начало массива, а нулевые - в конец массива (новый массив не заводить! ).

6. Элементы главной диагонали В(i)(i) квадратной матрицы B(n)(n) поставить на место максимального элемента в этой строке. 1Главная диагональ образована из элементов матрицы, имеющих одинаковые индексы строки и столбца. Главную диагональ имеют только квадратные матрицы!

7. В массиве X(M) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем 1, и, наконец, все 2. (Дополнительного массива не заводить. )

Указание. При решении этой задачи, ничего не нужно переставлять. Нужно сосчитать, сколько в массиве нулей, единиц и двоек, и заполнить массив требуемым образом.

8. Характеристикой столбца целочисленной матрицы назовем сумму модулей его отрицательных нечетных элементов. Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик.

9. " Сожмите" массив, " выбросив" каждый второй его элемент (дополнительные массивы использовать не разрешается! ).

10. Целое неотрицательное число М задано массивом своих двоичных цифр

a(1), a(2), ..., a(n-1), т. е. М=a(n-1)·2^n-1+a(n-2) 2^n-2+... +a(1) 2+a(0),

где a(i)=0 или a(i)=1 (i=0, 1, 2,..., n-1). Напечатать массив двоичных цифр числа М+1.

11. Транспонируйте матрицу (двухмерный массив), содержащую одинаковое количество строк и столбцов.

12. В заданном одномерном массиве поменяйте местами элементы в парах " элемент с нечетным номером - элемент с четным номером" (дополнительные массивы не использовать).

13. Объединить элементы массивов В и С, содержащих по Т элементов, в массив А таким образом, чтобы в массиве А на четных местах были элементы массива В, а на нечетных местах - элементы массива C (A, B, C - одномерные массивы).

14. Дан вещественный вектор А(n), такой что a₁≤ a₂≤... ≤ a_n и число В. Построить вектор С(n+1), элементами которого являются элементы вектора А и число В, упорядоченный по невозрастанию.

ЛАБОРАТОРНАЯ РАБОТА 7. АЛГОРИТМЫ ПОИСКА В РЕГУЛЯРНОМ ТИПЕ ДАННЫХ. ПРОСТЕЙШИЕ КЛАССИЧЕСКИЕ АЛГОРИТМЫ. СОРТИРОВКА В МАССИВЕ

7. 1 ЦЕЛЬ РАБОТЫ

 Познакомиться с простейшими классическими алгоритмами сортировки в регулярном типе данных, а также с основными алгоритмами поиска в массивах.

7. 2 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Под сортировкой обычно понимают процесс перестановки элементов данного множества в определенном порядке.

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

Ниже мы рассмотрим методы сортировки элементов в массивах (методы сортировки массивов).

Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочивание элементов нужно выполнять на одном и том же месте и что методы, которые пересылают элементы из массива А в массив В, не представляют для нас интереса. Проблема сортировки массивов относится в информатике к классичес­ким. Она кажется простой, ведь всем приходилось выполнять какую-либо механическую сортировку, была ли то раскладка игральных карт, гардеробных номерков, карточек из библиотечного каталога или денежных счетов. Однако простота эта иллюзорна. Хотя первые программы сортировки были написаны Дж. фон Нейманом в 1945 г., какого-либо значительного продвижения в теории сортировки не наблюдалось в течение последующих двадцати лет.

Рассмотрим несколько методов сортировки массивов. Для определен­ности, приведем методы сортировки (упорядочивания) векторов по неубыванию.

Пусть n - число элементов вектора A, а iизменяется от 0 до n-2.

1. Вектор называется упорядоченным по неубыванию, если для всех i выполнено A(i)< =A(i+1).

2. Вектор называется упорядоченным по невозрастанию, если для всех i выполнено A(i)> =A(i+1).

3. Вектор называется упорядоченным по убыванию, если для всех i выполнено A(i)> A(i+1).

4. Вектор называется упорядоченным по возрастанию, если для всех i выполнено A(i)< A(i+1).

Сортировка обменом

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

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

(См. Пример 1. )

⇐ Предыдущая17181920212223242526Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: