Задача на линейный поиск, помогите найти ошибку Опции

[dog]

1. Дан двумерный массив A [NxM] , элементы которого меняются по определенному закону. Определить, есть ли в массиве элемент со значением Q.

PROGRAM PRPV1;
const n=3;m=3;
type Tarr = Array[1..n,1..m] of real;
var
A:Tarr;

i,j:BYTE;
q:real;



BEGIN
    FOR i:=1 TO n DO
    FOR j:=1 TO m DO
    A[i,j]:=30*(n+1-j)+0.2*i; {закон изменения элементов}

    FOR i:=1 TO n DO {вывод массива на печать}
    BEGIN
        FOR j:=1 TO m DO
        WRITE(A[i,j]:0:2,' ');
        WRITELN;
    END;

    WRITELN('Enter Q'); {ввод значения для поиска}
    READLN(q); {до сюда все работает идеально}

    i:=1;
    j:=1;
    WHILE((i<=n) and (A[i,j]<>q)) do {проблемы начинаются тут}
    begin
    WHILE((i<=m) and (A[i,j]<>q)) do
    j:=j+1;
    IF j>m then
    i:=i+1;
    end;

    IF (i > n) AND (j > m) THEN {вывод на печать найденного элемента или сообщение об отсутствии элемента}
       WRITELN('not found')
    ELSE
       WRITELN('found A[',i,',',j,']');

END.

Программа работает идеально, ищет элементы выводит их индексы. Но когда задаешь элемент, которого нет в массиве программа зависает.

Сообщение отредактировано: dog - 1.04.2010 4:06

[Lapp]

Программа работает идеально, ищет элементы выводит их индексы.

Сама себя не похвалишь - кто еще похвалит?

Проограмма работает неправильно и при этом выходит за пределы массива. НИКОГДА не отключай Range Check до полного окончания отладки - и будет тебе ЩАСТЬЕ )). А также желательно не путать буковку i с буковкой j (хоть они и похожи)). А еще - инициализацию j нужно внести внутрь цикла по i. Короче, примерно так:

    i:=1;
    WHILE ((i<=n) and (A[i,j]<>q)) do begin
      j:=1;
      WHILE((i<=m) and (A[i,j]<>q)) do j:=j+1;
      if j>n then i:=i+1;
    end;

Последнее: условие на j при печати - лишнее. Вот так:

    IF i >n THEN {вывод на печать найденного элемента или сообщение об отсутствии элемента}
       WRITELN('not found')
    ELSE
       WRITELN('found A[',i,',',j,']');

Успехов тебе )).

PS
да хорошая у тебя прога, хорошая ))

[dog]

Спасибо огромное. Вот что значит свежий взгляд.

И еще один вопросик. Можно ли эту программу усовершенствовать, чтобы она работала не по линейному поиску а по бинарному поиску. В методичке только алгоритм бинарного поиска в одномерном массиве там ничего сложного, а по двумерному массиву ничего. Подскажите хоть алгоритм и смысл как проводить бинарный поиск в двумерном массиве. Программу целиком писать не надо просто объясните на каком-нибудь примере как делать бинарный поиск в условиях двумерного массива. Спасибо.

[volvo]

просто объясните на каком-нибудь примере как делать бинарный поиск в условиях двумерного массива.

А точно так же, как и в условиях одномерного массива. Дело все в том, что при наличии двумерной матрицы мы в любое время и для любого элемента можем получить смещение этого элемента от начала массива, правда? Нам же известны номер строки и номер столбца, а также число элементов в строке. Обратное преобразование (из смещения относительно начала в номера строки и столбца) - тоже делается очень просто. Это все, что нужно.

Так что никакой разницы между бинарным поиском в одно- двух- и вообще n-мерном массиве нет. Если у тебя есть программа, осуществляющая бинарный поиск в одномерном массиве, ее очень просто приспособить к любой размерности. Единственное условие - массив должен быть отсортирован, это необходимое условие при котором работает бинарный поиск.

Я не рассматриваю хаки, при которых описывается одномерный массив, расположение которого совпадает с расположением многомерного, и весь поиск осуществляется именно в одномерном массиве. Это не совсем честно, хотя многие именно этим способом и пользуются.

[dog]

Спасибо.

Ну вот допустим у нас есть классический алгоритм бинарного поиска в одномерном массиве:

i := 1;  { индекс первого элемента массива }
  j := n;  { индекс последнего элемента массива (0, если массив пуст) }
 
  while i <= j do begin
    { ищем элемент на интервале индексов от i до j, включительно }
    k := i + (j - i) div 2;  { k = элемент посередине интервала }
    if x > A[k] then
      i := k + 1
    else if x < A[k] then
      j := k - 1
    else
      break;  { искомый элемент найден }
  end;

Тут все более чем понятно.

Пробуем его модифицировать под двумерный массив

b := 1;  { индекс первого элемента массива }
e := nm;  {e - индекс последнего элемента, где nm = n*m, то есть размерность двумерного массива  }
 
  while b <= e do begin
    { ищем элемент на интервале индексов от b до n, включительно }
    k := b + (e - b) div 2;  { но индекс k середины массива должен быть двумерным так ведь? в общем с этого момента ничего не понятно }
    if x > A[k] then
      i := k + 1
    else if x < A[k] then
      j := k - 1
    else
      break;  { искомый элемент найден }
  end;

Сообщение отредактировано: dog - 3.04.2010 16:56

[volvo]

Я ж написал, что надо делать в случае двумерного массива... Смотри: допустим, у нас матрица, описанная так:

const
  m = 3; n = 5;
var
  a: array[1 .. m, 1 .. n] of integer;

, то есть матрица, состоящая из M строк по N элементов в каждой. Вот смотри, что происходит с твоим же кодом, чтобы заставить его работать:

b := 1;  { индекс первого элемента массива }
e := n*m;  {e - индекс последнего элемента, где nm = n*m, то есть размерность двумерного массива  }
 
  while b <= e do begin
    { ищем элемент на интервале индексов от b до n, включительно }
    k := b + (e - b) div 2;  { Вот k как раз одномерно... А дальше: }
    if x > A[(pred(k) div n) + 1, (pred(k) mod n) + 1] then { <--- Преобразуем k в номер строки и столбца }
      i := k + 1
    else if x < A[(pred(k) div n) + 1, (pred(k) mod n) + 1] then { <--- здесь - тоже самое }
      j := k - 1
    else
      break;  { искомый элемент найден }
  end;
...
  { Ну, и ответ печатать в виде: }
  writeln('строка = ', (pred(k) div n) + 1, ' столбец = ', (pred(k) mod n) + 1);

Очень много изменений?

[Lapp]

Спасибо огромное. Вот что значит свежий взгляд.

Пожалуйста . Да, и свежий взгляд тоже )).

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

dog, твой вопрос не определен.

Как сказал уже volvo, для того, чтобы использовать бинарный поиск (БП), массив должен быть упорядочен. Упорядочить одномерный массив - дело нехитрое. С упорядочиванием же двумерного ситуация в корне иная.

Чем отличается отличается прямая от плоскости или от трехмерного пространства? В частности, тем, что прямую упорядочить - не проблема, а вот упорядочить плоскость.. Ну, нельзя сказать, какая точка больше - A или B! Я не буду говорить, что этого сделать совершенно невозможно (например, можно опираться на биекцию прямой в плоскость), но для этого нужно ввести дополнительное отношение (отношение порядка) и при этом будет невозможно сохраненить "геометрию": две геометрически близкие точки будут далеки в смысле нашего упорядочивания, и наоборот.

Конечно, двумерный массив - это не плоскость. Хотя бы потому, что он конечен. Но все же его упорядочивание остается неоднозначным. volvo, например, опирался на упорядочение по строкам, но кто сказал, что this is the case? Массив может быть упорядочем по столбцам (не вижу никакого преимущества строк перед столбцами в смысле задачи) или, скажем, по диагоналям. Или по спирали..

Вывод такой.
Упорядочивание - прерогатива одномерной структуры. Упорядочить двумерное образование - означает сначала спроектировать на одномерное, а потом упорядочивать уже в нем. Именно поэтому в твоей методичке отсутствовала инфа по двумерным массивам, думаю. Вопрос не технический, вопрос принципиальный. Его решение таково: определить способ упорядочивания, сделать отображение двумерной структуры в одномерную - и упорядочить так, как сказано в методичке. А общего бинарного поиска (независимого от способа упорядочивания) просто не существует. Потому не существует его описания. И я бы не рекомендовал думать, что способ упорядочивания по строкам - какой-то выделенный, что он типа дефолтный, обычный и т.п. Обычного выделенного дефолтного способа не существует ВООБЩЕ. Не подумай, что я придираюсь, это действительно важно понять.

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