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

Тема в разделе "Pascal and Delphi", создана пользователем Rusl, 30 май 2010.

  1. Rusl

    Rusl Гость

    Подскажите, что не так в программе. Нужно найти 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.
     
  2. chirs

    chirs Гость

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

    Rusl Гость

    Пусть дан упорядоченный по неубыванию массив целых или действительных чисел 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). Применить алгоритм деления пополам
     
  4. Rusl

    Rusl Гость

    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:
     
  5. Rusl

    Rusl Гость

    При вводе последовательности а: 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:
     
Загрузка...

Поделиться этой страницей