озв’язання військово-прикладних задач із застосуванням електронних обчислювальних машин
План
Вступ
.
Блок-схема алгоритму сортування
.1
Опис алгоритму сортування проста вставка
.2
Побудова блок-схеми алгоритму сортування
2.
Програмна реалізації алгоритму сортування
2.1
Програмна реалізація алгоритму сортування
.2
Опис програмної реалізації алгоритму сортування
.3
Опис отриманих результатів
3.
Оцінка трудомісткості сортування
3.1
Аналітична оцінка трудомісткості сортування
.2
Графічне представлення оцінки трудомісткості сортування
.3
Аналіз отриманих результатів
Висновки
Список
використаних джерел
обчислювальний машина військовий
сортування
Вступ
Курсова робота є важливою частиною
навчальної дисципліни "Інформатика". Вона закріплює та заглиблює
знання, які курсанти отримали при вивченні дисципліни, та надає практичні
навички і уміння у використанні ЕОМ для розв’язання військово-прикладних та
прикладних задач за спеціальністю підготовки.
Ціль курсової роботи - (на основі
знань, вмінь і навичок, отриманих з дисципліни Інформатика) отримання
практичних навичок комплексного розв’язання військово-прикладної задачі з
застосування ЕОМ, яке включає розробку алгоритму і програму розв’язання
військово-прикладної задачі з використанням засобів мови Pascal, а також
оцінювання ефективності отриманого рішення з використанням засобів пакету
MathCad.
Основна мета курсової роботи -
оволодіння сучасною технологією підготовки та рішення на ЕОМ розрахункових
задач військового та прикладного характеру.
1. Блок-схема алгоритму сортування
1.1 Опис алгоритму
сортування проста вставка
Основна ідея алгоритму полягаяє в
тому що послідовно вибирати елементи з не відсортованого масиву та вставляти їх
на свої місця в відсортований масив.
Нехай заданий числовий масив
={m0 ,m1, m2,….,mn}.
Для формування відсортованої
послідовності створюється масив r такої ж розмірності , як і масив m. Елемент
m0 масиву m поміщається у нульовому коміру масиву r:
=m0.
Індекс k останнього елемента в
масиві r встановлюється до нуля: k=0.
Далі з масиву m до його вичерпання
ітераційно вибираються елементи mi (i=1,…,n) починаючи з елемента з індексом
i=1; для кожного вибраного елемента mi в ході однієї ітерації з номером і
реалізуються наступні кроки.
Крок 1. Пошук місцезнаходження
вибраного елемента. Для елемента mi ітераційно (j=0,…,k,) починаючи з j=0
шукається місце j вставки в відсортований масив r:
1.1 якщо mi < ri, тоді місце
вставного елементу mi комірка вихід з циклу;
1.2 інакше
=j+1:
якщо j≤k перехід на крок 1.1;
інакше - вихід з циклу.
Місце вставки j елементу mi
знайдено.
Крок 2. Зсув. Якщо на кроці 1 місце
вставки в середині циклу не знайшли (j=k+1), отже це місце останнім елементом
масиву r, крок 2 виконувати не потрібно,а потрібно тільки вставити елемент на
своє місце. Інакше елементи масиву r з індексами j,…,k ітераційно (p=k,…,j),
починаючи з найбільшого елемента rp, p=k, переміщуються на одну позицію вправо:
.1 записуємо
+1=rp
.2 припустимо
=p-1
якщо p≥j, перехід на крок 2.1;
інакше - вихід з циклу.
Крок 3. Вставка. Елемент mi
вставляєься на своє місце: rj=mi; індекс останнього елемента у відсотковому
масиві r збільшується на одиницю,
=k+1.
Крок 4. Завершення. Припускаємо
=i+1 i:
якщо i ≤ n перехід на крок, 1
Інакше сортування завершене, вихід.
1.2 Побудова блок-схеми алгоритму
сортування
На основі опису алгоритму проста
вставка побудуємо блок-схему.
Опис блок схеми алгоритму сортування
Крок 1: Підрахунок (Початок циклу
підрахунку).
Крок 2: Одержання відсортованого
масиву.
Ітераційно (i…n) починаючи з i=1,
перебираємо елемента для кожного вибраного числа n, збільшуємо значення в
комірці масиві проста вставка з індексом m, на одиницю. Далі припустимо що
i=i+1. Якщо i<n - переходимо на mj<rj, тоді місце елемента, що mi
вставляє - j осередок, інакше - вихід з циклу.
Наприклад, якщо зустрілися масиви
m=0, збільшуємо значення нульової комірки на 1. якщо зустріли четвірку,
збільшуємо значення комірки на 1.
В результаті підрахунків в кожній i
- й комірці простої вставки буде записане число. Яке показує в скільки разів
число i(з діапазону [1, n]) зустрілися в масиві m.
Далі припустимо, що j=0 ітераційно
(i = l,…, n ), починаючи з i=1 перебираємо комірки масива проста вставка : якщо
mi > 0 тоді : вважаємо , що rj=i, j=i+1 перехід на rp+1 =rp.
Таким чином, якщо значення mi в i-ої
комірки проста вставка була більше нуля (сі >0) тоді сі =2, то в початковому
масиві m зустрілися дві одиниці і в результуючий масив буде виведено дві
одиниці. Припустимо: i=i+1, якщо і≥к. Перехід до наступної інтеграції:
записуємо rp+1=rp, інакше сортування закінчено, вихід з циклу. Інакше
ітераційно (j=j,…,n) дописуємо елементи в кінці масива. Припустимо, що i=j=1,
k=k+1, якщо j≤n, перехід: записуємо rp+1=rp, думаємо p=p-1: якщо p≥j
2. Програмна реалізації алгоритму
сортування
.1 Програмна реалізація алгоритму
сортування
Згідно до блок схеми алгоритму
наведеної раніше розроблена програмна реалізація алгоритму проста вставка яка
наведена нижче.
.2 Опис програмної реалізації
алгоритму сортування
Згідно побудованої блок-схеми
алгоритму проведеної в підрозділі 1.2 розроблена програмна реалізація алгоритму
проста вставка яка поділяється на частини приведені нижче.
1. Описуюча частина, в якій
підключається бібліотеки, описуються константи та змінні.
2. Введення даних, в якій масив
заповнюється даними (за допомогою генератора випадкових чисел).
. Сортування, в якій масив
сортуються.
. Виведення результатів, в
якій виводяться відсортований масиви.
В якості вихідних даних в нас було
задано вихідний масив з 80 пріоритетних цілей, з виконанням оператора
випадкових чисел. Після виконання програмної реалізації алгоритму проста
вставка наведена в підрозділі 2.1 отримуємо наступні результати:
Отримані результати були перевірені
за 3 критеріями:
1) Кількісний критерій -
кількість чисел в початковому і кінцевому масиві збігаються.
2) Критерій складу - кількість
цифр одного достоїнства в початковому та кінцевому масиві.
) Критерій відношення - кожна
наступна цифра відсортованого масиву більша або дорівнює попередній.
3. Оцінка трудомісткості сортування
.1 Аналітична оцінка трудомісткості
сортування
Кожен алгоритм сортування
характеризується трудомісткістю, яка являє собою Т(n) числа елементів n=n+1
масиву що сортується. При оцінці трудомісткості алгоритм сортування в першому
наближені прийнято до уваги тільки кількість операцій порівнянь, що потребують
для повного сортування масиву. Трудомісткість алгоритмів залежить не тільки від
числа елементів масиву, що підлягають сортуванню, ай ще від інших характеристик.
Для всіх алгоритмів обов’язкова степінь упорядкованості масиву - чим вона
більше, тим трудомісткість менша.
Трудомісткість алгоритм проста
вставка оцінюється так;
Трудомісткість алгоритм лічильник
залежить від параметра n,k.
Трудомісткість алгоритм бульбашка
залежить від параметра n.
Трудомісткість алгоритм злиття
залежить від параметра n.
3.2 Графічне представлення оцінки
трудомісткості сортування
Згідно з критеріями оцінки
трудомісткості наведених в п. 3.1 можна виконати наступний аналіз
трудомісткості.
.3 Аналіз отриманих результатів
З отриманих результатів можна побачити,
що трудомісткість даної програми залежить від функції
Підставивши кількісне значення цілей
у формулі отримали:
Я отримав велике значення, тому
трудомісткість моєї програми висока, а отже для кращого сортування необхідно
використовувати алгоритм "Лічильник" чи "Бульбашка" тому що
вони мають меншу, а тому і найкращу трудомісткість.
Висновки
В процесі виконання курсової роботи
я отримав навички, як
за допомогою ЕОМ
підготувати та вирішувати розрахункові задачі військового та прикладного
характеру.
В результаті обчислення
військово-прикладної задачі:
У першому розділі будував блок схему.
У другому розділі будував програмну
реалізацію курсової роботи, отримав результати, оцінив роботу алгоритмів.
У третьому розділі оцінив
трудомісткість аналітично, графічно; зробив аналіз отриманих результатів.
Визначив кращий алгоритм шляхом порівняння.
В процесі виконання роботи я отримав
навички самостійного вирішення задач. Навчився вирішувати військово-прикладні
задачі за допомогою програм: MS Office, Pascal, Mathcad.
Список використаних джерел
1.
Обчислювальна техніка і програмування. Навчальна література. Під ред. Е.И.
Бобира, ХВУ 1994 г.
.
В.Е. Клімнюк, А.А. Попеленко. Обчислювальна техніка і програмування. Збірка
задач. ХВУ, 1994 г.
.
Д.П. Лабенко, В.А. Толстохатько. Обчислювальна техніка і програмування.
Методичні рекомендації по виконанні курсової роботи. ХВУ, 1996 г.
.
Навчальний посібник. Толстохатько В.А. та ін. Застосування персональних ЕОМ для
розв’язання військово-прикладних задач. Частина 1. Використання персональних
ЕОМ для розв’язання оперативно-тактичних задач. Харків: ХВУ, 2002.
.
Конспект лекцій, Молодожонов С.М., Федотенков А.Н. Применение персональних
микро-ЭВМ для решения военно-прикладных задач. - Харків: ВІРТА,1991.
.
Навчальний посібник. Бобир Е.И и др. Обчислювальна техніка і програмування.
Харків: ХВУ, 1994.
.
Підручник для ВНЗ. Симонович С.В. и др. Інформатика. Базовий курс. - СПб.:
Пітер, 2001.