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

[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

[dog]

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

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

[Lapp]

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

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

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

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

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

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

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

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

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