Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Ознайомлення із методами пошуку. Алгоритм бінарного пошуку
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
ПІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство науки і освіти України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра програмного забезпечення
Звіт з лабораторної роботи № 10
з дисципліни “Алгоритми і структури даних ”
Виконав:
студент групи ПІ – 1
Львів 2008
Тема роботи: Ознайомлення із методами пошуку. Алгоритм бінарного пошуку.
Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із методом бінарного пошуку. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу бінарного пошуку.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Двійковий пошук (англ. Binary Search) — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння.
Двійковий пошук суттєво швидший за лінійний, відносно простий в реалізації і загальновживаний. Обчислювальна складність алгоритму становить О(log2N).
Текст програми
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void main()
{
unsigned int mas[30000],mas2[4001],temp,a,beg=0,end=29999,ser=1,rez=0,i,j;
clrscr();
for(i=0; i<30000; i++)
mas[i]=rand()%4000;
//--------------------------------------------------------------------
j=0;
for (i=0;i<4001;i++)
mas2[i]=0;
for(i=0; i<30000; i++)
mas2[mas[i]]++;
for(i=0; i<=4001; i++)
while(mas2[i]>0)
{
mas[j]=i;
mas2[i]--;
j++;
}
for(i=0; i<29999; i++)
if(mas[i]>mas[i+1])
{
puts("Ne sortuje!");
ser=0;
break;
}
if(ser==1)
puts("Sortuje!");
getch();
//-------------------------------------------------------------------
puts("Vvedit chyslo vid 0 do 4000");
scanf("%i", &a);
if ((a>4000)||(a<0))
{
printf("Nekorectno vvedene chuslo");
getch();
return;
}
//-------------------------------------------------------------------
while (rez==0 && ser>0 && ser<29999)
{
ser=(beg+end)/2;
if(mas[ser]==a)
rez=1;
else
if(mas[ser]<a)
beg=ser;
else
end=ser;
}
//-------------------------------------------------------------------
if(rez==0)
printf("Shykanogo elementa nemaje!\n");
else
printf("%i: %i\n", ser, mas[ser]);
getch();
}
Протокол роботи програми
Висновок: Вивчив та дослідив метод пошуку, як один із методів обробки даних. Ознайомився із методом бінарного пошуку. Виконав лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу бінарного пошуку.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора