VPF::Бинарный поиск по диагоналям матрицы.

Avaj

Дата 28.9.2008, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 212
Регистрация: 14.7.2008
Где: Владивосток.

Репутация: 1
Всего: 3

Вобщем нужно реализовать бинарный поиск квадратной матрице А[n][n] по диагоналям, параллельным побочной (т.е. диагоналями здесь будут эл-ты A[0][0], A[n-1][n-1], побочная диагональ и все параллельные ей)

Алгоритм поиска вот такой:

Код


char string[]="0245789AAABDFHJKLXYZ"; // sorted ASCIIZ string
char symbol='J'; // symbol to find
unsigned int left,right; // bounds of the area where we search
unsigned int middle; // center of the area where we search
unsigned int length=sizeof(string)/sizeof(char); // string length

void main(void)
{
 printf("String: %s\n",string);

 left=0;
 right=length-1;

 while (left<right)
 {
   middle=(left+right)/2;
   if (string[middle]<symbol) left=middle+1; else right=middle;
 }
}

по-подробней он описан здесь.

С другим алгоритмом бинарного поиска я уже разобрался и реализовал, smile

А вот с приведённым выше - нифига не получается smile

.

Короче ближе к делу - Я ни как немогу найти у себя в коде ошибку из-за которой поиск не работает!

Вот ф-ция, которая работает(упрощённый алгоритм бинарного поиска):

Код


template <class Type> bool bin_search1(Type **a, Type *b, int n2, int n, Type x){
    int i, j, k, Li, Ri, Lj, Rj, Mi, Mj;
    bool found ,res = false;
    for(i=0;i<n;i++){        //поиск в первых n - диагоналях    
        Li = i;
        Lj = 0;
        Ri = 0;
        Rj = i;
        found = false;
        while(Lj<=Rj && !found){
            Mi = (Li + Ri)/2;    
            Mj = (Lj + Rj+1)/2;
            if(a[Mi][Mj] == x){
                found = true;
                b[i] = Mj+1;
                res = true;
            }
            else
                if(a[Mi][Mj]<x){
                    Li = Mi-1;
                    Lj = Mj+1;
                }
                else{
                    Ri = Mi+1;
                    Rj = Mj-1;
                }
    }
    /*for(i=1;i<n;i++){                      //поиск в остальных n-1 - диагоналях
        k=1;
        for(j=i;j<n;j++){
            a[n-k][j];
            k++;
        }
    }*/
    }
    return res;
}

Пояснение:

Этой ф-ции передаётся двумерный массив n*n(ну или квадратная матрица), в котором(-ой) и нужно произвести поиск заданного элемента(x) по диагоналям, параллельным побочной - диагонали пронумерованы начиная с эл-та A[0][0] - диагональ №0 и заканчивая элементом A[n-1][n-1] - диагональ №2n-2. Т.е. как вы поняли, сама побочная диагональ будет иметь номер n-1.
Диагонали отсортированы по неубыванию слева на право.
Затем производится сам поиск и результаты поиска заносятся в одномерный массив b, т.е если в i-ой диагонали эл-т найден, то его позиция в диагонали заносится в b[i].

Ну а n2 - ненужный пока параметр.

Так вот, как я уже говорил, эта функция работает, и суть вопроса в том почему не работает эта функция:

Код


template <class Type> bool bin_search2(Type **a, Type *b, int n2, int n, Type x){
    int i, j, k, Li, Ri, Lj, Rj, Mi, Mj;
    bool res = false;
    for(i=0;i<n;i++){        //поиск в первых n - диагоналях    
        Li = i;
        Lj = 0;
        Ri = 0;
        Rj = i/*+1*/;      //Вот тут "+1" не надо! )))
        while(Lj<Rj){
            Mi = (Li + Ri+1)/2;    
            Mj = (Lj + Rj)/2;
            if(a[Mi][Mj]<x){
                Li = Mi-1;
                Lj = Mj+1;
            }
            else{
                Ri = Mi;
                Rj = Mj;
            }
        }
        if(a[Ri][Rj] == x){
            b[i] = Rj+1;
            res = true;
        }
    }
    /*for(i=1;i<n;i++){
        k=1;
        for(j=i;j<n;j++){
            a[n-k][j];
            k++;
        }
    }*/
    return res;
}

Как видите, это тоже бинарный поиск, но немного модифицированный.

Кто скажет, где ошибка?

P.S. не обращайте внимание на то, что ф-ции ищут только в первых n-диагоналях, потом доделаю.

Я сам всё понял smile

, но всё равно Большое Спасибо всем товарищам форумчанам и до скорых встреч.

Это сообщение отредактировал(а) Avaj - 28.9.2008, 14:45

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »