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. int mapowanie( int k, bool * uzyto, int ind, int * jest ) { int suma, suma_trojki; int warto = false; if( mapa.size() == k + 1 ) { 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 ) { 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 ) 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; }
|
|
DejaVu |
» 2018-02-15 19:52:38 Coś takiego? 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 ); } }
|
|
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. |
|
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 :) |
|
garlonicon |
» 2018-02-15 22:25:29 Mała wskazówka: 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? |
|
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. |
|
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. |
|
garlonicon |
» 2018-02-15 23:18:20 W takim razie wzór dla sześciu elementów: 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. |
|
« 1 » 2 |