Міністерство освіти і науки україни національний технічний університет україни

„КПІ”

“Механіко-Машинобудівний Інститут”

Кафедра: “Динаміки і Міцності машин та опору матеріалів”

“КУРСОВА РОБОТА”

З ДИСЦИПЛІНИ «ІНФОРМАТИКА»

Варіант №15

Виконав:

студент гр. МП-02

Чеков Євген Олександрович

Перевірив:

Кучер Микола Кирилович

Оцінка ___

Київ 2011

Зміст

Вступ………………………………………………………………………3

Завдання курсової роботи……………………………………………….4

I. Завдання 1. Розробити алгоритм, що впорядковує елементи

масиву за їх зростанням використовуючи метод ͈ бульбашки ̎ .......5

2.1.Схема програми в Mathcad……………...……………...…..…….…8

2.2.Розв’язок завдання в програмі C++………………….......................9

ІI. Завдання 2. Методом січних знайти всі корені рівняння……....10

2.1.Схема програми в Mathcad……………...……………...…..…….…12

2.2.Розв’язок завдання в програмі C++………………….......................13

ІІІ. Завдання 3. Розробити програму для обчислення визначника матриці А розмірністю n*n…...………..…………………………...…14

3.1. Обчислення визначника в програмі Mathcad...………….............15

3.2. Складання програми обчислення визначника в C++…..…....….16

Висновок………………………………………………………………....17

Література………………………………………………………….…..18

Вступ

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

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

В наш час, вік інформаційних технологій, ми повинні використовувати електронно-обчислювальні машини. На заняттях з інформатики, ми вивчили багато методів для обчислення різних математичних задач. Це стосується обчислення інтегралів, матриць, визначників, знаходження коренів рівнянь парної і не парної кратності, та ін. Ця курсова робота – як підсумок і контроль вивченого матеріалу. В моїй курсовій роботі, у трьох питаннях, ми торкнемось таких основних тем:

метод ͈ бульбашки ̎ що впорядковує елементи масиву за їх зростанням, метод січних для знаходження всіх коренів рівняння, обчислення визначника матриці. Також врахуємо розв’язання цих завдань в програмі MathCad і складемо для них програми в C++.

Завдання курсової роботи

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

А=

ІI. Методом січних знайти всі корені рівняння.

ІІІ. Розробити програму для обчислення визначника матриці А розмірністю n*n:

A=

І

Сортування бульбашкою

Сортування обміном або Сортування бульбашкою є простим алгоритмом сортування. Алгоритм працює таким чином — у поданому наборі даних (списку чи масиві) порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування згідно нього нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це сортування на основі порівнянь.

Продуктивність

Складність алгоритму у найгіршому у середньостатистичному випадку рівна О(n²), де n — кількість елементів для сортування. Існує чимало значно ефективніших алгоритмів, наприклад, з найгіршою ефективністю рівною O(n log n). Тому даний алгоритм має низьку ефективність у випадках, коли N є досить великим, за винятком рідких конкретних випадків, коли заздалегідь відомо, що масив з самого початку буде добре відсортований.

Кролики і черепахи

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

З метою підвищення швидкодії алгоритму, у свій час було здійснено чимало зусиль для зменшення кількості "черепах". Сортування перемішуванням є порівняно не поганим, однак, усе ще у своєму найгіршому випадку має складність O(n2). Сортування гребінцем спершу порівнює великі елементи один з одним, а вже тоді поступово переходить до все менших і менших. Його середньотатистична швидкість приблизно рівна такій в алгоритми Швидке сортування.

Приклад реалізації крок за кроком

Візьмемо масив чисел "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 ) Нарешті, масив відсортовано, і алгоритм може припинити свою роботу.

Реалізація

Алгоритм можна реалізувати так:

Вхід: массив A,який складається з елементів A[1], A[2], ..., A[n-1], A[n]

t := правда

цикл доки t:

t := брехня

цикл для j = 1, 2, ..., n − 1:

якщо A[j] > A[j+1], то:

обменять местами элементы A[j] и A[j+1]

t := истина

На практиці

Хоча, алгоритм є одним із найпростіших алгоритмів сортування, його ефективність є досить низькою, і він погано підходить для сортування великих списків. Більшість інших алгоритмів з такою ж швидкодією O(n2) є ефективнішими за алгоритм сортуванням бульбашками, наприклад, сортування включенням

Через свою простоту, алгоритм часто використовується для пояснення студентам концепції алгоритмів, та алгоритмів сортування, зокрема. Однак, деякі дослідники, як то Оуен Астрахан(Owen Astrachan) ретельно дослідивши даний алгоритм, стверджують, що він настільки поганий і неефективний, що вони навіть не використовуватимуть його в якості прикладу у своїй викладацькій діяльності.

Дональд Кнут у своїй знаменитій праці The Art of Computer Programming прийшов до висновку, що "немає жодних підстав рекомендувати використовувати даний алгоритм, окрім, хіба що через примітну назву і через те, що він є лідером у кількості цікавих теоретичних проблем", частину з яких він обговорює у своїй праці.

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

Сортування бульбашкою також погано використовує можливості сучасних мікропроцесорів. Він вимагає щонайменше удвічі більше операцій, ніж сортування включенням, удвічі більше кешпам'яті, і асимптоматично більше передбачень переходів. Результати експериментів проведених Астраханом показали, що сортування рядка за алгоритмом сортування бульбашками у п'ять разів повільніше за сортування того ж рядка за алгоритмом сортування включенням і на 40% повільніше за сортування за алгоритмом сортування вибором.

І.1. Схема програми в С++

#include <stdafx.h>

#include <iostream>

using namespace std;

int array[100];

int main()

{

int col_el;

printf(" Vvedit cilkist elementiv \n");

scanf("%d",&col_el);

printf(" Vvedit elementu \n");

for (int n=1; n<=col_el ; n++)

scanf("%d",&array[n]);

int trash=0;

for (int i=1; i<=col_el ; i++)

{

for (int j=1; j<=col_el-i; j++)

{

if (array [j]>array [j+1])

{

trash=array[j];

array [j]=array [j+1];

array [j+1]=trash;

}

}

}

printf(" Resultat: \n");

for (int i=1; i<=col_el; i++)

printf("%d ", array [i]);

scanf("%d",&col_el);

return 0;

}

І.2. Розв’язок завдання в програмі Mathcad

IІ

Метод січних

Цей метод застосовується, так як і метод поділу відрізка пополам, для уточнення кореня на відрізку . Будемо вважати, що на даному проміжку функція міняє знак . На графіку функції виберемо дві точки і , які мають наступні координати , .

Рис.2.Графічне зображення обчислювального процесу за методом січних.

Проведемо через ці точки пряму лінію (хорду). Тоді рівняння цієї прямої матиме вигляд

. (1)

Перепишемо рівняння хорди у більш зручному для нас вигляді

, (2)

де

. (3)

Знайдемо точку перетину хорди з віссю ох. Для цього в співвідношення (2) треба покласти . Тоді , звідки легко вираховуємо значення координати .

. (4)

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

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

та .

Тут - деяка мала величина, що визначає точність обчислення кореня, а - обмежує смугу шуму для функції .

ІІ.1. Схема програми в С++

#include <stdafx.h>

#include<stdio.h>

#include<math.h>

float F(float x);

float a,b,e,q,w,x1;

int

main()

{

m1: printf("\n Vvedit a,b,e ");

scanf("\n %f %f %f",&a,&b, &e);

if(F(a)*F(b)>0) {printf("%Perevirte danni"); goto m1;}

m2: x1=a-(((b-a)*F(a))/(F(b)-F(a)));

if(F(a)*F(x1)>0) b=x1; else a=x1;

q=(b-a);

w=F(x1);

if(q<0) q=-q;

if(w<0) w=-w;

if((q<e)&&(w<e)) {printf("\n korin %f",x1); goto m3;} else goto m2;

m3: getchar ();

getchar ();

return 0;

}

float F(float x)

{

return x*x*x-4*x*x+10*x-10;

}