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;

}


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

Висновки

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


 

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

17471. Документальные системы АИС 189.5 KB
  Лекция Документальные системы Документальные системы предназначенные для обработки поиска представления полнотекстовых документов или справочнореферативной информации ведут свое происхождение от библиотечнореферативных служб или информационных центров вы...
17472. ТЕХНОЛОГИИ ПРОЕКТИРОВАНИЯ АИС 84.5 KB
  Тема ТЕХНОЛОГИИ ПРОЕКТИРОВАНИЯ АИС Современные информационные технологии предоставляют широкий набор способов реализации ИС выбор которых осуществляется на основе требований со стороны предполагаемых пользователей которые как правило изменяются в процессе раз...
17473. АВТОМАТИЗИРОВАННЫЕ ИС ПО ОБЛАСТЯМ ПРИМЕНЕНИЯ 51 KB
  Лекция АВТОМАТИЗИРОВАННЫЕ ИС ПО ОБЛАСТЯМ ПРИМЕНЕНИЯ Рассмотрим некоторые основные типы АИС ориентированные на различные области применения. Автоматизированные информационные системы по законодательству Законодательство Российской Федерации в настоящее ...
17474. Географические информационные системы (ГИС) 27 KB
  Лекция Географические информационные системы ГИС Важным специфическим классом АИС специализирующихся на определенном виде информации в основном графической являются географические системы ГИС. Согласно некоторым оценкам 80 всех существующих данных являю
17475. Гипертекстовые АИС 107.5 KB
  Лекция Гипертекстовые АИС Слово гипертекст hypertext буквально переводится как нелинейный текст nonlinear text. Элемент гипертекста узел дискретный объект. Узлы между которыми возможен переход считаются смежными а сама возможность перехода называется связью. Для описан...
17476. Документальный информационный поиск в сети Интернет 40.5 KB
  Лекция №9 Документальный информационный поиск в сети Интернет Информационнопоисковые системы Интернет могут быть разделены по функциональноструктурному принципу на следующие классы: полностью распределенные системы где реализуются принципы распределенных вы
17477. Конструирование системы упражнений по теме Геометрическая оптика на основе обобщения опыта работы учителя физики лицея №40 Морозовой Н.В 2.46 MB
  Педагогический опыт как результат практики является критерием истины: он либо подтверждает либо отвергает те или иные нововведения. Этот опыт как правило результат творческих поисков педагогов в нем сливаются воедино творческое новаторское и в то же время традиционное начала.
17478. Автоматизированные информационные системы (АИС), структура и классификация 127 KB
  Лекция №2 Автоматизированные информационные системы АИС структура и классификация АИС комплекс автоматизированных информационных технологий предназначенный для информационного обслуживания организованного непрерывного технологического процесса подготовк...
17479. Организационное обеспечение и пользователи АИС 36.5 KB
  Организационное обеспечение и пользователи АИС В состав организационного обеспечения АИС принято включать структурные подразделения организации осуществляющие управление технологическими процессами и поддержку работоспособности системы а также совокупность док