Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Źle działający algorytm zliczający

Ostatnio zmodyfikowano 2015-11-02 10:44
Autor Wiadomość
TheReclif
Temat założony przez niniejszego użytkownika
[C++] Źle działający algorytm zliczający
» 2015-11-02 00:21:18
Witam!
Stworzyłem algorytm mający za zadanie zliczenie liczby wystąpień każdego z występujących w drzewie kolorów. Jest to algorytm rekursyjny(rekurencyjny). Kod:
C/C++
struct Wezel
{
    Wezel * lewyWezel;
    Wezel * prawyWezel;
    int kolor;
    Wezel( Wezel * l, Wezel * r, int k )
    {
        lewyWezel = l;
        prawyWezel = r;
        kolor = k;
    };
   
    Wezel( void )
    {
        lewyWezel = NULL;
        prawyWezel = NULL;
        kolor = 0;
    }
};

void zlicz( Wezel * wezel, int * tablica )
{
    if( wezel == NULL )
         return;
   
    tablica[ wezel->kolor ] += 1;
   
    zlicz( wezel->lewyWezel, tablica );
   
    zlicz( wezel->prawyWezel, tablica );
   
    return;
}
Ogólnie, program wczytuje liczbę węzłów, potem "wypełnia" je wartościami kolorów, a potem łączy węzły. Miałem spore obawy co do tego, czy algorytm zadziała, jak trzeba. Niestety, obawy sprawdziły się. Dla 4 węzłów o kolorach 1, 2, 2 i 2 oraz połączeniach {0, 1}, {1, 2} i {2, 3} otrzymałem takie wyniki:
1 0 0 0
.
Jak program wyświetla?:
C/C++
int * kolory;

for( int x = 0; x < n; x++ )
{
    sum = 0;
    fill( kolory, kolory + najwyzszyKolor, 0 );
    zlicz( & wezely[ x ], & kolory );
    for( int y = 0; y < najwyzszyKolor; y++ )
    {
        sum += kolory[ y ] * kolory[ y ]; //Kwadrat wystąpień każdego z kolorów
    }
    cout << sum << " "; //Dodaję wszystkie i wyświetlam sumę
}
Czemu wyszły mi takie dziwne wyniki? Za nic nie mogę pojąć natury ich powstania
P-139499
pekfos
» 2015-11-02 02:14:11
Podaj prawdziwy kod.
P-139501
TheReclif
Temat założony przez niniejszego użytkownika
» 2015-11-02 08:33:58
C/C++
#include <iostream>
#include <vector>
#include <algorithm>

#define sum temp1

using namespace std;

struct Wezel
{
    Wezel * lewyWezel;
    Wezel * prawyWezel;
    int kolor;
    Wezel( Wezel * l, Wezel * r, int k )
    {
        lewyWezel = l;
        prawyWezel = r;
        kolor = k;
    };
   
    Wezel( void )
    {
        lewyWezel = NULL;
        prawyWezel = NULL;
        kolor = 0;
    }
};

void zlicz( Wezel * wezel, int * tablica )
{
    if( wezel == NULL )
         return;
   
    tablica[ wezel->kolor ] += 1;
   
    zlicz( wezel->lewyWezel, tablica );
   
    zlicz( wezel->prawyWezel, tablica );
   
    return;
}

int main( void )
{
    vector < Wezel > wezely;
   
    ios_base::sync_with_stdio( false );
   
    int najwyzszyKolor = 0;
    int n;
    long long temp1, temp2;
    cin >> n;
   
    wezely.reserve( n );
   
    for( int x = 0; x < n; x++ )
    {
        cin >> temp1;
       
        if( temp1 > najwyzszyKolor )
             najwyzszyKolor = temp1 + 1;
       
        wezely.push_back( Wezel( NULL, NULL, temp1 ) );
    }
   
    int * kolory;
   
    for( int x = 0; x < n - 1; x++ )
    {
        cin >> temp1 >> temp2;
        temp2--;
        temp1--;
        if( wezely[ temp1 ].lewyWezel != NULL )
             wezely[ temp1 ].lewyWezel = & wezely[ temp2 ];
        else
             wezely[ temp1 ].prawyWezel = & wezely[ temp2 ];
       
    }
   
    for( int x = 0; x < n; x++ )
    {
        sum = 0;
        fill( kolory, kolory + najwyzszyKolor, 0 );
        zlicz( & wezely[ x ], kolory );
        for( int y = 0; y < najwyzszyKolor; y++ )
        {
            sum += kolory[ y ] * kolory[ y ];
        }
        cout << sum << " ";
    }
   
    cout << endl;
   
    return 0;
}
P-139502
j23
» 2015-11-02 10:44:15
C/C++
int * kolory; <--- !!!
...


fill( kolory, kolory + najwyzszyKolor, 0 );
zlicz( & wezely[ x ], kolory );
Jakim cudem ten program w ogóle coś zwrócił? Na co wskaźnik 'kolory' wskazuje?

Pomijając powyższy błąd, kolor u Ciebie jest typu 'int', więc zakładam, że wielkości mogą być duże. Wartością koloru indeksujesz tablicę 'kolory', co jest dość problematyczne, bo ta tablica musi być wystarczająco duża, żeby każdy kolor miał własną komórkę pamięci - pamięciowo może to być mało efektywne rozwiązanie. Tutaj idealnie sprawdziłby się kontener 'std::map'.
P-139504
« 1 »
  Strona 1 z 1