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;

}


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

Висновки

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


 

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

84931. Казка – казочка. Українська народна казка. Казкові герої 1.22 MB
  Мета: продовжити знайомство з усною народною творчістю засвоювати форми звертання українською мовою формувати вміння визначати змісткову лінію казки вірно називати і характеризувати героїв казок ставити та відповідати на питання виховувати любов до мови книги вміння спілкуватися один з одним...
84932. Закріплення вивчених букв. Робота з дитячою книгою. Українська народна казка «Курочка Ряба» 161 KB
  Мета. Формувати у дітей поняття про казку як художній твір, розвивати мовлення, уяву, фантазію; закріплювати вміння читати склади, слова, речення з вивченими буквами, вдосконалювати навички звукового аналізу слів; вчити будувати звукові моделі; збагачувати мовленнєвий словник дітей...
84933. Українська народна казка «Рукавичка» 317 KB
  Мета. Ознайомити учнів з українською народною казкою «Рукавичка». Повторити назви диких звірів. Розвивати уміння слухати і розуміти українську мову, увагу, пам’ять, мислення. Прищеплювати інтерес до української народної творчості.
84934. Звук м. Позначення його буквами Мм. Читання складів із вивченими буквами. Звуковий аналіз слів. Словниково-логічні вправи 31 KB
  Мета: знайомити з артикуляцією звука м буквами Мм формувати в учнів уміння читати склади та слова з вивченими буквами; закріплювати знання учнів про вивчені букви їх звукове значення; розвивати мовлення дітей фонематичний слух інтерес до народних свят; виховувати доброту чуйне ставлення до мами.
84935. Складання тексту-опису лисички за питаннями і опорними словами 70.5 KB
  Мета. Вчити складати найпростіший текст - опис за питаннями і опорними словами, добирати до тексту заголовок. Формувати вміння стисло і послідовно висловлювати думку, передавати її на письмі. Вдосконалювати навички літературної вимови слів. Збагачувати словниковий запас.
84936. Подорож країною Мовознавство 244.5 KB
  Мета: у невимушеній ігровій формі повторити вивчене з курсу мови; поширювати й уточнювати словниковий запас учнів, розвивати мислення, мовлення, пам’ять, увагу; створити атмосферу доброзичливості, чесного змагання; виховувати любов до рідного слова як неоціненного духовного багатства...
84937. Узагальнюючий урок за розділом «Речення» 51 KB
  Мета. Узагальнити і повторити знання по темі «Речення», збагачувати словниковий запас учнів; розвивати творче мислення; виробляти навички каліграфічного письма; виховувати бережне ставлення до природи. Обладнання: ілюстрації, листочки, схеми до гри, таблиці, магнітофон.
84938. Розповідні речення. Розділові знаки в кінці розповідних речень. Складання і інтонування розповідних речень 59 KB
  Мета: дати уявлення дітям про розповідні речення учити інтонувати розповідні речення аналізувати навчальний матеріал збагачувати словниковий запас учнів розвивати спостережливість мову учнів уяву виховувати вбачати красу осінньої природи.
84939. Урок розвитку зв’язного мовлення у 2 класі 40 KB
  Пізньої осені, коли промерзає ґрунт, зменшується кількість корму, насамперед у комах; їжаки зариваються в опале листя і впадають у сплячку аж до березня. У цей час у них дуже повільне дихання (до 6 разів на хвилину), різко знижується температура тіла, серце робить лише кілька ударів на хвилину.