c++ metoda naiwna wyszukiwania wzorca-problem

[pangapz 0]

Witam,

mam problem z naiwnym algorytmem wyszukiwania wzorca w tablicy dwuwymiarowej.

zasada dzialania programu : 

 

1.program pobiera z pliku tekstowego wzorzec i tekst

2. tworzy dwie tablice dwuwymiarowe - wzorzec i tekst

3. bada ilosci kolumn i wierszy w kazdej z tablic

 

No i teraz zaczynaja sie schody poniewaz kolejnym punktem jest wyszukanie wzorca w tekscie. Oczywiscie debugger nie wyrzuca zadnych bledow, program sie odpala, wykonuje 1, 2 ,3 punkt lecz algorytm nie zostaje wykonany.

 

zamieszczam kod do algorytmu :

 

w-ilosc wierszy wzorca

t-ilosc wierszy tekstu

dl_w-ilosc kolumn wzorca

dl_t-ilosc kolumn tekstu

for ( i=0 ; i<( t - w ); i++) 
{ 
   for ( j=0 ; j<( dl_t - dl_w ); j++) 
   { 
      for ( x=0 ; x<w ; x++) 
      { 
         for ( y=0 ; y< dl_w; y++) 
         {  
            if ( tekst[i + x][j + y] != wzorzec[x][y]) 
            { 
               g = 0 ; 
               break ;  
            } 
         } 
         if ( g == 0 ) 
         { 
            cout << "znaleziono -> " << ( i + 1 )  << "x" << ( j + 1 ); 
            break; 
         } 
      }    
   }
}   

Edytowane 23 Marca 2014 przez pangapz

[Luki91 157]

Po pierwsze, trudno znaleźć błąd w nieczytelnym kodzie. Na przyszłość wystrzegaj się:

- Robienia wielu zmiennych o nazwach a, b, c, d, e ... To nie nauka abecadła, tylko programowanie. Zmienna powinna sugerować, co oznacza, a nie że jest jakaś zmienna g i przyjmuje magiczną wartość 0

- Łańcuszka pętli. Zagnieżdżenie w sobie czterech pętli zapętla umysł, gdy chcesz to wszystko zrozumieć Twórz procedury (funkcje), które wykonują jakiś wydzielony fragment pracy i uruchamiaj je w co najwyżej podwójnej pętli.

 

 

Pierwszy błąd, jaki widzę, to:

            if ( tekst[i + x][j + y] != wzorzec[x][y]) 
            { 
               g = 0 ; 
               break ;  
            } 
         } 
         if ( g == 0 ) 
         { 
            cout << "znaleziono -> " << ( i + 1 )  << "x" << ( j + 1 ); 
            break; 
         } 

Stwierdzasz, że tekst != wzorzec, a jednak ustawiasz flagę g, która z tego co widzę oznacza, że znaleziono dopasowanie. Co najgorsze, nigdzie w następnych krokach tej flagi nie resetujesz.

[Hans Olo 92]

Od siebie dodam, że lepiej jest używać tablic jednowymiarowych z zastosowaniem offsetów symulujących drugi wymiar, algorytmy są wtedy prostsze w realizacji.

[pangapz 0]

Na pewno przy pisaniu kolejnych kodów zastosuje się do twoich wskazówek

if ( tekst[i + x][j + y] != wzorzec[x][y]) 
            { 
               g = 1 ; 
               break ;  
            } 
         } 
         if ( g == 0 ) 
         { 
            cout << "znaleziono -> " << ( i + 1 )  << "x" << ( j + 1 ); 
            break; 

Teraz lepiej ?

 

 

 

Od siebie dodam, że lepiej jest używać tablic jednowymiarowych z zastosowaniem offsetów symulujących drugi wymiar, algorytmy są wtedy prostsze w realizacji.

Jestem chyba zbyt duzym nowicjuszem aby korzystac z takich zastosowan.

Odgórnie mam pracować na tablicach 2d, jest to narzucone przez mojego prowadzącego.

 

 

EDIT:

Algorytm w końcu zaczął działać lecz jeszcze nie działa poprawnie, jakieś rady co dalej ?

Edytowane 23 Marca 2014 przez pangapz

[Onvil 12]

Podaj zadanie od prowadzącego może będzie łatwiejsze do zrozumienia, bo ciężko jest określić co dokładnie ma to robić.

Edytowane 24 Marca 2014 przez Onvil

[pangapz 0]

Napisać naiwny algorytm wyszukiwania wzorca (k²) w tekscie (k*w), działający na tablicach dwuwymiarowych typu char.

Program ma pobierać z pliku tablice tekstu(k*n) i tablice wzorca(k²).

Porównać (złożoność obliczeniową) w.w algorytmu, z algorytmem Rabina Karpa dla tych samych plików.

 

Generalnie brakuje mi algorytmu wyszukiwania naiwnego jak i Rabina Karpa, lecz gdy będę już miał ten pierwszy, myślę że z drugim nie będzie już takiego problemu

 

Moj program do tej pory pobiera dane z pliku i tworzy tablice, nastepnie oblicza ilosc kolumn i wierszy dla wzorca jak i dla tekstu. Algorytm który zamieściłem działa ale tylko w pewnym stopniu

Edytowane 24 Marca 2014 przez pangapz