Бинарный поиск в Паскаль

  • Автор темы Rusl
  • Дата начала
R

Rusl

#1
Подскажите, что не так в программе. Нужно найти ki - решение задачи поиска места bi среди ai .

Листинг программы:

for i:=1 to n+1 do
s:=round((i+(n+1))/2);
While i<(n-1) do
if b>=a then begin
k:=s+1; end
else begin
k:=s; end;
for i:=1 to n do
write(k);
repeat until keypressed;

End.
 
C

chirs

#2
какая-то бессмыслица, а не программа у тебя...
Например, для чего этот цикл нужен ?
Код:
for i:=1 to n+1 do
s:=round((i+(n+1))/2);
для чего тут n+1 раз вычисляется значение s ?
после выполнения этого цикла переменная i будет равна n+2
и цикл
Код:
While i<(n-1) do
не выполнится ни разу, т.к. i заведомо больше чем n-1
Вообщем, глупости какие-то, а не программа.
Напишите лучше полностью условие задачи. Что дано и что надо получить.
 
R

Rusl

#3
Пусть дан упорядоченный по неубыванию массив целых или действительных чисел a1<=a2<=...<=an и пусть дано некоторое число b (соответственно целое или действительное), для которого нужно найти такое место среди чисел a1,...,an , чтобы после вставки числа b на это место упорядоченность не нарушилась. Если вследствие равенства между собой некоторых элементов массива число b можно вставлять на разные места, то требуется определить ближайшее к началу массива место. Эта задача называется поиском места элемента. Для b имеется n+1 возможность: b<=a1, a1<b<=an, an<b, и решением задачи поиска элемента b будет соответственно одно из чисел 1,...,n+1. Для решения задачи полезен алгоритм, который называется алгоритмом деления пополам: взять первоначально 1 и n+1 в качестве границ поиска места элемента; далее, до тех пор пока границы не совпадут, шаг за шагом сдвигать эти границы следующим образом: сравнить b с a, где s - целая часть среднего арифметического границ; если b>a - заменить прежнюю нижнюю границу на s+1, а верхнюю оставить без изменения, иначе оставить без изменения нижнюю границу, а верхнюю заменить на s; когда границы совпадут, став равными некоторому числу t, выполнение вышеописанного алгоритма закончится с результатом t. (Число сравнений, требуемых этим алгоритмом, не превосходит [log2(n+1)]+1 ).
Само задание:
a) даны действительные числа a1,...,an (причем упорядочены по возрастанию a1<=a2<=...<=an) и b1,...,bm. Получить натуральные числа k1,...,km такие, kj- решение задачи поиска места bj среди a1,...,an (i=1,...,m). Применить алгоритм деления пополам
 
R

Rusl

#4
for i:=1 to m do begin
s:=round((i+(i+1))/2);

if b>=a then begin
k:=s+1; end
else begin
k:=s; end;
write(k);
end;
Вроде подправил, но все равно, что то не так :rolleyes:
 
R

Rusl

#5
При вводе последовательности а: 1 3 5 7 9 11 и последовательности b: 2 4 6 8 значение k: 2 3 4 5. Т.е. правильно, но при вводе а: 2 4 6 8 11 13 и в: 1 3 5 7 значени k: 2 2 4 4 , что не есть правильно :rolleyes: