Сортування вибором.

1. За вказівкою викладача студент отримує бурильну головку, кернорвідривач та ОЦЕ.

2. Встановити: призначення породоруйнівного інструменту; для яких типів порід призначений кернорвідривач; до якого з видів ОЦЕ відноситься отриманий інструмент.

3. Дати характеристику кожного з отриманих зразків:

- вказати до якого типу належить;

- порахувати кількість робочих органів породоруйнівного інструменту (шарошок, лопатей, секторів);

- перелічити які переваги та недоліки мають дані типи інструментів.

4. Написати шифр колонкового долота. Після цього звірити з шифром вибитим на долоті;

5. Зробити короткі висновки щодо області застосування ін-трументів.

6. За результатами виконання п. 2-5 зробити опис результатів огляду отриманих типів інструментів.

КОНТРОЛЬНІ ЗАПИТАННЯ

1. Для чого проводять відбір керну?

2. З чого складається колонкове долото?

3.Які бурильні головки використовують для відбору керну?

4. Для чого призначені керновідривачі?

5. Які типи керновідривачів доцільно застосовувати у твердих, міцних і монолітних породах?

6. Недоліки шарошкових бурильних головок.

7. Перелічіть долота спецпризначення.

8. Для чого застосовують долота типу ПЦ?

9. Для чого призначені фрези?

10. Що називають пілотною ділянкою?

ЛАБОРАТОРНА РОБОТА № 4.1

ОПИС МАСИВІВ НА МОВІ C++. АЛГОРИТМИ І ПРОГРАМИ ОБРОБКИ ОДНОМІРНИХ МАСИВІВ. АЛГОРИТМИ СОРТУВАННЯ.

МЕТА РОБОТИ. Задавши із клавіатури послідовність символів, реалізувати обробку її, як зазначено у варіанті. Вихідні дані задати самостійно, з огляду на специфіку конкретного варіанта.

У програмі повинні бути передбачені процедури вводу-висновку послідовності символів і її обробки. Вихідні дані повинні вводитися з перевіркою на область припустимих значень.

У протоколі лабораторної роботи повинна бути наведена блок-схема алгоритму.

ТЕХНІЧНЕ І ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ:

ПЕОМ з операційною системою Windows та компілятором Borland С++.

КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ.

Сортування вибором.

Ідея методу полягає в тому, щоб створювати відсортовану послідовність шляхом приєднання до неї одного елемента одним в правильному порядку. Якщо вхідна послідовність майже впорядкована, то порівнянь буде стільки ж, значить алгоритм поводиться неприродно.

void selectSort(int* arr, int size) { int tmp, i, j, pos; for(i = 0; i < size; ++i) // i - номер текущего шага { pos = i; tmp = arr[i]; for(j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента { if (arr[j] < tmp) { pos = j; tmp = arr[j]; } } arr[pos] = arr[i]; arr[i] = tmp; // меняем местами наименьший с a[i] }} 2. Сортування бульбашкою (обміном). Ідея методу: крок сортування складається в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.void bubbleSort(int* arr, int size){ int tmp, i, j; for(i = 0; i < size - 1; ++i) // i - номер прохода { for(j = 0; j < size - 1; ++j) // внутренний цикл прохода { if (arr[j + 1] < arr[j]) { tmp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } }}Додаткова пам'ять, очевидно, не потрібно. Поведінка вдосконаленого (але не початкового) методу досить природне, майже відсортований масив буде відсортований набагато швидше випадкового. Сортування бульбашкою стійка, однак шейкер-сортування втрачає цю якість.На практиці метод бульбашки, навіть з поліпшеннями, працює надто повільно. А тому - майже не застосовується. 3. Сортування вставками. Сортування простими вставками в чомусь схожа на вищевикладені методи.void insertSort(int* a, int size) { int i, j, tmp; for (i = 1; i < size; ++i) // цикл проходов, i - номер прохода { tmp = a[i]; for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли a[j + 1] = tmp; // место найдено, вставить элемент }}Аналогічно сортуванню вибором, середнє, а також найгірше число порівнянь і пересилань оцінюються як O (n ^ 2), додаткова пам'ять при цьому не використовується.Хорошим показником сортування є вельми природна поведінка: майже відсортований масив буде досортірован дуже швидко. Це, вкупі з стійкістю алгоритму, робить метод хорошим вибором у відповідних ситуаціях.Алгоритм можна злегка поліпшити. Зауважимо, що на кожному кроці внутрішнього циклу перевіряються 2 умови. Можна об'єднати з в одне, поставивши в початок масиву спеціальний сторожовий елемент. Він повинен бути свідомо менше всіх інших елементів масиву. 4. Сортування Шелла. Сортування Шелла є досить цікавою модифікацією алгоритму сортування простими вставками.int increment(long inc[], long size) { int p1, p2, p3, s; p1 = p2 = p3 = 1; s = -1; do { if (++s % 2) { inc[s] = 8*p1 - 6*p2 + 1; } else { inc[s] = 9*p1 - 9*p3 + 1; p2 *= 2; p3 *= 2; } p1 *= 2; } while(3*inc[s] < size); return s > 0? --s: 0;}void shellSort(int* a, long size) { long inc, i, j, seq[40]; int s; s = increment(seq, size); // вычисление последовательности приращений while (s >= 0) // сортировка вставками с инкрементами inc[] { inc = seq[s--]; for (i = inc; i < size; ++i) { T temp = a[i]; for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc) a[j + inc] = a[j]; a[j] = temp; } }}Часто замість обчислення послідовності під час кожного запуску процедури, її значення розраховують заздалегідь і записують у таблицю, якою користуються, вибираючи початкове прирощення по тому ж правилу: починаємо з inc [s-1], якщо 3 * inc [s]> size. 5. Пірамідальне сортування. Пірамідальна сортування є першим з розглянутих методів, швидкодія яких оцінюється як O (n log n).template< class T >void downHeap(T a[], long k, long n) { // процедура просеивания следующего элемента // До процедуры: a[k+1]...a[n] - пирамида // После: a[k]...a[n] - пирамида T new_elem; long child; new_elem = a[k]; while(k <= n/2) // пока у a[k] есть дети { child = 2*k; if(child < n && a[child] < a[child+1]) // выбираем большего сына child++; if(new_elem >= a[child]) break; // иначе a[k] = a[child]; // переносим сына наверх k = child; } a[k] = new_elem;}void heapSort(int* a, long size) { long i; T temp; // строим пирамиду for(i = size / 2 - 1; i >= 0; --i) downHeap(a, i, size-1); // теперь a[0]...a[size-1] пирамида for(i=size-1; i > 0; --i) { // меняем первый с последним temp = a[i]; a[i] = a[0]; a[0] = temp; // восстанавливаем пирамидальность a[0]...a[i-1] downHeap(a, 0, i-1); }}Побудова піраміди займає O (n log n) операцій, причому більш точна оцінка дає навіть O (n) за рахунок того, що реальний час виконання downheap залежить від висоти вже створеної частини піраміди.Друга фаза займає O (n log n) часу: O (n) разів береться максимум і відбувається просіювання колишнього останнього елемента. Плюсом є стабільність методу: середнє число пересилань (n log n) / 2, і відхилення від цього значення порівняно малі.Метод не є стійким: по ходу роботи масив так "перетрушується", що вихідний порядок елементів може змінитися випадковим чином. 6. Швидке сортування (сортування Хоара) "Швидке сортування", хоч і була розроблена більше 40 років тому, є найбільш широко застосовуваним і одним їх найефективніших алгоритмів.void quickSortR(int* a, long N) {// На входе - массив a[], a[N] - его последний элемент. long i = 0, j = N; // поставить указатели на исходные места 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);}Кожне поділ вимагає, очевидно, O (n) операцій. Кількість кроків поділу (глибина рекурсії) становить приблизно log n, якщо масив ділиться на більш-менш рівні частини. Таким чином, загальну швидкодію: O (n log n), що і має місце на практиці. Порозрядне сортування. Розглянутий нижче алгоритм істотно відрізняється від описаних раніше.По-перше, він зовсім не використовує порівнянь сортируемих елементів.По-друге, ключ, за яким відбувається сортування, необхідно розділити на частини, розряди ключа. Наприклад, слово можна розділити по буквах, число - по цифрах...typedef struct slist_ { long val; struct slist_ *next; } slist; // функция сортировки возвращает указатель на начало отсортированного списка slist *radix_list(slist *l, int t) { // t - разрядность (максимальная длина числа) int i, j, d, m=1; slist *temp, *out, *head[10], *tail[10]; out=l; for (j=1; j<=t; j++) { for (i=0; i<=9; i++) head[i] = (tail[i]=NULL); while (l!= NULL) { d = ((int)(l->val/m))%(int)10; temp = tail[d]; if (head[d]==NULL) head[d] = l; else temp->next = l; temp = tail[d] = l; l = l->next; temp->next = NULL; } for (i=0; i<=9; i++) if (head[i]!= NULL) break; l = head[i]; temp = tail[i]; for (d=i+1; d<=9; d++) { if (head[d]!= NULL) { temp->next = head[d]; temp = tail[d]; } } m*=10; } return (out);}

Завдання:

Дано послідовність, що містить від 1 до 30 слів, у кожному з яких від 1 до 5 прописних латинських букв; між сусідніми словами - кома, за останнім словом - крапка. Надрукувати:

1) цю же послідовність слів, але у зворотному порядку;

2) ті слова, перед якими в послідовності перебувають тільки менші (за алфавітом) слова, а за ними - тільки більші;

3) цю же послідовність слів, але видаливши з її повторні входження слів;

4) всі слова, які зустрічаються в послідовності по одному разі;

5) всі різні слова, указавши для кожного з них число його входжень у послідовність;

6) всі слова за абеткою (у порядку зростання);

7) всі слова в порядку убування.

КОНТРОЛЬНІ ПИТАННЯ:

1. Особливості опису рядкових змінних.

2. Особливості використання операторів вводу-виведення для рядкових даних.

 

АНАЛІЗ ОДЕРЖАНИХ РЕЗУЛЬТАТІВ:

Підсумування та оформлення результатів експерименту слід обов’язково писати в кінці звіту в розділі «висновки». Висновки до лабораторної роботи слід писати про те, що було досліджено чи проаналізовано в даній лабораторній роботі. Не писати висновки від першої особи, уникаючи фраз типу: «я вивчи(в) / (ла)», чи «ми вивчили». Обов’язково здійснити та задокументувати обробку експериментальних даних.