Здравствуйте,

вот в универе заставили решить задачку на Delphi, я бы на С++ или на PHP решил бы, а вот с Delphi пока не особо знаком. Прошу помощи:confused:

Задача 1. Таблица выиграшей денежной лотереи представляется в виде массива номеров, которые выиграли a1,...,an и массивом выиграшей в рублях p1,..,pn (pi — это выиграш, который выпадает на номер ai (i=1,...,n)). Вычислить суммарный выиграш, который выпадает на билет с номерами b1,...,bm. Для развязания задачи использовать алгоритм деления пополам.

Мои пояснения к задаче, для лучшего понимания:
Допустим это массив выигрышных номеров: a =(1, 2, 3, 4, 5,...,36)
Это массив выиграшей в рублях: p = ( 3, 6, 1, 5, 8,...,1) руб
т.е. если выбрать из массива выигрышных номеров число 4 то выигрыш будет равен 5 руб и т.д.

Допустим лотерея 6 из 36,
делаем ввод 6 чисел к примеру 2, 5, 18, 22, 30, 32
загоняем их в массив b

далее циклами вычисляем ключи чисел, 2, 5, 18 ... в массиве a

потом тупо по полученным ключам вытаскиваем из массива P суммы денег и плюсуем их.

Что касается алгоритма деления пополам, я никогда не применял. Теоретически массив делится пополам и определяем в какую сторону перебирать значения. Это типа делается для ускорения процесса вычисления.

Буду очень признателен за неоценимую помощ!
Артем

Здравствуйте, ukrsonic, Вы писали:

...
алгоритм деления пополам — двоичный поиск в отсортированном массиве. позволяет снизить число сравнений до O(log(N)). Так как ищется номер билета в массиве a — надо сначала отсортировать массив a любым способом (не забывая что A(i) связано с P(i)). двоичный поиск в классическом варианте будет таким:

type 
  arr_i: array of integer;

function binary_search(a:arr_i;value:integer):integer;
var
  l,r,x:cardinal;
begin
  result := -1;
  l:=low(a);
  r:=high(a);
  while l<r do
    begin
      x := (l+r) shr 1; // div 2
      if a[x]=value then
        begin
          result := x;
          break;
        end
      else if a[x]<value then l:=x+1;
      else r:=x-1;      
    end;
  while (result>0) and (a[result-1]=value) do dec(result);
end;

дальше что на си что на пхп будет примерно также как на дельфи. удачи.

Благодарю Leonidze,

Позвольте мне прокомментировать код, чтобы было видно что я правильно понял. Поправьте меня пожалуйста, если что не так

type 
  arr_i: array of integer; // Объявляем числовой массив arr_i 

function binary_search(a:arr_i;value:integer):integer; //Создаем функцию двойного поиска и передаем ей 2 параметра, 1- объект a: числового массива arr_i, 2 - value искомое число  
var
  l,r,x:cardinal; // регистрируем локальные количественные переменные l - left, r- right, x 
begin // начало выполнения сценария
  result := -1; //??
  l:=low(a);//передаем  переменной l начальное значение массива = 1. Или это передается ключ начального значения, которым будет 0?
  r:=high(a);//передаем максимальное значение или ключ переменной r
  while l<r do // запускаем цикл, до тех пор пока l<r
    begin
      x := (l+r) shr 1; // что делает shr ?
      if a[x]=value then //тут условие,  если зачение массива, к примеру a[6] равняется значению искомого числа value тогда выполняется следущее
        begin
          result := x; // переменной result передаем ключ x
          break;
        end
      else if a[x]<value then l:=x+1; // если значение массива (к прим. a[6]) меньше искомого числа тогда, перезаписываем переменную l = 6+1 
      else r:=x-1;  //или, перезаписываем переменную r = 6-1 
    end;
  while (result>0) and (a[result-1]=value) do dec(result);// можно пояснить эту строку?
end;

Спасибо

Здравствуйте, Аноним, Вы писали:

А>Благодарю Leonidze,

А>Позвольте мне прокомментировать код, чтобы было видно что я правильно понял. Поправьте меня пожалуйста, если что не так

А>type 
А>  arr_i: array of integer; // Объявляем числовой массив arr_i 
// не сам массив, его тип чтобы в функцию спокойно передавать

А>function binary_search(a:arr_i;value:integer):integer; //Создаем функцию двойного поиска и передаем ей 2 параметра, 1- объект a: числового массива arr_i, 2 - value искомое число  
А>var
А>  l,r,x:cardinal; // регистрируем локальные количественные переменные l - left, r- right, 
// x - среднее значение
А>begin // начало выполнения сценария
А>  result := -1; //??
А>  l:=low(a);//передаем  переменной l начальное значение массива = 1. Или это передается ключ начального значения, которым будет 0?
// нижний индекс массива. 0
А>  r:=high(a);//передаем максимальное значение или ключ переменной r
// верхний индекс (последнего элемента)
А>  while l<r do // запускаем цикл, до тех пор пока l<r
// тут очепятка, прошу прощения. д.б. l<=r
А>    begin
А>      x := (l+r) shr 1; // что делает shr ? == div 2, т.е. целочисленно делит пополам. (сдвиг вправо на 1 бит)
А>      if a[x]=value then //тут условие,  если зачение массива, к примеру a[6] равняется значению искомого числа value тогда выполняется следущее
// если медиана равна искомому, возвращаем индекс
А>        begin
А>          result := x; // переменной result передаем ключ x
А>          break;
А>        end
// если медиана больше искомого - дальше рассматриваем "левую" половину массива, иначе - "правую"
А>      else if a[x]<value then l:=x+1; // если значение массива (к прим. a[6]) меньше искомого числа тогда, перезаписываем переменную l = 6+1 
А>      else r:=x-1;  //или, перезаписываем переменную r = 6-1 
А>    end;
А>  while (result>0) and (a[result-1]=value) do dec(result);// можно пояснить эту строку?
// это на случай массива вида 1,2,2,2,2,2,2,5 и поиска 2 - смещаемся влево, если не первый элемент (result>0) и предыдущий ключ равен текущему; т.е.
// для примера код без этой строки вернет индекс 3, хотя индекс первой "2" - это 1.
А>end;

А>Спасибо
пожалуйста. этот, и еще многие алгоритмы можно найти у Кнута, Кормена и других гуру. рекомендуется к прочтению