Форум программистов, компьютерный форум, киберфорум
Наши страницы

Turbo Pascal

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.95
simon140906
2 / 2 / 1
Регистрация: 06.04.2010
Сообщений: 52
#1

Двоичный(бинарный) поиск - Turbo Pascal

17.05.2010, 21:31. Просмотров 5426. Ответов 5
Метки нет (Все метки)

Доброго времени суток,коллеги =) Возникла у меня проблема - написал программу,реализующую двоичный поиск,а препод говорит,что неправильно)) и не говорит,где ошибка >___<
Проверьте пожалуйста=)
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
program dvoichn_poisk;
uses crt;
var  a: array [1..16] of integer;
    g,m,i,h,k,n,l,j,smena,kol,centr,d:integer;
     flag:boolean;
     label 1,2,3;
 
begin
clrscr;
randomize; kol:=0;
for i:=1 to 16 do
    begin
    a[i]:=0;
    end;
for i:=1 to 16 do
    begin
    a[i]:=random(100);
    writeln(a[i]);
    end;
3: for h:=0 to 17 do begin
   for m:= 0 to 17 do
       begin if a[m]<a[m-1] then
       begin smena:=a[m-1]; a[m-1]:=a[m]; a[m]:=smena; end;
       end;
       end;
{for g:=1 to 16 do
    begin
    write (a[g],' ');
    end;}
writeln('vvedite argument poiska');
readln(k); l:=0; flag:=false; centr:=a[8]; d:=8;
if k=centr then begin kol:=kol+1; goto 1; end;
if k<centr then begin kol:=kol+1; d:=4; centr:=a[d];
           if k=centr then begin kol:=kol+1; goto 1; end;
           if k<centr then begin kol:=kol+1; d:=2; centr:=a[d];
                      if k=centr then begin  kol:=kol+1; goto 1; end;
                      if k<centr then begin kol:=kol+1;d:=1; centr:=a[d]; end;
                      if k>centr then begin kol:=kol+1;d:=3; centr:=a[d]; end;
                      end;
           if k>centr then begin kol:=kol+1; d:=6; centr:=a[d];
                   if k=centr then begin kol:=kol+1; goto 1; end;
                   if k<centr then begin kol:=kol+1;d:=5; centr:=a[d]; end;
                   if k>centr then begin kol:=kol+1;d:=7; centr:=a[d]; end;
                   end;
                end;
if k>centr then begin kol:=kol+1;d:=12; centr:=a[d];
           if k=centr then begin kol:=kol+1; goto 1 ;end;
           if k<centr then begin kol:=kol+1; d:=10; centr:=a[d];
                   if k=centr then begin kol:=kol+1; goto 1; end;
                   if k<centr then begin kol:=kol+1;d:=9; centr:=a[d]; end;
                   if k>centr then begin kol:=kol+1;d:=11; centr:=a[d]; end;
                end;
           if k>centr then begin kol:=kol+1; d:=14; centr:=a[d];
                   if k=centr then begin kol:=kol+1; goto 1; end;
                   if k<centr then begin kol:=kol+1; d:=13; centr:=a[d]; end;
                   if k>centr then if k=a[15] then begin kol:=kol+1; d:=15; end;
                                   if k=a[16] then begin kol:=kol+1; d:=16 end;
                                   end;
                 end;
 
 
 
{for j:=1 to 16 do
begin
l:=l+1;
if k=a[j] then begin flag:=true; goto 1; end;
end;}
{if flag=false then begin writeln ('poisk zavershen  ne udachno');
   writeln ('chislo sravnenii = ',l); end;}
 
1: if k=a[d] then begin writeln ('poisk zavershen udachno');
   writeln ('chislo sravnenii = ', kol); end;
if k<>a[d] then begin  writeln('poisk zavershen ne udachno');
   writeln ('chislo sravnenii = ', kol); end;
readln;
end.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2010, 21:31
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Двоичный(бинарный) поиск (Turbo Pascal):

Двоичный поиск - Turbo Pascal
Задание: Реализуйте алгоритм бинарного поиска. Входные данные: В первой строке входных данных содержатся натуральные числа N и K...

Добавить бинарный поиск - Turbo Pascal
Программа готова, просто добавить этот &quot;ужасный&quot; бинарный поиск если нужно условие: В заданном массиве A(N) вычислите среднее...

Бинарный поиск в матрице - Turbo Pascal
Матрица упорядочена по столбцам по не убыванию. Как можно реализовать бинарный поиск непосредственно в матрице? Переписывать...

задание на бинарный поиск - Turbo Pascal
Используя бинарный поиск элементов в массиве найти на каком месте находится заданный элемент. П.С. если не трудно , можно чтобы было...

Последовательный и бинарный поиск - Turbo Pascal
нужно сделать 2 программы: 1)которая осуществляет последовательный поиск(без барьера) дан массив из 9 элементов записей ввод...

Бинарный поиск в типизированном файле - Turbo Pascal
function bsearch(var search:LongInt;var f:tfile ):Boolean; var Low,High,mid,z:longint; found:Boolean; begin ...

5
lera8
634 / 217 / 26
Регистрация: 03.11.2009
Сообщений: 488
17.05.2010, 21:37 #2
эм ваша программа двоичного поиска как то странно выглядит..Это вам я так понимаю в массиве найти заданный элемент?
1
simon140906
2 / 2 / 1
Регистрация: 06.04.2010
Сообщений: 52
17.05.2010, 21:44  [ТС] #3
И если кто может,объясните нубу человеческим языком,что творится тут

Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.

Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел
1 2 3 4 5. Здесь средним элементом является 3. Это значени.

меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел
4 5. На следующем шаге нужный элемент будет найден. При дво.

ичном поиске число сравнений в худшем случае равно
log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.

Приводимую ниже функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой произвольной структуры данных, изменив блок сравнения и определение типа данного "DataItem".

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function BSearch (item: DataArray; count:integer;                             
key:DataItem):integer;     
var       low, high, mid: integer;       
found:boolean;     
begin       
low:=1; 
high:=count;       
found:=false;         { не найден }      
 while (low<=high) and (not found) do       
begin         
mid:=(low+high) div 2;         
if key<item[mid] then high:=mid-1         
else if key>item[mid] then low:=mid+1        
 else found:=true;  { найден }       
end;       
if found then BSearch:=mid       
else BSearch:=0;  { не найден }    
 end; { конец поиска }
взято с http://www.cyberguru.ru/programming/...ia-page19.html

Добавлено через 33 секунды
Цитата Сообщение от lera8 Посмотреть сообщение
эм ваша программа двоичного поиска как то странно выглядит..Это вам я так понимаю в массиве найти заданный элемент?
да-да =) в массиве)
0
lera8
634 / 217 / 26
Регистрация: 03.11.2009
Сообщений: 488
17.05.2010, 21:47 #4
ну вот код двоичного поиска, все в принципе просто, у вас хорошая теория найдена
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var
a: array [1..20] of integer;
i,j,x,n,c,nx,r,l:integer;
flag:boolean;
begin
  writeln('Введите размер и элемет для поиска');
  readln(n,x);
    writeln('Исходный массив');
   for i:=1 to n do
     begin
       a[i]:=random(250)-27;
       write(a[i]:4);
     end;
      writeln;
     i:=0;
   repeat
       i:=i+1;
       flag:=false;
     for j:=n-1 downto i do
        if a[j] > a[j+1] then begin
          c:=a[j]; a[j]:=a[j+1]; a[j+1]:=c; flag:=true;
        end;
   until not flag;
   nx:=0; l:=1; r:=n;
    while l <= r do begin
     c:=(l+r) div 2;
     if x=a[c] then begin
       nx:=c; r:=l-1;
     end;
     if x > a[c] then r:=c-1;
     if x < a[c] then l:=c+1;
   end;
     writeln('Отсортированный массив');
    for i:=1 to n do
      write(a[i]:4);
    if nx=0 then writeln('Не найден')
    else  writeln('Числу x',x,'равен элемент',a[nx])
end.
1
simon140906
2 / 2 / 1
Регистрация: 06.04.2010
Сообщений: 52
17.05.2010, 21:48  [ТС] #5
огромное спасибо вам, очень большое)))
1
lera8
634 / 217 / 26
Регистрация: 03.11.2009
Сообщений: 488
17.05.2010, 21:49 #6
а если что у меня массив заполняется случайными числами исправьте если хотите явно убедиться что правильно работает, а написана это прога без процедур

Добавлено через 20 секунд
Пожалуйста)
1
17.05.2010, 21:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2010, 21:49
Привет! Вот еще темы с ответами:

Бинарный поиск. В массиве A(N) найти элементы, принадлежащие диапазону [М, К] - Turbo Pascal
В массиве A(N) найти элементы, принадлежащие диапазону .

Бинарный поиск. В массиве X (К) заменить каждый пятый элемент на ноль - Turbo Pascal
В массиве X(К) заменить каждый пятый элемент на ноль. Заранее спасибо!

Бинарный поиск. В массиве X(К) заменить каждый пятый элемент на ноль - Turbo Pascal
В массиве X(К) заменить каждый пятый элемент на ноль.

В отсортированном массиве произвести бинарный поиск индекса элемента со значением K - Turbo Pascal
Дан линейный целочисленный массив из N элементов. Отсортировать элементы массива в порядке не убывания их значений (метод сортировки...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru