75659

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

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

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

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

Украинкский

2015-01-24

338.16 KB

4 чел.

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

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

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

Кафедра ПЗ

Лабораторна робота №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;

}


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

Висновки

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


 

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

72837. Типы круговоротов веществ в природе: геологический, биологический и антропогенный 71 KB
  Большой круговорот веществ в природе геологический обусловлен взаимодействием солнечной энергии с глубинной энергией Земли и осуществляет перераспределение вещества между биосферой и более глубокими горизонтами Земли.
72838. Местообитания и экологическая ниша. Типы связей и взаимоотношений между организмами 80.5 KB
  Для того чтобы описать экологическую нишу организма нужно знать чем он питается кому он служит пищей его способность к передвижению и его воздействие на другие организмы и на неживые элементы внешней среды.
72839. Нормирование ЭМП. Защита от воздействия электромагнитных полей 67 KB
  Различные виды неионизирующих излучений электромагнитных полей ЭМП оказывают разное физиологическое воздействие. В связи со всё большим распространением источников ЭМП в быту СВЧ микроволновые печи мобильные телефоны телерадиовещание и на производстве оборудование ТВЧ радиосвязь...
72840. Техногенные источники электромагнитных полей. Электростатические поля. Биологическое действие электромагнитных полей 62 KB
  Однако за последние 50-60 лет возник и сформировался новый значимый фактор окружающей среды ЭМП антропогенного происхождения или электромагнитный смог. Его создают 2 большие группы искусственных источников: изделия которые специально создавались для излучения электромагнитной энергии...
72841. Воздействие вредных веществ на организм человека в условиях производства. Системы промышленной вентиляции и кондиционирования 66 KB
  Вредные вещества могут проникать в организм человека через органы дыхания органы пищеварения а также кожу и слизистые оболочки. Через дыхательные пути попадают пары газо и пылеобразные вещества через кожу - преимущественно жидкие вещества.
72843. Промышленные источники вибраций. Биологическое действие вибраций. Нормирование вибраций 61 KB
  Вибрация - это механическое колебательное движение системы с упругими связями; движение точки или механической системы, при котором происходит поочередное возрастание и убывание во времени значений по крайней мере одной координаты.
72844. Инфразвук. Средства защиты от инфразвука 58.5 KB
  Снижение неблагоприятного воздействия инфразвука достигается комплексом инженерно-технических и медицинских мероприятий основными из которых являются: устранение причин генерации инфразвука в источнике образования повышение жесткости конструкций больших размеров устранение...