Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.05.2007, 23:34
Димка

 
Сообщений: n/a

бинарный посик - помогите разобраться
Здравствуйте, пробую написать на Delphi программу использующая бинарный поиск в массиве. Но что то не получается!
Цитата:
int function BinarySearch (Array A, int Lb, int Ub, int Key);
begin
do forever
M = (Lb + Ub)/2;
if (Key < A[M]) then
Ub = M - 1;
else if (Key > A[M]) then
Lb = M + 1;
else
return M;
if (Lb > Ub) then
return -1;
end;
Ругается в третей строчке ( do forever), пишет что пропущено что-то.
Помогите пожалуйста разобраться.

И второй вопросе. И как я понял данный поиск работает только в отсортированном массиве по возрастанию и в массиве не должны повторяться числа, иначе будет не точный поиск.
  #2  
Старый 05.05.2007, 00:10
Пользователь

Отправить личное сообщение для M_Gustokashin Посмотреть профиль Найти все сообщения от M_Gustokashin
 
Регистрация: 24.09.2006
Адрес: Москва, Багратионовская
Сообщений: 81

первый раз такой язык вижу, если честно. это точно Delphi?
  #3  
Старый 05.05.2007, 13:03
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>это точно Delphi?
нет, это гибрид с С и еще с чем-то

Result := -1;
while l <= r do begin
m := (l + r) div 2;
if A[m] < Value then
l := m + 1
else if A[m] > Value then
r := m - 1
else begin
Result := m;
Break;
end;
end;
  #4  
Старый 05.05.2007, 17:06
Димка

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
>это точно Delphi?
нет, это гибрид с С и еще с чем-то

Result := -1;
while l <= r do begin
m := (l + r) div 2;
if A[m] < Value then
l := m + 1
else if A[m] > Value then
r := m - 1
else begin
Result := m;
Break;
end;
end;
Спасибо большое Только как то странно работает.
беру массив 10 элементов. l=1 r=20 расставляю в порядке возрастания,
1; 3; 5;...; 20 . Положение элемента находит просто на ура.
беру массив 10 элементов l=1 r=100 раставляю так же в порядке возрастания 1;5;22;...;100. Он у меня не один элемент не может найти. В чем может быть дело???
  #5  
Старый 05.05.2007, 20:27
Димка

 
Сообщений: n/a

все, вопрос снимается, я разобрался. моленько прогнал
надо было указывать от скальки и до скальки идет цикл, а не максимальный и минимальный элемент массива
пасиба кто откликнулся и помог.
  #6  
Старый 07.05.2007, 21:06
незарегистрированный

 
Сообщений: n/a

Ребят, а как будет это же на C++ Visual ??? я не особо дружу с ним, что то не особо получается у меня
Цитата:
count =0;
while (min<=max){
count=count+1; //Считаем какое кол-во выполнений циклов ушло на поиск числа
i=(min+max)/2;
if (a[i]<x) {min=i+1;} else { if(a[i]>x) { max=i-1; return 0; } else {result=i;
cout << result;
cout << count;}}
return -1;}
Где ошибка??? Только не ругайтесь, я с++ не знаю
  #7  
Старый 07.05.2007, 21:32
незарегистрированный

 
Сообщений: n/a

У меня получилось, вот рабочий код:
Цитата:
#include <iostream.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>

main()
{
long a[100000],max,min,count,i,x,y,z,result;

//Ввод данных
printf("\nVvedite razmer massiva\n");
scanf("%d",&y);
printf("\nVvedite K\n");
scanf("%d",&x);

z=0; //обнуляем счетчик

min=1; // от
max=y; //до
//Заполнения массива
for (i=1;i<y;i++) {
z=z+1; // Шаг заполнения массива равен 1
a[i]=z; //Заполняем массив
}

count =0; //Обнуляем счетчик циклов
while (min<=max){
count=count+1; //Считаем какое кол-во выполнений циклов ушло на поиск числа
i=(min+max)/2;
if (a[i]<x) {min=i+1;} else { if(a[i]>x) { max=i-1; } else {result=i;
cout << "I = ";
cout << result;
cout << "\n";
cout << "Ko/|-Bo = ";
cout << count;
cout << "\n";
return 0;}}
}
}
Теперь следующий вопрос, как сделать чтобы поиск работал с большими числами??? с миллионами ?
  #8  
Старый 08.05.2007, 06:18
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>как сделать чтобы поиск работал с большими числами???
поиску наплевать на размер чисел
в твоем случае, видимо, нужно изменить метод заполнения массива
  #9  
Старый 08.05.2007, 12:23
незарегистрированный

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
>как сделать чтобы поиск работал с большими числами???
поиску наплевать на размер чисел
в твоем случае, видимо, нужно изменить метод заполнения массива
Предложения будут??? Я уже все перепробовал
  #10  
Старый 08.05.2007, 18:08
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Я уже все перепробовал
что перепробовал???
Заполни массив большими слкчайными числами и отсортируй.
Или в строке z = z + 1 увеличивай не на 1, а на случайное число
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите разобраться Мёртвый Анархист Реализация, исходники, языки 13 23.01.2007 08:25