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

ustalanie zbioru na podstawie drugiego zbioru

Ostatnio zmodyfikowano 2018-02-16 15:32
Autor Wiadomość
mikewazowski
Temat założony przez niniejszego użytkownika
ustalanie zbioru na podstawie drugiego zbioru
» 2018-02-15 16:40:38
mając zbiór np Mapa = (3, 4, 2, 6, 3) tworzony jest zbiór A, w którego skład wchodzą wszystkie elementy mapy oraz sumy sąsiadujących dwójek (3+4,4+2,...), trójek, czwórek itp aż do sumy wszystkich elementów mapy - dla tej konkretnej mapy wyszedłby zbiór A = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18}. Moim zadaniem jest odtworzyć prawidłową kolejność elementów w mapie mając do dyspozycji zbiór A i informację że pierwszy element mapy to zawsze element ostatni A minus element przedostatni A (w tym wypadku 18-15 =  3)

Program wylicza ile liczb powinno być w mapie, po czym sprawdza po kolei wszystkie liczby ze zbioru A czy mogą być w mapie.
Utknęłam na etapie w którym prawidłowo sprawdzane są tylko pary i nie mogę wpaść na pomysł jak mam sprawdzać trójki, czwórki, bez tworzenia osobnych funkcji. Problemem jest też to że w przypadku tego zbioru A utworzy mi w pierwszej iteracji mapę (3,3,...) ponieważ jest 6 w zbiorze A - ale mapa z 3 na drugim miejscu nie ma prawa istnieć - nie wiem więc jak sprawdzać z góry czy liczba może zająć dane miejsce w mapie jeśli dotychczasowe sumy się zgadzają, ale te z kolejnych iteracji już nie.

C/C++
int mapowanie( int k, bool * uzyto, int ind, int * jest )
{
    int suma, suma_trojki;
    int warto = false; // do sprawdzania czy warto kontunuowac roziwazanie
   
    if( mapa.size() == k + 1 ) //  jesli na mapie jest juz k+1 elementow (czyli wymagana licznosc)
    {
        cout << "jest";
        * jest == 1;
        return 1;
    }
    else for( int i = 0; i < A.size(); i++ )
    {
        suma = mapa.back();
       
        if( uzyto[ i ] == false )
        {
            suma += A[ i ];
           
            if( suma > A.back() )
            {
                warto = false;
                break;
            }
            else
            for( int j = 0; j < A.size(); j++ )
            {
                if( A[ j ] == suma && uzyto[ j ] == false ) // jesli taka suma jest w zbiorze A i nie jest sumą jakis innych liczb
                {
                   
                    uzyto[ j ] = true;
                    uzyto[ i ] = true;
                    mapa.push_back( A[ i ] );
                    warto = true;
                    break;
                }
            }
        }
       
        if( mapa.size() == k + 1 )
        {
            * jest = 1;
            break;
            return 1;
        }
        if( warto == true ) // jesli rozwiazanie warto kontynuowac bo sumy wystapily w A
             mapowanie( k, uzyto, ind + 1, jest );
       
    }
}

void nieuzyte( int licznosc, bool * odwiedzone )
{
    for( int i = 0; i < licznosc; i++ )
    {
        odwiedzone[ i ] = false;
    }
}
int main()
{
   
    // .....
   
    mapowanie( k, uzyte, 0, & jest );
   
    if( jest == 0 )
         cout << endl << "nie ma rozwiazania" << endl;
   
   
    return 0;
}
P-169419
DejaVu
» 2018-02-15 19:52:38
Coś takiego?
C/C++
std::vector < int > v;
//...
std::vector < int > result;
for( auto n = 1; n <= v.size(); ++n )
     appendResults( v, result, n );

std::sort( result.begin(), result.end() );

//...
void appendResults( const std::vector < int >& _v, std::vector < int >& _result, int _n )
{
    for( auto i = _n - 1; i < _v.size(); ++i )
    {
        auto suma = 0;
        for( auto k = 0; k < _n; ++k )
             suma += _v[ i + k ];
       
        _result.push_back( suma );
    }
   
}
P-169424
mikewazowski
Temat założony przez niniejszego użytkownika
» 2018-02-15 20:15:10
Dokładnie na odwrót, z tego co widzę to twój program tworzy ten zbiór wszystkich sum -  A na bazie mapy, a ja muszę odtworzyć mapę mając ten większy zbiór A.
P-169425
DejaVu
» 2018-02-15 21:08:22
A no widzisz :P To przynajmniej ktoś ma teraz łatwiej zrozumieć o co chodzi w zadaniu :P Czasami rekurencja ułatwia rozwiązywanie dziwnych problemów - może tu też pomoże.

Ja bym pewnie najpierw ustalił ile liczb ma być w zbiorze wynikowym (w Twoim przykładzie 5), a potem ustalił zbiory liczb, których suma n liczb (w przykładzie n=5) nie przekroczy maksymalnej wartości (w Twoim przykładzie 18). Potem bym dla każdego zbioru bym kombinował jak ustalić poprawną kolejność liczb (np. wykluczyć, że zbiór {2,3,(...)} nie może istnieć, ponieważ nie masz nigdzie liczby 5.

Ogólnie fajne zadanie na pokombinowanie :)
P-169426
garlonicon
» 2018-02-15 22:25:29
Mała wskazówka:
C/C++
A = { x, y, z };
Mapa = { z - y, y };
Najprostszą mapą jest mapa dwuelementowa. Powyżej masz wzór zamieniający trzyelementowy zbiór A na dwuelementową mapę. Wyprowadź sobie taki sam wzór dla sześciu, dziesięciu, piętnastu elementów A (odpowiednio trzech, czterech, pięciu elementów mapy). Co zauważasz?
P-169428
pekfos
» 2018-02-15 22:48:31
mając do dyspozycji zbiór A i informację że pierwszy element mapy to zawsze element ostatni A minus element przedostatni A (w tym wypadku 18-15 =  3)
Mapa może zawierać tylko liczby nieujemne? Ten sposób na uzyskanie pierwszego elementu nie zadziała w przypadku liczby ujemnej.
P-169429
mikewazowski
Temat założony przez niniejszego użytkownika
» 2018-02-15 22:58:38
@garlonicon szczerze mówiąc nie wiem zauważam nic z tego wzoru, mógłbyś rozwinąć myśl?
@pekfos Tak, tylko nieujemne liczby.
P-169430
garlonicon
» 2018-02-15 23:18:20
mógłbyś rozwinąć myśl?
W takim razie wzór dla sześciu elementów:
C/C++
A = { a, b, c, d, e, f };
Mapa = { f - e, decode3( { a, b, c, d } / { f - e } ) };
gdzie decode3 oznacza poprzednio podany wzór używany do zdekodowania trójelementowego zbioru
{ x, y, z }
 do dwuelementowej mapy
{ z - y, y }
. Najpierw obliczasz pierwszy element (wynoszący
f - e
), następnie wyrzucasz go z czteroelementowego, posortowanego zbioru
{ a, b, c, d }
, a później dekodujesz ten trzyelementowy zbiór i otrzymujesz dwa kolejne elementy mapy. Teraz spróbuj wyprowadzić wzór dla dziesięciu elementów (czteroelementowa mapa). Wskazówka: potraktuj powyższy algorytm jako decode6, poprawnie dekodujący posortowany, sześcioelementowy zbiór do trzyelementowej mapy.
P-169431
« 1 » 2
  Strona 1 z 2 Następna strona