Алгоритм деления пополам

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

  1. Rusl

    Rusl Гость

    Помогите пожалуйста с решением задачи на Паскаль:

    Разработать программу, реализующую поиск места элемента в отсортированном массиве алгоритмом деления пополам.

    Даны действительные числа a1, …, an, b1, …, bm (a1<=a2<= … <=an). Получить натуральные числа k1, …, km такие, что ki — это решение задачи поиска места bi среди a1, …, an (i=1, …, m). Применить алгоритм деления пополам.

    Например даны последовательность А: 1 3 5 6 7 9 и последовательность В: 2 1 3 4. Элемент К получается: 2 1 3 4, т.к. В1=2, значит оно должно занимать место под номером 2 после единицы в массиве А. Далее берем В2=1, К здесь будет равно 1, т.к. занимает первое место и т.д.

    Что не так, я не могу разобраться. Пока дошел до конца, чуть репа не треснула :KillMe:

    Program pr2;
    uses crt;
    var
    a:array [1..1000] of real;
    b:array [1..1000] of real;
    k:array [1..1000] of real;
    i,n,m,s:integer;
    flag:boolean;
    Begin
    clrscr;
    n:=6;
    m:=5;
    for i:=1 to n do
    begin
    writeln('Ââåäèòå',i ,'-é ýëåìåíò ïîñëåäîâàòåëüíîñòè a' );
    readln(a);
    end;
    for i:=1 to m do
    begin
    writeln('Ââåäèòå',i ,'-é ýëåìåíò ïîñëåäîâàòåëüíîñòè b' );
    readln(b);
    end;
    for i:=1 to m do
    begin
    s:=round(n/2);
    flag:=true;
    while (flag) do
    begin
    if (b>a) then
    begin
    inc(s);
    if (b<a) then
    begin
    k:=s;
    flag:=false;
    end;
    end else
    begin
    dec(s);
    if (b>a) then
    begin
    k:=s+1;
    flag:=false;
    end;
    end;
    end;
    writeln(a:5:1 , b:5:1 , k:5:1);
    writeln(' ');
    end;
    repeat until keypressed;
    End.
     
  2. DarkDaiver

    DarkDaiver Гость

    сделаю за умеренную плату
    ISQ: 412842920
    MAIL: darkdaiver777@gmail.com
     
  3. Dock1100

    Dock1100 :-]

    Регистрация:
    9 ноя 2009
    Сообщения:
    678
    Симпатии:
    0
  4. vital

    vital Больной Компом Детектед

    Регистрация:
    29 янв 2006
    Сообщения:
    2.468
    Симпатии:
    27
    Этот Алгоритм называется Бинарный поиск. ЕГо вариантов реализации в инете - тонны.
    ПС.
    Считается, что сходу написать без ошибок алгоритм бинарного поиска, при всей его простоте НЕ могут 95% всех программистов.
     
Загрузка...

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