Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Оператори циклу. Методи перестановок елементів масивів
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2021
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритмізація та програмування
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
Алгоритмізація та програмування 1: Базові концепції програмування
ЗВІТ
до лабораторної роботи № 7+8
«Оператори циклу. Методи перестановок елементів масивів»
Варіант 16
Дата «10» грудня 2021
ЗАВДАННЯ:
1. Ознайомитись з алгоритмами перестановок елементів масивів та способами сортування масивів. 2. У якості індивідуального завдання необхідно написати програмний код, що реалізує перестановку елементів масивів та сортування масивів. 3. Звернення до елементів масиву реалізувати за допомогою вказівника на масив. 4. Роздрукувати (вивести на екран) початковий масив та масив після виконання сортування.
Варіант завданнь:
Лабораторна робота №7:
За варінатом 16 – з таблиці з рисунка 1 варіант 4.
/
Рисунок 1.
/
Рисунок В.1
Лабораторна робота №8:
За варінатом 16 – з додатку 5.
16.Задана матриця M*N. Відсортувати непарні рядки за зростанням.
Теоритичні відомості:
Пузырьковая сортировка (Bubble-sort)
Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются / раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Худшее время
/
Лучшее время
/
Среднее время
/
Затраты памяти
/
Пример работы алгоритма
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как /
(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как /
(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (/), алгоритм не меняет их местами.
Второй проход:
(1 4 2 5 8) (1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как /
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
C
#define SWAP(A, B) { int t = A; A = B; B = t; }
void bubblesort(int *a, int n)
{
int i, j;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (a[j] > a[j + 1])
SWAP( a[j], a[j + 1] );
}
}
}
Быстрая сортировка
"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.
Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:
из массива выбирается некоторый опорный элемент a[i],
запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого, /
для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
В конце получится полностью отсортированная последовательность.
Рассмотрим алгоритм подробнее.
Разделение массива
На входе массив a[0]...a[N] и опорный элемент p, по которому будет производиться разделение.
Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p.
Далее, если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i,j по тем же правилам...
Повторяем шаг 3, пока i <= j.
Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3].
/
Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой - больше, либо равны p. Разделение завершено.
Общий алгоритм
Псевдокод.
quickSort ( массив a, верхняя граница N ) {
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quickSort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quickSort для него.
}
Реализация на Си.
template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
long i = 0, j = N-1; // поставить указатели на исходные места
T temp, p;
p = a[ N>>1 ]; // центральный элемент
// процедура разделения
do {
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;
if (i <= j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );
// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) quickSortR(a, j);
if ( N > i ) quickSortR(a+i, N-i);
}
Блок-схеми
Повна програма:
/
Методи:
Метод randomMatrix7:
/
Метод perevertMatrix7: Метод printMatrix7:
//
Метод randomMatrix8:
/
Метод perevertMatrix8:
/
Метод printMatrix8: /
Метод bubblesort:
/
Вивід програми:
/ /
Код програми:
Посилання на Repl.it:
https://replit.com/join/mybbanxcjq-tr-15khavkin
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void randomMatrix7(int size, char mat[size][size]){//Метод для заповнення матриці
srand(time(NULL));
int ran;
char alf[26];
for (int i = 0; i < 26; i++){
alf[i] = i + 65; //У массиві будут зберігатися усі літери у верхньому регистрі.
}
for(int i=0; i<size;i++){
for(int j=0;j<size;j++){
ran = rand() % 26; //Генерація випадкого числа від 0 до 25
mat[i][j]=alf[ran];
}
}
}
void perevertMatrix7(int size, char mat[size][size]){//Метод для перестановки матриці
char left,right;
int n=size;
for(int i=0; i<size-1;i++){
for(int j=0;j<size-i-1;j++){
left = mat[i][j];
right = mat[n-1-j][n-1-i];
mat[i][j]=right;
mat[n-1-j][n-1-i]=left;
}
}
}
void printMatrix7(int size, char mat[size][size]){//Метод для виводу матриці
for(int i=0; i<size;i++){
printf("\n");
for(int j=0;j<size;j++){
printf("\t%c\t", mat[i][j]);
}
}
}
void randomMatrix8(int N, int M, int ar8[N][M]){//Метод для заповнення матриці
srand(time(NULL));
for (int i = 0; i < N; i++ ) {
for (int j = 0; j < M; j++ ){
ar8[i][j]= rand() % 40 - 20;//Призначення елементу матриці випадкового значенння
}
}
}
void bubblesort(int *a, int n){//Метод сортивування одновимірного масиву методом бульбашки
int i, j;
int temp;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (a[j] > a[j + 1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
void perevertMatrix8(int N, int M, int mat[N][M]){//Метод для перестановки матриці
int st[M];//Ініціалізація додаткового ондовимірного масиву для
for(int i=0; i<N;i++){//Цикли для опрацювання тільки непарних рядків
for(int j=0;j<M;j++){
st[j]=mat[i][j];
}
bubblesort(st,M);//Сортировка строки
for(int j=0;j<M;j++){
mat[i][j]=st[j];
}
i++;
}
}
void printMatrix8(int N, int M, int mat[N][M]){//Метод для виводу матриці
printf("\n");
for(int i=0; i<N;i++){
for(int j=0;j<M;j++){//Вивід матриці
if(i%2==0){//Перевірка на непарність рядка та зміна його кольру у залежності від результату
printf("\033[1;32m");
printf("%4d", mat[i][j]);
}
else{
printf("\033[0m");
printf("%4d", mat[i][j]);
}
}
printf("\n");
}
}
int main(void){
int k,n,m;
//Завдання 7-ї лабораторної роботи
printf("Завдання для 7-ї лабораторної\nВвести розмірність для матриці (за варіантом 4):\n");
scanf("%d", &k);//Зчитування розмірності матриці
char arr[k][k];//Ініціалізація матриці для обробки
randomMatrix7(k,arr);//Заповнення матриці
printf("\n\tПочаткова матриця\t");
printMatrix7(k,arr);
printf("\n\n\tПеревернута матриця\t");
perevertMatrix7(k,arr);//Перестановка матриці
printMatrix7(k,arr);
//Завдання 8-ї лабораторної роботи
printf("\n\nЗавдання для 8-ї лабораторної\nВвести розмірність для матриці N M (через пробіл):\n");
scanf("%d %d", &n,&m);//Зчитування розмірності матриці
printf("\nРядки для опрацювання та відсортировки будуть непарними, вони буду віділяться \033[1;32mзеленим\033[0m кольором\n\nПочаткова матриця N*M:");
int ar8[n][m];
randomMatrix8(n,m,ar8);//Заповнення матриці
printMatrix8(n,m,ar8);//Вивід початкової матриці
perevertMatrix8(n,m,ar8);//Опрацювання та сортировка массиву
printf("\n\033[0mОпрацювана та відсортована матриця:");
printMatrix8(n,m,ar8);//Вивід опрацьованного масиву
return 0;
}
Висновок:
У цій лабораторної роботі ознайомилися з методами перестановки елементів матриці. Було створено методи для сортировки, заповнення масиву випадковими символами (для матриці з 7-ї лабораторної) та цілими числами (для матриці з 8-ї лабораторної), вивід матриць. Перестановка для першої матриці було згідно до завдання 7-ї лабораторної роботи по варіанту, тобто перестановка через додаткову діагональ. У другій матриці потрібно було сортирувати непарні рядки за зростанням. Для цього було спочатку обрано метод швидкої сортировки, але він працював не коректно й видавав постійно помилки. Чому так так і не було з’ясовано. Потім було переобрано метод сортировки і вибір пав на самий стабільний і простий метод бульбашки. З ним ніяких проблем не було знайдено. Створенні блок-схеми до коду. Зроблено звіт з лабораторної роботи та вчасно надіслано викладачу на перевірку.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора