75659

Плгоритми пошуку та сортування для одновимірних масивів

Лабораторная работа

Информатика, кибернетика и программирование

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

Украинкский

2015-01-24

338.16 KB

3 чел.

Міністерство  освіти  і  науки України

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

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №9 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: алгоритми пошуку та сортування для одновимірних масив.

Мета: набуття практичних навичок застосування алгоритмів пошуку та сортування.

Завдання:

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

 

Варіант № 9.

9

Елементи присутні в обох масивах А і В в одному екземплярі

Складність алгоритму

Складність алгоритму пошуку (для одного масиву) дорівнює O( 2N ) від t ;

Складність алгоритму сортування дорівнює O( 4N2 +4N+1 ) від t, де:

t - час виконання;
Nкількість елементів масиву.

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

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


Блок-схема алгоритму



Лістинг програми 

#include <iostream>

#include <vector>

using namespace std;

void Input(int arr[], int num)  // input array

{

   for (int i=0; i<num; ++i)

       cin>>arr[i];

}

void Print(int arr[], int num)  // output array

{

   cout<<endl;

   for (int i=0; i<num; ++i)

       cout<<arr[i]<<" ";

}

void Sort(int arr[], int num)  // bubble sort

{

   int temp=0;

   for (int j=0; j<num-1; ++j)

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

           if (arr[i]>arr[i+1])

           {

               temp=arr[i];

               arr[i]=arr[i+1];

               arr[i+1]=temp;

           }

}

bool Search(int arr1[], int n, int arr2[], int m, int val)  // search

{

   int arrVal_1 = 0;

   int arrVal_2 = 0;

   for (int i=0; i<n; ++i)

       if(arr1[i]==val)

           ++arrVal_1;

   for (int i=0; i<m; ++i)

       if(arr2[i]==val)

           ++arrVal_2;

   if (arrVal_1==1&&arrVal_2==1)

       return true;

   else return false;

}

void SearchWithoutVal(int arr1[], int n, int arr2[], int m, vector<int> &mutual)

{

       vector<int> singleArr1;

       for  (int i=0; i<n; ++i)

       {

           int arr1_val=0;

           int temp=arr1[i];

           for (int j=0; j<n; ++j)

           {

               if (temp==arr1[j])

                   ++arr1_val;

           }

            if (arr1_val==1)

                   singleArr1.push_back(temp);

       }

       vector<int> singleArr2;

       for  (int i=0; i<m; ++i)

       {

           int arr2_val=0;

           int temp=arr2[i];

           for (int j=0; j<m; ++j)

           {

               if (temp==arr2[j])

                   ++arr2_val;

           }

               if (arr2_val==1)

                   singleArr2.push_back(temp);

       }

      for (size_t i=0; i<singleArr1.size(); ++i)

           for (size_t j=0; j<singleArr2.size(); ++j)

               if(singleArr1[i]==singleArr2[j])

                   mutual.push_back(singleArr1[i]);

}

int main()

{

   int n=0;

   int m=0;

   int value=0;

   int command = 0;

   cout<<"n(A)= "; cin>>n;

   cout<<"m(B)= "; cin>>m;

   int A[n];

   int B[m];

   cout<<"\n\nInput "<<n<<" elements of A array: ";

   Input(A, n);

   Print(A,n);

   cout<<"\n\nInput "<<m<<" elements of B array: ";

   Input(B,m);

   Print(B,m); 

   while(command!=123)

   {

   cout<<"\n~~~~~~~~~~~~~~~~~~ MENU ~~~~~~~~~~~~~~~~~~~~~~~~~";

   cout<<"\n- To input value for searching press 1.\n- To search for all of the unique mutual values press 2.";

   cout<<"\n- To input value for searching WITH SORT press 3.\n- To search for all of the unique mutual values WITH SORT press 4.";

   cout<<"\n- To exit press 123.  \nInput command:";

   cin>>command;

   if (command==1)

   {

       cout<<"\nInput the value to search for: ";

       cin>>value;

       if(Search(A, n, B, m, value))

           cout<<"\nThis value appears in both arrays only one time.\n";

       else

           cout<<"\nThis value doesn't match the conditions.\n";

   }

   else if (command==3)

   {

       cout<<"\n\nSorted arrays are: ";

       Sort(A,n);

       Print(A,n);

       Sort(B,m);

       Print(B,m);

       cout<<"\nInput the value to search for: ";

       cin>>value;

       if(Search(A, n, B, m, value)) 

           cout<<"\nThis value appears in both arrays only one time.\n";

       else

           cout<<"\nThis value doesn't match the conditions.\n";

   }

   else if(command==2)

   {

       cout<<"\n\nSearching for the mutual unique elements: ";

       vector <int> mutual;

       SearchWithoutVal(A, n, B, m, mutual);

       for(size_t i =0; i<mutual.size(); ++i)

           cout<<mutual[i]<<"  ";

   }

   else if (command==4)

   {

       cout<<"\n\nSorted arrays are: ";

       Sort(A,n);

       Print(A,n);

       Sort(B,m);

       Print(B,m);

        cout<<"\n\nSearching for the mutual unique elements: ";

       vector <int> mutual;

       SearchWithoutVal(A, n, B, m, mutual);

       for(size_t i =0; i<mutual.size(); ++i)

           cout<<mutual[i]<<"  ";

   }

   }

   return 0;

}


Результат виконання 

Висновки

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


 

А также другие работы, которые могут Вас заинтересовать

32310. Место и роль ТГП в системе юридических наук 40.5 KB
  Они дают знания о развитии и чертах государства и права вообще безотносительно к конкретным государствам или праву действующему на отдельной территории. К фундаментальным наукам относятся: o теория государства и права; o история государства и права России и зарубежных стран; o история политических и правовых учений. Эти науки изучают отдельные отрасли права. Они призваны выявить специфику той или иной отрасли ее особенности характерные черты отличия от других отраслей права.
32311. Методология юридической науки 39.5 KB
  Методология юридической науки. Особенности науки теории государства и права выражаются не только в ее предмете но и в методе. Под методом науки понимается совокупность приемов средств принципов и правил с помощью которых обучающийся постигает предмет получает новые знания. Метод это подход к изучаемым явлениям предметам и процессам планомерный путь научного познания и установления истины.
32312. Общая характеристика власти догосударственного периода 37 KB
  Любое общество представляет собой своего рода целостный социальный организм систему который отличается той или иной степенью организованности урегулированности упорядоченности общественных отношений. Для первобытнообщинного строя были характерны следующие черты: наличие лишь примитивных орудий и неспособность человека без помощи всего рода выжить и обеспечить себя пищей одеждой жилищем. Все взрослое население рода и мужчины и женщины имели право участвовать в обсуждении и решении любого вопроса связанного с деятельностью рода....
32313. Азиатский способ производства и возникновение государств на Др.Востоке (восточно-деспотических государств) 34.5 KB
  Постепенно по мере роста масштабов кооперации коллективной трудовой деятельности зародившиеся еще в родоплеменных коллективах зачатки государственной власти превращаются в органы управления и господства над суммами общин которые в зависимости от широты экономических целей складываются в микро и макрогосударства объединяемые силой централизованной власти. Общинники считаются свободными однако фактически все стало государственной собственностью включая личность и жизнь всех подданных которые оказались в безраздельной власти...
32314. Возникновение государственности в Европе (Афины, Рим, германцы, славяне). Общие закономерности и особенности 50 KB
  В отличие от азиатского государства ведущим государствообразующим фактором на территории Европы было классовое разделение общества. Следовательно для генезиса Афинского государства характерно то что оно возникает непосредственно и прежде всего из классовых антагонизмов развивающихся в недрах родоплеменного общества. В длившейся 200 лет борьбе между двумя группами свободных членов римского родоплеменного общества плебеи вырывали у патрициев одну уступку за другой. Если само положение Греции и Рима способствовало...
32315. Теории возникновения государства и права 43 KB
  Одни государства подчас могут распадаться СССР Югославия Чехословакия; другие объединяются в более крупные такой процесс возможно начался в рамках Европейского Союза. Могут зародиться новые причины и формы такого возникновения что бесспорно только обогатит теорию государства. Основные теории происхождения государства теологическая патриархальная договорная насилия органическая материалистическая психологическая патримониальная и ирригационная ставят во главу угла какойлибо один конкретный доминирующий способ...
32316. Государственная власть: понятие и общие черты 33 KB
  В юридической литературе одни авторы рассматривают власть как определенную функцию присущую любому коллективу обществу; другие исследователи как волевое отношение властеотношение властвующего и подвластного субъектов; третьи как способность властвующего управляющего навязывать свою волю другим лицам; четвертые как организованную силу способную подчинять воле определенной социальной общности других людей. Власть понимается также как управление связанное с принуждением. И наконец зачастую под властью понимается государство или его...
32317. Сущность государства. Признаки и определение понятия государства. Различные подходы к определению понятия государства 45 KB
  Сущность государства. Признаки и определение понятия государства. Различные подходы к определению понятия государства. Его определяют и как общественный союз свободных людей с принудительно установленным мирным порядком посредством предоставления исключительного права принуждения только органам государства Н.
32318. больших группах классах тех или иных объектов обладающих набором общих характерных для каждого типа приз 27.5 KB
  В его основе лежит учение об общественноэкономической формации которая включает в себя тип производственных отношений базис и соответствующий ему тип надстройки государство право и т. Ленина и других решающим фактором общественного развития который детерминирует и соответствующий тип надстроечных элементов: государство и право. Рабовладельческое государство есть орудие поддержания власти рабовладельцев над рабами которые были собственностью свободных граждан. Феодальное государство это диктатура класса феодалов земельных...