Рішення військово-прикладної задачі

Побудова блок-схеми алгоритму проста вставка. Програмна реалізація алгоритму, опис результатів. Особливості обліку ітерації масивів. Відсортування даних за допомогою програми Turbo Pascal. Аналітична оцінка трудомісткості, графічне представлення.
Краткое сожержание материала:

Размещено на

[Введите текст]

Харківський університет Повітряних Сил

Кафедра № 402

Контрольна робота з теми:

Рішення військово-прикладної задачі

Харків 2014



Зміст

Вступ

1. Блок-схема алгоритму проста вставка

1.1 Опис алгоритму проста вставка

1.2 Побудова блок-схеми алгоритму проста вставка

1.3 Опис блок-схеми алгоритму проста вставка

2. Програмна реалізація алгоритму проста вставка

2.1 Програмна реалізація алгоритму проста вставка

2.2 Опис програмної реалізації алгоритму проста вставка

2.3 Опис отриманих результатів

3. Оцінка трудомісткості простої вставки

3.1 Аналітична оцінка трудомісткості проста вставка

3.2 Графічне представлення оцінки трудомісткості проста вставка

3.3 Аналіз отриманих результатів

Висновки

Список використаних джерел



Вступ

Курсова робота є важливою частиною навчальної дисципліни «Інформатика». Вона закріплює та заглиблює знання, які курсанти отримали при вивченні дисципліни, та надає практичні навички і уміння у використанні ЕОМ для розв'язання військово-прикладних та прикладних задач за спеціальністю підготовки.

Ціль курсової роботи - (на основі знань, вмінь і навичок, отриманих з дисципліни Інформатика) отримання практичних навичок комплексного розв'язання військово-прикладної задачі з застосування ЕОМ, яке включає розробку алгоритму і програми розв'язання військово-прикладної задачі з використанням засобів мови Pascal, а також оцінювання ефективності отриманого рішення з використанням засобів пакету MathCad.

Основна мета курсової роботи - оволодіння сучасною технологією підготовки та рішення на ЕОМ розрахункових задач військового та прикладного характеру.



1. Блок-схема алгоритму сортування проста вставка

1.1 Опис алгоритму сортування проста вставка

Основна ідея алгоритму полягає в тому, щоб послідовно вибрати елементи з не відсортованого масиву та вставляти їх на свої місця в відсортований масив.

Алгоритм

Нехай заданий числовий масив m={m0,m1,m2,…,mn}.

Для формування відсортованої послідовності створюється масив r такої ж розмірності, як і масив m. Елемент m0 масиву m поміщається у нульову комірку масиву r: = . Індекс k останнього елемента в масиві r встановлюється до нуля: k=0.

Далі з масиву m до його вичерпання ітераційно вибираються елементи mi(i = 1,…,n) починаючи з елемента з індексом і=1; для кожного вибраного елемента mi в ході однієї ітерації з номером і реалізуються наступні кроки.

Крок 1. Пошук місцезнаходження вибраного елемента. Для елемента mi ітераційно (j=0,…,k), починаючи з j=0, шукається місце j вставки в відсортований масив r: якщо mi <ri, тоді місце вставного елементу mi - комірка j, вихід з циклу; інакше j=j+1: якщо j?k, перехід на крок 1.1; інакше - вихід з циклу.

Місце вставки j елементу mi знайдено.

Крок 2. Здвиг. Якщо на кроці 1 місце вставки в середині циклу не знайшли (j=k+1), отже це місце останнім елементом масиву r, крок 2 виконувати не потрібно, а потрібно тільки вставити елемент на своє місце. Інакше елементи масиву r з індексами j,…,k ітераційно (p=k,…,j), починаючи з найбільшого елемента rp, p=k, переміщуються на одну позицію вправо: записуємо rp+1=rp, припустимо р=р-1: якщо p?j, перехід на крок 2.1; інакше - вихід з циклу.



1.2 Побудова блок-схеми алгоритму сортування проста вставка

Ввід

Вивід

Крок 3. Вставка. Елемент mi вставляється на своє місце: rj=mi; індекс останнього елемента у відсортованому масиві r збільшується на одиницю, k=k+1. Крок 4. Завершення. Припускаємо і=і+1 і: якщо і ? n перехід на крок,1 інакше сортування завершене, вихід.

Опис блок схеми алгоритму сортування проста вставка

Ітераційно (i…n) починаючи з і=1, перебираємо елементи для кожного вибраного числа n, збільшуємо значення в комірці масиві проста вставка з індексом m, на одиницю. Далі припустимо що i=i+1. Якщо і<n - переходимо на mj<rj, тоді місце елемента, що mi вставляє - j осередок, інакше - вихід з циклу.

Наприклад, якщо зустрілися масиви m=0, збільшуємо значення нульової комірки на 1, якщо зустріли четвірку, збільшуємо значення комірки на 1.

В результаті підрахунків в кожній і-й комірці простої вставки буде записане число. Яке показує в скільки разів число і(з діапазону [1, n]) зустрілися в масиві m.

Далі припустимо, що j=0 ітераційно (і = 1,…, n), починаючи з і=1 перебираємо комірки масива проста вставка: якщо mi > 0 тоді: вважаємо, що rj=i, j=i+1 перехід на rp+1=rp.

Таким чином, якщо значення mi в і-ої комірки проста вставка була більше нуля(сі > 0) тоді сі = 2, то в початковому масиві m зустрілися дві одиниці і в результуючий масив буде виведено дві одиниці. Припустимо:

і=і+1, якщо і?k. Перехід до наступної інтеграції: записуємо rp+1=rp, інакше сортування закінчено, вихід з циклу. Інакше ітераційно(j=j,…,n) дописуємо елементи в кінці масива. Припустимо, що і=j=1, k=k+1, якщо

j?n, перехід: записуємо rp+1=rp, думаємо р=р-1: якщо р?j записуємо rp+1=rp інакше - вихід із циклу, інакше сортування закінчено, вихід.



2. Програмна реалізації алгоритму сортування

2.1 Програмна реалізація алгоритму сортування

Рис. 2.1

2.2 Опис програмної реалізації алгоритму сортування проста вставка

простий вставка масив ітерація

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

Далі у програмі йде цикл обліку ітерації масивів, після якого йде проведення ітерацій. В циклі йде процес елементів масиву, а потім йде процес змін елементів масиву при заданій умові.

Потім після проведення розрахунків йде виведення відсортованого масиву.

2.3 Опис отриманих результатів

В якості вихідних даних в нас було задано вихідний масив, який ми повинні були відсортувати за допомогою програми Turbo Pascal.

Рис. 2.2

З отриманих результатів у програмі Pascal можна зробити висновок що програма працює, тому що задані масиви були відсортовані.



3. Оцінка трудомісткості сортування

3.1 Аналітична оцінка трудомісткості сортування

Кожен алгоритм сортування характеризується трудомісткістю, яка являє собою Т(n) числа елементів n=n+1 масиву що сортується. При оцінці трудомісткості алгоритм сортування в першому наближені прийнято до уваги тільки кількість операцій порівнянь, що потребують для повного сортування масиву. Трудомісткість алгоритмів залежить не тільки від числа елементів масиву, що підлягають сортуванню, ай ще від інших характеристик. Для всіх алгоритмів обов'язкова степінь упорядкованості масиву - чим вона більше, тим трудомісткість менша.

Алгоритм проста вставка. Трудоємність даного алгоритму залежить від параметра х.

Т1(х):=0,75x2

Алгоритм лічильник

Трудоємність даного алгоритму залежить від параметра х,k.

T2(x,k):=2(x+k)

Алгоритм бульбашка. Трудоємність даного алгоритму залежить від параметра х.

Т3(х):= x2

Алгоритм злиття. Трудоємність даного алгоритму залежить від параметра х.



Т4(х):=5х

3.2 Графічне представлення оцінки трудомісткості сортування

Рис. 3.1



3.3 Аналіз отриманих результатів

З отриманих результатів можна побачити, що трудомісткість даної програми залежить від функції Т1(х):=0,75x2.

Підставивши кількісне значення цілей у формулі отримали: Т1(20):=300.

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

Порівнявши свої отримані результати з даними інших алгоритмів та проаналізувавши їх, я мушу сказати, що для вирішення нашої задачі доцільно буде використовувати алгоритм сортування «Лічильник». Тому, що саме за допомогою цього алгоритму ми отримали найменше значення.



Висновки

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

Моїм завданням було:

Скласти і описати блок схему алгоритму проста вставка, скласти на мові Pascal і описати програму проста вставка, одержати аналітичний...